Hacker News Reader

Comment by scythe | Hacker News Reader

I would say that's a pretty inaccurate analogy. The incompleteness theorem can be considered a consequence of the halting problem, but not the other way around. The incompleteness theorem depends heavily on the properties of Peano arithmetic, as defined by the presence of both addition and multiplication. If you construct a set of numbers with one defined arithmetic operation (Presburger arithmetic), the incompleteness theorem does not hold and all statements can be confirmed or disconfirmed by an algorithm (albeit not efficiently). The halting problem, by contrast, is much more general, and recurs in many settings where self-reference is possible.

View on HN

Godel's completeness theorem rests on a system's ability to represent addition and multiplication, not whether they define it. Basically, it recurs where reasoning about addition and multiplication is possible within the internal theory. This is why it applies to e.g. ZF set theory, even though there is no mention of addition, multiplication, or even numbers in ZF's definition.

The role of Peano arithmetic is somewhat analogous to the role of the particular definition of a Turing machine in the proof of the halting problem: you can easily swap it out with something commensurate and get the same result.

If you can represent something, it's defined. There's no real distinction there. In weaker systems, this is not possible. ZF proves all of the Peano axioms, for example.

(Stop pretending to explain things to me that I already know.)

Then what do you mean by "depends heavily on the properties of Peano arithmetic"? There are lots of axiomatizations of arithmetic that can represent addition and multiplication that are not equiconsistent with Peano arithmetic, just like there are lots of definitions of computability that are equivalent to Turing machines (e.g. the partial recursive functions).

Also when talking about a formal theory distinguishing the definition (i.e. the axioms) and the theorems is pretty important.

EDIT: I realize now that a specific example would be helpful. Goedel's theorem can be applied to primitive recursive arithmetic[1], which is neither weaker nor stronger than Peano arithmetic. Interestingly enough PRA with a small addition (of broader transfinite induction) can actually prove Peano arithmetic[2].

[1]: https://en.wikipedia.org/wiki/Primitive_recursive_arithmetic

[2]: https://en.wikipedia.org/wiki/Gentzen%27s_consistency_proof

I mean this:

>represent addition and multiplication

It's the simplest possible explanation. Stop being a pretentious jerk. Yes, I know about primitive recursive arithmetic. I first learned about it about ten years ago.

EDIT: Wait a second. Look, I said this:

>depends heavily on the properties of Peano arithmetic, as defined by addition and multiplication

I said it right there. How could you not know this? When I said "the properties of Peano arithmetic", I meant the presence of addition and multiplication.

Let me explain it another way: Goedel's theorem is a theorem about math. Math as it was understood in the 18th century. That's what makes it interesting. The halting problem is proven with an abstract machine that was invented, mostly, to use as a basis to form analogies with other machines. So it's general by construction. (If the integers were not already interesting, Goedel's theorem would be like proving a variant of the halting problem for some weird computational structure that has no relevance to anything and is absurdly cumbersome to prove equivalent to other systems. But for the integers, the analogy is why it's interesting. Nobody expected the Goedel numbering.)

Yes, Goedel's theorem applies to all interesting versions of the integers, but it does not apply to all interesting mathematical systems. IIRC people usually cite the theory of "real closed fields" or something like that.

Just because I mention something doesn't mean I assume you don't know it. This is a public forum and although it's Hacker News I still doubt everyone has heard of primitive recursive arithmetic. You're the only one making personal statements here. Also I don't know what sort of code I'm supposed to use to make my arguments without offending you, if PRA is the example I think illuminates my point I kind of have to write its name whether you know of it or not.

> I said it right there. How could you not know this? When I said "the properties of Peano arithmetic", I meant the presence of addition and multiplication.

That's a curious definition of "heavily dependent" on the properties of Peano arithmetic (when the condition is in fact "any integer arithmetic with addition and multiplication"), and I'd argue it would be hazardously confusing to the uninitiated, but that's just semantics. Back to the original point (that the analogy is poor) I don't see how that breaks the analogy at all. Just like there are weaker arithmetics that escape Goedel's theorems (I will not mention their names since that seems to just cause issues), there are weaker models of computation that dodge the halting problem (again I'm sure you know of them, the one I'm thinking of off the top of my head rhymes with schmimative shmecursive shmunctions).

> Let me explain it another way: Goedel's theorem is a theorem about math. Math as it was understood in the 18th century. That's what makes it interesting.

I think what makes it interesting has nothing to do with the particulars of what people thought math was in the 18th century. I doubt there are any mathematicians from ancient Greece to a thousand years from now that would seriously consider using a logical system incapable of modeling addition and multiplication as a ground-level theory for the majority of mathematics. They probably would be fine with one that only killed off Peano arithmetic, just like we'd be fine with a form of computation that wasn't as limiting as PRFs but didn't happen to be susceptible to Turing's reasoning. It seems just as general by construction, and I doubt it is an accident that Goedel using something so basic.

Basically what I'm saying is just like the fact that the Church-Turing thesis has held up and all interesting forms of computation and equivalent to Turing machines, there is an implicit Addition-And-Multiplication-Are-Basic thesis that claims that systems unable to model addition and multiplication in some form are fun to visit but not to live in when you're doing mathematics.

A system so weak it can't represent arithmetic is a notable but minor edge case that doesn't really deserve to be called a logic system.

(Stop pretending people can read your mind.)

It's not an analogy. I thought so too at first, but the connection is material: In the blog it shows a proof of Godel's theorems using the Halting Problem.

Reply on news.ycombinator.com