3 ms·
If you can solve the halting problem, then you can apply it to a solution checker that works by enumerating potential solutions and halting when it finds one.
by munch117 5y ago
If you can solve the halting problem, then you can apply it to a solution checker that works by enumerating potential solutions and halting when it finds one. Therefore, if you've solved the halting problem then you've also solved the Entscheidungsproblem, and since the latter is impossible, it follows that the premise of having a solution to the halting problem is false.
Yes, that does seems trivial to me. Although maybe that just shows the brilliance of the people who came up with it and made it sound simple.
Did Turing's original machine not have a halting state? That does change things. You can hardly express the halting problem if you don't have the concept of halting.
- qiskit 5y agoUsing your logic, Alonzo Church should be credited with the Turing machine and the halting problem since he solved Hilbert's Entscheidungsproblem before Turing did. If everything follows trivially from an answer to the same question, then Turing's solution follows trivially from Church. Not sure why you are fixated on the Entscheidungsproblem. Turing's claim to fame isn't the entscheidungsproblem. If it were, nobody would know who Turing is because Church already solved the entscheidungsproblem. His contribution are the theoretical concept of Turing machines ( universal turing machines especially ) and computable numbers. > Did Turing's original machine not have a halting state? Are you asking me? > You can hardly express the halting problem if you don't have the concept of halting. He did have a concept of halting. He called them circular/unsatisfactory. Did you even read his paper?
- munch117 5y agoI did read the paper, 30 years ago.