7 ms·

Godel Incompleteness Theorem and Turing Halting Problem are two faces to the same coin, I intuited. It is deeper than I thought, especially that I forgot about

Godel Incompleteness Theorem and Turing Halting Problem are two faces to the same coin, I intuited. It is deeper than I thought, especially that I forgot about the two godel's incompleteness theorems (not just one.) Scott Aaranson "popularizes" Kleene's textbook proof of Godel's theorems using Turing machines in his blog: https://www.scottaaronson.com/blog/?p=710 https://www.scottaaronson.com/blog/?p=710

scythe 8y ago
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.
- arithma 8y ago
  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.
- johncolanduoni 8y ago
  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.
  - scythe 8y ago
    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.)
    - johncolanduoni 8y ago
      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 https://en.wikipedia.org/wiki/Primitive_recursive_arithmetic [2]: https://en.wikipedia.org/wiki/Gentzen%27s_consistency_proof https://en.wikipedia.org/wiki/Gentzen%27s_consistency_proof
      - scythe 8y ago
        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.

scythe 8y ago

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.

arithma 8y ago
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.
johncolanduoni 8y ago
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.
- scythe 8y ago
  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.)
  - johncolanduoni 8y ago
    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 https://en.wikipedia.org/wiki/Primitive_recursive_arithmetic [2]: https://en.wikipedia.org/wiki/Gentzen%27s_consistency_proof https://en.wikipedia.org/wiki/Gentzen%27s_consistency_proof
    - scythe 8y ago
      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.