N is encoded by N triplets of bits of the form 1??, followed by a zero.
Each triplet is of the form (1, a(N, k), b(N, k)) (with 1 ⇐ k ⇐ N), where
a(N, k) means “Turing machine number k halts in N steps or less, and it’s final state has an even number of ones on the tape”, and
b(N, k) means “Turing machine number k halts in N steps or less, and it’s final state has an odd number of ones on the tape”.
By “Turing machine number k” I mean we have an infinite list containing all possible Turing machines, sorted by description length.
So to encode N, the encoder “just” simulates the N first turing machines for N steps, and notes which of them stops.
The decoder reads his input triplet-by-triplet. When reading input k, it simulates the k first Turing machines for k steps, and checks whether the results are consistent with all that it has read in the input so far : if one of the simulated machines halts in a way not announced in the input (or if a triplet is impossible like “111”), it stops reading.
While an “infinitely confusing” input stream does exist, generating it requires solving the halting problem, which is generally considered pretty hard.
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.
OK, here’s my encoding (thanks Misha):
N is encoded by N triplets of bits of the form 1??, followed by a zero.
Each triplet is of the form (1, a(N, k), b(N, k)) (with 1 ⇐ k ⇐ N), where
a(N, k) means “Turing machine number k halts in N steps or less, and it’s final state has an even number of ones on the tape”, and
b(N, k) means “Turing machine number k halts in N steps or less, and it’s final state has an odd number of ones on the tape”.
By “Turing machine number k” I mean we have an infinite list containing all possible Turing machines, sorted by description length.
So to encode N, the encoder “just” simulates the N first turing machines for N steps, and notes which of them stops.
The decoder reads his input triplet-by-triplet. When reading input k, it simulates the k first Turing machines for k steps, and checks whether the results are consistent with all that it has read in the input so far : if one of the simulated machines halts in a way not announced in the input (or if a triplet is impossible like “111”), it stops reading.
While an “infinitely confusing” input stream does exist, generating it requires solving the halting problem, which is generally considered pretty hard.
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.