3 ms·
Therefore, there are some Turing machines which can't be proven to halt or run forever in any given consistent system that can be computed. I feel like it'
by andrewflnr 10y ago
Therefore, there are some Turing machines which can't be
proven to halt or run forever in any given consistent
system that can be computed.
I feel like it's worth clarifying the quantifiers here. For all consistent systems, there exist Turing machines whose halting behavior can't be proven in that system. Unless I have some disastrous misunderstanding...
- ikeboy 10y agoWell a consistent system that can't be computed can prove things about all Turing machines. E.g. ZFC plus an infinite set of axioms of the sort "machine X halts" for all machines that halt. We can't compute all the axioms, but the system is perfectly consistent. We could compute the axioms if we had a halting Oracle. It wouldn't be able to prove the halting behavior of some Turing machines that have halting oracles attached, though.