As the question says, if I input on the tape of a Turing complete machine a program that solves the halting problem with the correct inputs the program will never end its execution regardless of memory and time. Isn't the halting problem a computational problem that can't be executed by a Turing complete machine so that it's halts sometime?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
The halting problem is the problem of deciding whether a given Turing machine halts on a given input or not.
This problem is undecidable, meaning that no program running on a Turing machine can solve this problem for all possible inputs. Hence, your assumption that such a program exists is wrong.
answered Nov 6, 2019 at 22:26
-
$\begingroup$ What I meant is that I can give a program H(x) that supposedly solves the halting problem and we do:
P(x) = run H(x) If H(x) halts then loop forever else haltthis program will loop forever regardless of time or memory so this is a computational problem that can´t be solve by a Turing Machine regardless of memory and time as I said before $\endgroup$ Nov 7, 2019 at 21:40 -
1$\begingroup$ Yes and this problem is not supposed to be solvable in bounded time or resources that is why we call it undecidable. You can always design such programs for all problems. The interesting case is the decidable problems where you can build a Turing machin that halts on each input and accepts if it is a yes instance $\endgroup$ Nov 7, 2019 at 22:15