Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

What does “Undecidable” mean, anyway

buttondown.com

Post reply on HN
Print view View original

121–130 of 196 posts

Re: What does “Undecidable” mean, anyway

#121

Post by Ukv »

bubblyworld wrote: post #96
Animats wrote: post #73

Any deterministic system with a finite number of states is decidable, in the halting problem sense. Either it halts or repeats a state. The halting problem only applies for infinite memory. Now, there are finite state systems where the halting problem is arbitrarily hard. But that's not undecidability. That's complexity. That's a problem in the space where P=NP lives. The article does not make this distinction, and i…

I don't think this is an important distinction. The point of Turing machines is that you can ask questions like "can all instances of this problem be solved uniformly, and how relatively expensive is it?". This requires infinite memory in a formal sense , because instances of (most) problems can be arbitrarily large. Yes, if you ask the same question with a fixed (finite) memory restriction on everything, the answer…

> Yes, if you ask the same question with a fixed (finite) memory restriction on everything, the answer is uninteresting. To me, this is... uninteresting. It tells you nothing about the underlying logical structure of your problem, which is what mathematicians are really trying to get at!

> (first and foremost Turing machines are a tool for analysing problems mathematically, not a model of your laptop)

I think what makes Animats's distinction worth stressing is that a lot of people miss this and fall into the trap of making false/misleading claims about the impact of the halting problem on actual computers/software.

For instance, claiming that the halting problem proves there are problems humans can solve that computers fundamentally can't, giving "the halting problem makes this impossible" as reason against adding a halt/loop detector to a chip emulator, making all sorts of weird claims about AI[0][1], or arguably even this author's claim that a halt detector would make bcrypt cracking trivial.

[0]: https://mindmatters.ai/2025/02/agi-the-halting-problem-and-t...

[1]: https://arxiv.org/pdf/2407.16890

Re: What does “Undecidable” mean, anyway

#123

Post by yusina »

dooglius wrote: post #118
yusina wrote: post #117

Earlier quoted context omitted.

And how does your decider recognize that a state has been attained twice? If I make the input system large enough then you don't have enough space in your decider to save all the states which it has observed.

What do you mean "space in your decider"? My decider takes finite but unbounded memory, same as the machine it's deciding.

Ok, if that's the class of systems we are talking about, then the system that your decider wants to check does not need to attain the same state twice. It may or may not terminate, and your decider may never know. You can't have it both ways. Keep in mind that the input can be as adversarial as it wants and knows, including having full knowledge of what your decider is trying to do.

Re: What does “Undecidable” mean, anyway

#124

Post by bubblyworld »

Ukv wrote: post #121
bubblyworld wrote: post #96

Earlier quoted context omitted.

I don't think this is an important distinction. The point of Turing machines is that you can ask questions like "can all instances of this problem be solved uniformly, and how relatively expensive is it?". This requires infinite memory in a formal sense , because instances of (most) problems can be arbitrarily large. Yes, if you ask the same question with a fixed (finite) memory restriction on everything, the answer…

> Yes, if you ask the same question with a fixed (finite) memory restriction on everything, the answer is uninteresting. To me, this is... uninteresting. It tells you nothing about the underlying logical structure of your problem, which is what mathematicians are really trying to get at! > (first and foremost Turing machines are a tool for analysing problems mathematically, not a model of your laptop) I think what ma…

That's fair, I've run into a lot of misconceptions like that before. And probably believed some of them at earlier points in my life =P

(Roger Penrose himself makes a version of that claim in "the Emperor's New Mind", so we're in good company...)

About the bcrypt thing... yeah, so one way you can do it is write a program that generates all possible keys starting with the letter 'a', and tests them. Then you run your halting oracle on that, and if it returns true you know the first letter of the key is 'a'.

Do this for each index/letter combination and you can crack bcrypt keys in linear time (in the number of calls to your halting oracle).

Re: What does “Undecidable” mean, anyway

#125

Post by Ukv »

yusina wrote: post #117
dooglius wrote: post #115

Earlier quoted context omitted.

That doesn't sound right. All my decider needs to do is wait for a repeated state (no halt) or a halt. If the state space is finite then one of these is guaranteed to happen.

And how does your decider recognize that a state has been attained twice? If I make the input system large enough then you don't have enough space in your decider to save all the states which it has observed.

> If I make the input system large enough then you don't have enough space in your decider to save all the states

We have cycle detection algorithms that don't require saving all states and work in the same big-O space complexity (constant factor overhead) as just running the input system normally without cycle detection.

To my understanding that means that, for any input system that runs in finite-but-unbounded space, the detector will determine whether it halts in finite-but-unbounded space - unless I am misunderstanding that term.

Re: What does “Undecidable” mean, anyway

#126

Post by tliltocatl »

pdpi wrote: post #119
mreid wrote: post #65

This is a really nice explanation of decidability. One extra thing it might be worth mentioning is that there are many more functions `f : string -> boolean` then there are programs that implement those functions. When I first encountered this topic I had trouble intuitively understanding how there could not exist an `IS_HALTING` function when it is also just a function that takes in a string (representing a program…

> The result becomes less weird when you realize that that almost all functions from string -> boolean are not expressible as a program. I think this is one of those cases where a maths background makes computer science much easier. It only takes enough calculus to get you to entry level differential equations before you’re confronted with the fact that most functions ℝ → ℝ aren’t elementary functions (or admit any c…

IMHO what just referring to uncountability misses is that not only most functions are unexpressable, many __useful ones__ are not. Most ℝ→ℝ functions (and even most real numbers) are so unremarkable there is no way to uniquely name them. The fact that some useful functions are undecidable is quite a bit less trivial than "there are more functions than there are programs to evaluate them".

Re: What does “Undecidable” mean, anyway

#127

Post by SkyBelow »

pdpi wrote: post #119
mreid wrote: post #65

This is a really nice explanation of decidability. One extra thing it might be worth mentioning is that there are many more functions `f : string -> boolean` then there are programs that implement those functions. When I first encountered this topic I had trouble intuitively understanding how there could not exist an `IS_HALTING` function when it is also just a function that takes in a string (representing a program…

> The result becomes less weird when you realize that that almost all functions from string -> boolean are not expressible as a program. I think this is one of those cases where a maths background makes computer science much easier. It only takes enough calculus to get you to entry level differential equations before you’re confronted with the fact that most functions ℝ → ℝ aren’t elementary functions (or admit any c…

Isn't this related to why the busy beaver is the fastest growing program, given that at some N states it would be able to emulate any closed form function and then at some greater number N + M states be able to use that function in more complex functions (as a lower bounds, the actual busy beaver of N + M states given size would likely be an even larger output than the same sized Turing machine emulating whichever fast growing function is used for comparison)?

Re: What does “Undecidable” mean, anyway

#128

Post by Ukv »

bubblyworld wrote: post #124
Ukv wrote: post #121

Earlier quoted context omitted.

> Yes, if you ask the same question with a fixed (finite) memory restriction on everything, the answer is uninteresting. To me, this is... uninteresting. It tells you nothing about the underlying logical structure of your problem, which is what mathematicians are really trying to get at! > (first and foremost Turing machines are a tool for analysing problems mathematically, not a model of your laptop) I think what ma…

That's fair, I've run into a lot of misconceptions like that before. And probably believed some of them at earlier points in my life =P (Roger Penrose himself makes a version of that claim in "the Emperor's New Mind", so we're in good company...) About the bcrypt thing... yeah, so one way you can do it is write a program that generates all possible keys starting with the letter 'a', and tests them. Then you run your…

> About the bcrypt thing... yeah, so one way you can do it is write a program that generates all possible keys starting with the letter 'a', and tests them. Then you run your halting oracle on that, and if it returns true you know the first letter of the key is 'a'.

And you really can do that. For actual computers we have cycle detection algorithms that can tell you definitively if your program will halt or not.

Determining whether the program halts can still be complex or slow, which is the case here, but the halting problem does not make it undecidable (because it doesn't apply to real computers) nor place any lower bound on that complexity (nothing preventing a more advanced halt detector from finding better shortcuts).

Re: What does “Undecidable” mean, anyway

#129

Post by dooglius »

yusina wrote: post #123
dooglius wrote: post #118

Earlier quoted context omitted.

What do you mean "space in your decider"? My decider takes finite but unbounded memory, same as the machine it's deciding.

Ok, if that's the class of systems we are talking about, then the system that your decider wants to check does not need to attain the same state twice. It may or may not terminate, and your decider may never know. You can't have it both ways. Keep in mind that the input can be as adversarial as it wants and knows, including having full knowledge of what your decider is trying to do.

What class of system are you talking about where the claim is false? Can you express your statement/definitions rigorously? A system that enters the same state twice will never halt, we know it will keep cycling through the same list of states over and over again.

Re: What does “Undecidable” mean, anyway

#130

Post by skydhash »

dooglius wrote: post #116
andoando wrote: post #70

Earlier quoted context omitted.

I'm not sure what were arguing to be honest. You definitely don't need to understand Turing machines to understand how computers work, and certainly not how to do programming. But as far as understanding computer science, computational theory, etc certainly you'd want to study Turing machines and lambda calculus. If you were say, writing a programming language, it would be nice to understand the fundamentals. I mean,…

Suppose I were to teach theoretical CS using only RAM models of computation, with no reference to Turing Machine tapes. Would there be any downside to doing this, pedagogically? (Other than, of course, the backward compatibility concern of students being able to engage with existing literature, which is the main reason this isn't done I think)

You could do this with the C abstract machine. because it’s Turing complete. But we go with TM because they’re the most basic. Anything else is an abstraction. So you can stop at any level you like.
Post reply on HN