You're looking at Less Wrong's discussion board. This includes all posts, including those that haven't been promoted to the front page yet. For more information, see About Less Wrong.

cousin_it comments on No coinductive datatype of integers - Less Wrong Discussion

4 Post author: cousin_it 04 May 2011 04:37PM

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

Comments (138)

You are viewing a single comment's thread. Show more comments above.

Comment author: cousin_it 04 May 2011 06:02:31PM 4 points [-]

The informal part is kinda sorta reminiscent, but the formal part is too simple to be analogous to Gödel's theorem.

Comment author: David_Allen 04 May 2011 06:11:17PM -2 points [-]

But is it analogous to the halting problem?

Comment author: cousin_it 04 May 2011 06:13:08PM 7 points [-]

The halting problem and Gödel's first incompleteness theorem are pretty much the same thing, and proofs of both involve self-reference. The proof of my thingy is much simpler and doesn't involve self-reference, so it seems to be unrelated.