4 ms·

Slight tangent, but it seems to me that humans are not bounded by the halting problem like computers are. In other words, given a general algorithm to determine

by umvi 7y ago

Slight tangent, but it seems to me that humans are not bounded by the halting problem like computers are. In other words, given a general algorithm to determine whether a program halts, I can always write a program that fools the algorithm. But I can't write a program that fools my brain. Ergo, human brains are not simply biological Turing machines like everyone seems to think?

adt2bt 7y ago
Ever stare at a loading screen unsure if Windows is actually updating before?
- umvi 7y ago
  That's the not halting problem. The halting problem is whether or not you can make an algorithm that determines whether a program will halt given the source code and inputs.
artemisyna 7y ago
I think that’s more of a matter that human lifespan is finite while the halting problem proof for Turing machines is across every single program. (Which is to say... humans aren’t more powerful — it’s that we’re so limited, we will never reach the domain for which the halting problem is relevant.)
- umvi 7y ago
  No, the problem is that I can design programs that fool any general algorithm A you produce. Even small programs. You can't fool my brain though for the same programs. Therefore my brain transcends general algorithms.
Zalastax 7y ago
A pretty simple program that fools your brain is one testing the Collatz conjecture: https://cs.stackexchange.com/a/44875 https://cs.stackexchange.com/a/44875 Or did you mean something else?
- umvi 7y ago
  That seems kind of bogus because you've just disguised an unsolved math problem as a computer program. It's like me making a program like this: if fermats_last_theorem_holds(x,y,z): halt() else: infinite_loop() Will this program halt for all possible input integers > 2? It may be able to "trick my brain" but only because I don't have a PhD in mathematics. Obviously no general algorithm can solve this, or else said general algorithm would easily be able to solve all unanswered questions in mathematics, physics, etc. Yet, human mathematicians are able to determine whether my program above halts, even if a general algorithm can't.
  - Strilanc 7y ago
    > you've just disguised an unsolved math problem as a computer program But that's the point! The halting problem hides inside of it all of the complexity of math, including the dark tricky self-referential corners. Saying that you can solve the halting problem is tantamount to saying you've solved Godel incompleteness. If you applied the halting proof diagonalization step to yourself (modeled as a machine built of out physics) you would find that it spit out something very complicated that ultimately amounted to a program equivalent of a statement of the form "The physics machine that I am cannot prove this statement". If you proved the statement then that would disprove it, which is the core of the problem.
gopiandcode 7y ago
Have you ever written a program that incorrectly looped forever? or one that deadlocked? or had any such other liveness bugs? I can't speak for you, but I certainly have, and, if the questions on stackoverflow are to be considered representative of typical humans, then it seems most other programmers have also done this at some point in their lives. In general, human answers to halting problems have no guarantees of soundness or completeness, and can't be guaranteed to be correct unless presented as some kind of proof in some kind of logic. Then, if a human can use some logic system to guarantee that a particular program halts, then a turing machine could also trivially solve this problem, by simply enumerating and verifying the possible proofs of program in the logic system. This proof strategy has further benefits beyond ad-hoc human reasoning, in that it is guaranteed to eventually find the proof if it exists.
codebje 7y ago
The halting problem is that there is no algorithm possible that can answer, for all programs and all inputs, whether that program with that input will halt. Here is my program: def fool(input): while input: pass The input given to the program is your answer as to whether it halts given that input. That's the gist of the proof that the halting problem is unsolvable. Whatever the algorithm or method is used to answer the problem, you can take that method and "embed" it into the program to be verified, and invert the answer. The halting program doesn't say you can't answer for many or even most programs and inputs, it just says there'll be at least one counter-example.
- thehappypm 7y ago
  That's not really how it works, though. You could imagine writing an AI program that can read this program, figure out that it halts on the truthiness of the input, and handles this case flawlessly. The real proof is a bit of a head scratcher. Imagine we created such a function, doesHalt, that can read any program's source code and always figure out if the program will halt. This program can solve the halting problem -- it always produces a solution, either a True or a False. Feed it your fool program, it can always solve it, for any arbitrary input. So what happens if we run create this little head scratcher function, that takes no input: def headScratcher(): if doesHalt(headScratcher): while 1: pass This program halts if doesHalt() says it doesn't halt, and does not halt if doesHalt says it does halt. These are both contradictions -- proving that such a doesHalt function cannot actually exist.

by umvi 7y ago

adt2bt 7y ago

Ever stare at a loading screen unsure if Windows is actually updating before?

umvi 7y ago
That's the not halting problem. The halting problem is whether or not you can make an algorithm that determines whether a program will halt given the source code and inputs.

artemisyna 7y ago

I think that’s more of a matter that human lifespan is finite while the halting problem proof for Turing machines is across every single program. (Which is to say... humans aren’t more powerful — it’s that we’re so limited, we will never reach the domain for which the halting problem is relevant.)

umvi 7y ago
No, the problem is that I can design programs that fool any general algorithm A you produce. Even small programs. You can't fool my brain though for the same programs. Therefore my brain transcends general algorithms.

Zalastax 7y ago

A pretty simple program that fools your brain is one testing the Collatz conjecture: https://cs.stackexchange.com/a/44875 https://cs.stackexchange.com/a/44875 Or did you mean something else?

umvi 7y ago
That seems kind of bogus because you've just disguised an unsolved math problem as a computer program. It's like me making a program like this: if fermats_last_theorem_holds(x,y,z): halt() else: infinite_loop() Will this program halt for all possible input integers > 2? It may be able to "trick my brain" but only because I don't have a PhD in mathematics. Obviously no general algorithm can solve this, or else said general algorithm would easily be able to solve all unanswered questions in mathematics, physics, etc. Yet, human mathematicians are able to determine whether my program above halts, even if a general algorithm can't.
- Strilanc 7y ago
  > you've just disguised an unsolved math problem as a computer program But that's the point! The halting problem hides inside of it all of the complexity of math, including the dark tricky self-referential corners. Saying that you can solve the halting problem is tantamount to saying you've solved Godel incompleteness. If you applied the halting proof diagonalization step to yourself (modeled as a machine built of out physics) you would find that it spit out something very complicated that ultimately amounted to a program equivalent of a statement of the form "The physics machine that I am cannot prove this statement". If you proved the statement then that would disprove it, which is the core of the problem.

gopiandcode 7y ago

Have you ever written a program that incorrectly looped forever? or one that deadlocked? or had any such other liveness bugs? I can't speak for you, but I certainly have, and, if the questions on stackoverflow are to be considered representative of typical humans, then it seems most other programmers have also done this at some point in their lives. In general, human answers to halting problems have no guarantees of soundness or completeness, and can't be guaranteed to be correct unless presented as some kind of proof in some kind of logic. Then, if a human can use some logic system to guarantee that a particular program halts, then a turing machine could also trivially solve this problem, by simply enumerating and verifying the possible proofs of program in the logic system. This proof strategy has further benefits beyond ad-hoc human reasoning, in that it is guaranteed to eventually find the proof if it exists.

codebje 7y ago

The halting problem is that there is no algorithm possible that can answer, for all programs and all inputs, whether that program with that input will halt. Here is my program: def fool(input): while input: pass The input given to the program is your answer as to whether it halts given that input. That's the gist of the proof that the halting problem is unsolvable. Whatever the algorithm or method is used to answer the problem, you can take that method and "embed" it into the program to be verified, and invert the answer. The halting program doesn't say you can't answer for many or even most programs and inputs, it just says there'll be at least one counter-example.

thehappypm 7y ago
That's not really how it works, though. You could imagine writing an AI program that can read this program, figure out that it halts on the truthiness of the input, and handles this case flawlessly. The real proof is a bit of a head scratcher. Imagine we created such a function, doesHalt, that can read any program's source code and always figure out if the program will halt. This program can solve the halting problem -- it always produces a solution, either a True or a False. Feed it your fool program, it can always solve it, for any arbitrary input. So what happens if we run create this little head scratcher function, that takes no input: def headScratcher(): if doesHalt(headScratcher): while 1: pass This program halts if doesHalt() says it doesn't halt, and does not halt if doesHalt says it does halt. These are both contradictions -- proving that such a doesHalt function cannot actually exist.