# Misha comments on No coinductive datatype of integers - Less Wrong

4 04 May 2011 04:37PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Sort By: Best

Comment author: [deleted] 04 May 2011 05:51:52PM 9 points [-]

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.

Comment author: 04 May 2011 06:08:07PM 4 points [-]

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.

Comment author: [deleted] 04 May 2011 06:19:16PM 2 points [-]

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.

Comment author: [deleted] 04 May 2011 06:52:26PM *  3 points [-]

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.