Nice! But why do you need the parity of the output tape? Can’t you use groups of 2 bits instead of 3 and just specify whether machine number k halts within N steps? (Edit: sorry, now I see why. You could confuse the decoder by telling it that all machines halt.)
Thanks a lot! Your solution feels more intuitive to me than the one offered on MathOverflow.
Well you could, but then you’d need a way to protect against an input of only ones—i.e. “all Turing machines halt in N steps or less”. You could make a decoder that handles cases like that by checking whether a Turing machine eventually starts looping, but that makes it’s logic less straightforward, and it isn’t clear whether an infinite input couldn’t be found without solving the halting problem.
Turing machines could be classified in three categories:
H: those that halt
L: those that eventually start looping
F : those that go on forever
The halting problem is checking for membership in H, and tricking the “loop-detecting” 2-bit decoder would “only” require never returning ‘1’ for a member of L. There may be an algorithm A that returns 1 for membership in H, 0 for membership of L, and either 1 or 0 for membership of F. That algorithm wouldn’t be equivalent to a halting oracle, so it might not be undecidable, I don’t know.
So having 3 bits just makes checking simpler, since you can’t pretend to know that an algorithm will halt, you have to know something about the state it halts in too.
Nice! But why do you need the parity of the output tape? Can’t you use groups of 2 bits instead of 3 and just specify whether machine number k halts within N steps? (Edit: sorry, now I see why. You could confuse the decoder by telling it that all machines halt.)
Thanks a lot! Your solution feels more intuitive to me than the one offered on MathOverflow.
Well you could, but then you’d need a way to protect against an input of only ones—i.e. “all Turing machines halt in N steps or less”. You could make a decoder that handles cases like that by checking whether a Turing machine eventually starts looping, but that makes it’s logic less straightforward, and it isn’t clear whether an infinite input couldn’t be found without solving the halting problem.
Turing machines could be classified in three categories:
H: those that halt
L: those that eventually start looping
F : those that go on forever
The halting problem is checking for membership in H, and tricking the “loop-detecting” 2-bit decoder would “only” require never returning ‘1’ for a member of L. There may be an algorithm A that returns 1 for membership in H, 0 for membership of L, and either 1 or 0 for membership of F. That algorithm wouldn’t be equivalent to a halting oracle, so it might not be undecidable, I don’t know.
So having 3 bits just makes checking simpler, since you can’t pretend to know that an algorithm will halt, you have to know something about the state it halts in too.