Those are statements that fall under what Godel proved, that is they are statements that are unprovable in ZF. So even though his statement doesn't include self-reference it can still fall under Godel's proof if his decoder is strong enough to determine what is an integer and what is not an integer. Self-referencing has nothing to do with it at all.
The best response that anyone has given to me about being wrong itself references back to the halting problem which is itself another formulation of Godel's proof.
The correct response would be to point out that deciding if something is an integer can be accomplished with just addition and the example decoder proceeds in that manner rather than using any form of multiplication to determine what is an integer and what is not. Such a system is decidable but also infinite, so the string given is indeed decidable and given infinite time the decoder will halt (at infinity which isn't part of the axiomization, which is where the problem lies). However, what throws me is "we can find such pathological inputs for any other encoding system," which to me implies a stronger system is being thought of which would cause the system to hang for some inputs as it would fall under Godel's proof.
It is very funny to me that my most downvoted comment isn't about religion but is about Godel's proof and no one gave a decent refutation of what I said.
Those are statements that fall under what Godel proved, that is they are statements that are unprovable in ZF. So even though his statement doesn't include self-reference it can still fall under Godel's proof if his decoder is strong enough to determine what is an integer and what is not an integer. Self-referencing has nothing to do with it at all.
The existence of specific undecidable statements in ZF or ZF - AC is a different sort of result than what Godel showed. That for example the continuum hypothesis is undecidable in ZFC is interesting because t...
Followup to: What's a "natural number"?
While thinking about how to make machines understand the concept of "integers", I accidentally derived a tiny little math result that I haven't seen before. Not sure if it'll be helpful to anyone, but here goes:
You're allowed to invent an arbitrary scheme for encoding integers as strings of bits. Whatever encoding you invent, I can give you an infinite input stream of bits that will make your decoder hang and never give a definite answer like "yes, this is an integer with such-and-such value" or "no, this isn't a valid encoding of any integer".
To clarify, let's work through an example. Consider an unary encoding: 0 is 0, 1 is 10, 2 is 110, 3 is 1110, etc. In this case, if we feed the decoder an infinite sequence of 1's, it will remain forever undecided as to the integer's value. The result says we can find such pathological inputs for any other encoding system, not just unary.
The proof is obvious. (If it isn't obvious to you, work it out!) But it seems to strike at the heart of the issue why we can't naively explain to computers what a "standard integer" is, what a "terminating computation" is, etc. Namely, if you try to define an integer as some observable interface (get first bit, get last bit, get CRC, etc.), then you inevitably invite some "nonstandard integers" into your system.
This idea must be already well-known and have some standard name, any pointers would be welcome!