I guess my objection is that your task is too obviously impossible. If I tell you that I can color any page in any coloring book, and you give me an infinite coloring book, I won’t be able to finish, even though I know how to color. Similarly, if we have a decoder that can interpret infinitely many finite bit strings, it can be stumped by an infinite one, by virtue of its being infinite.
Agreed. There’s an even easier way to confound the machine, really: when it asks you for the bit string, walk away from the computer!
Note that there is no way to feed infinite input to a Turing machine. The halting problem isn’t demonstrated by a program of infinite length. It’s demonstrated by a finite program that resists static analysis. The analogous integer is not the one represented by an infinite bit stream, but it might be something like the Berry number.
The thing is, not just any infinite input stream will do. It has to at all times look properly encoded to the decoder. You’re allowed to come up with any encoding scheme that you like, so what you can try to do is to come up with an encoding scheme that an infinite input stream must violate in finite time. This turns out to be impossible, and the proof is fairly easy, but it is not as obvious as your description characterizes it here.
Granted. But even so, the primary problem is that the input is infinite: we can deal with any finite input stream, no problem.
ETA: Also, the obvious way to approach the problem is to have a terminator character (this is how the unary representation works, for instance). In that case, what this result says is “if your decoder expects a terminator, then if you feed it an infinite string without a terminator, it’ll get stuck.” This seems obvious.
I guess my objection is that your task is too obviously impossible. If I tell you that I can color any page in any coloring book, and you give me an infinite coloring book, I won’t be able to finish, even though I know how to color. Similarly, if we have a decoder that can interpret infinitely many finite bit strings, it can be stumped by an infinite one, by virtue of its being infinite.
Agreed. There’s an even easier way to confound the machine, really: when it asks you for the bit string, walk away from the computer!
Note that there is no way to feed infinite input to a Turing machine. The halting problem isn’t demonstrated by a program of infinite length. It’s demonstrated by a finite program that resists static analysis. The analogous integer is not the one represented by an infinite bit stream, but it might be something like the Berry number.
The thing is, not just any infinite input stream will do. It has to at all times look properly encoded to the decoder. You’re allowed to come up with any encoding scheme that you like, so what you can try to do is to come up with an encoding scheme that an infinite input stream must violate in finite time. This turns out to be impossible, and the proof is fairly easy, but it is not as obvious as your description characterizes it here.
Granted. But even so, the primary problem is that the input is infinite: we can deal with any finite input stream, no problem.
ETA: Also, the obvious way to approach the problem is to have a terminator character (this is how the unary representation works, for instance). In that case, what this result says is “if your decoder expects a terminator, then if you feed it an infinite string without a terminator, it’ll get stuck.” This seems obvious.
It is very nearly as obvious as Misha’s description characterizes… and Misha’s analogy could be extended to ‘color encoding schemes’ in the same way.