News for hackers. Stuff that matters.
Re:Incompleteness ex Machina – proving Gödel's theorems in t... by neokantian on Saturday February 16, 2019 @03:01AM (#19177632)
It is not about systems that can "do" basic arithmetic but that can "talk about" basic arithmetic.

The mere execution of basic arithmetic does not require the capability of manipulating propositions of basic arithmetic.

Doing basic arithmetic:

12 * ( 5 + 8 ) --> 12 * 13 --> 156

Talking about basic arithmetic:

a * ( b + c ) == a * b + a * c

The formal language needed to describe basic arithmetic is much more powerful than a simple execution engine, such as a stack engine, that can merely carry out basic arithmetic.

For example, I must be able to express that for all natural numbers x and y, if x = y, then y = x. The result could look like this:

∀ x,y ∈ N: x=y ⇔ y=x

Hence, this language must be able to express all Dedekind-Peano's axioms as well as every proposition provable from these axioms, along with their formal proofs.

In that sense, the Gödel numbering system is the "bytecode" of quite a serious programming (or at least, specification) language. (https://en.wikipedia.org/wiki/G%C3%B6del_numbering)

Re:Incompleteness ex Machina – proving Gödel's theorems in t... by rocqua on Saturday February 16, 2019 @06:14AM (#19178139)
It should be noted that the special sauce that makes arithmetic really difficult is induction.

Induction isn't just reasoning about computation, (i.e simple equations). Instead it is reasoning about reasoning about equations (i.e. reasoning about all equations).

Specifically we have: this formula https://wikimedia.org/api/rest_v1/media/math/render/svg/67e2...

Re:Incompleteness ex Machina – proving Gödel's theorems in t... by salthound on Saturday February 16, 2019 @05:45PM (#19181422)
But it should be pointed out that induction is essentially unrelated to Gödel's theorem.

For example, Robinson Arithmetic is a finitely axiomatized theory whose axioms contain only one existential quantifier, but just like full (Peano) arithmetic, it is subject to Gödel's incompleteness theorems.

Re:Incompleteness ex Machina – proving Gödel's theorems in t... by rocqua on Sunday February 17, 2019 @03:20AM (#19183318)
Wow, I thought it was required to have second order logic for godel to apply, but this seems to be a first order logic that is still undecidable.
Re:Incompleteness ex Machina – proving Gödel's theorems in t... by ratmice on Sunday February 17, 2019 @04:22PM (#19186990)
From the other side of the fence, another thing to look at would be the decidability of presburger, and skolem arithmetic, the following paper then goes over the extensions of these, which render the result undecidable. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.21...
Re:Incompleteness ex Machina – proving Gödel's theorems in t... by imh on Sunday February 17, 2019 @02:35AM (#19183180)
Thanks for the answer! Out of curiosity what about systems we can prove able to "do" basic arithmetic, ignoring whether they can talk about it?

I'm imagining the difference between a system that can show "P(n)" for any n, rather than a system that can show "P(n) for any n."

It seems like the former must come with a proof about the system. The quantifiers "for any n" have to come somewhere. If they aren't embedded within the system, do we still end up with a system that must be able to express "This sentence is not provable?"