# Re: Why AI is impossible

```
On 17 Aug 2012, at 21:14, meekerdb wrote:```
```
```
```On 8/17/2012 2:43 AM, Bruno Marchal wrote:
```
```

On 16 Aug 2012, at 22:11, meekerdb wrote:
```
```

```
```
```
Are there any explicitly known arithmetic propositions which must be true or false under Peanao's axioms, but which are known to be unprovable? If we construct a Godel sentence, which corresponds to "This sentence is unprovable.", in Godel encoding it must be an arithmetic proposition. I'm just curious as to what such an arithmetic proposition looks like.
```

I forgot to mentioned also the famous Goodstein sequences:

http://en.wikipedia.org/wiki/Goodstein_theorem

```
Goodstein sequences are sequences of numbers which always converge to zero, but PA cannot prove this, although it can be proved in second order arithmetic.
```
```
I'd say they are not part of arithmetic, since they are generated by substituting one number for another - not an arithmetic operation.
```
```
Come on. Arithmetic is Turing universal. You can program substitution with only "E", "s", "0", "+" and "*". It is long and tedious, and not simple prove, but has been done by Matiyasevich (or just Gödel if you add the symbol "A", eliminated by Davis, Robinson and Matiyasevich.
```

```
So I find it hard to see "Goodstein sequences terminate in zero." as a proposition of arithmetic or number theory.
```
It is.

```
```It seems that they depend on positional notation.
```
```
```
You can program positional notations with the arithmetical little language sketched above. If you want I can give more detail, but it is obviously rather technical, and very long. You really need the fundamental theorem of arithmetic, the chinese rest lemma, the Gödel beta function, etc. I can give a shorter sketchy description, as I intent to do on the FOAR list soon or later. I can sent the relevant post here on that occasion.
```
Bruno

```
```
```
You can google also on "hercule hydra undecidable" to find a game, which has a winning strategy, but again this is not provable in PA.
```
```
But "machine theologians" are not so much interested in those extensional undecidable sentences (in PA), as they embrace the intensional interpretation of the undecidable sentence, like CON(t), (<>t).
```
Bruno

```
```
Brent

```
```
```
If Goldbach is un-provable we will never know it's un-provable, we know that such statements exist, a infinite number of them, but we don't know what they are. A billion years from now, whatever hyper intelligent entities we will have evolved into will still be deep in thought looking, unsuccessfully, for a proof that Goldbach is correct and still be grinding away at numbers looking, unsuccessfully, for a counterexample to prove it wrong.
```
John K Clark

--
```
You received this message because you are subscribed to the Google Groups "Everything List" group. To post to this group, send email to everything-list@googlegroups.com . To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/everything-list?hl=en .
```

--
```
You received this message because you are subscribed to the Google Groups "Everything List" group. To post to this group, send email to everything-list@googlegroups.com . To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/everything-list?hl=en .
```
http://iridia.ulb.ac.be/~marchal/

--
```
You received this message because you are subscribed to the Google Groups "Everything List" group. To post to this group, send email to everything- l...@googlegroups.com. To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/everything-list?hl=en .
```

--
```
You received this message because you are subscribed to the Google Groups "Everything List" group.
```To post to this group, send email to everything-list@googlegroups.com.
```
To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/everything-list?hl=en .
```
http://iridia.ulb.ac.be/~marchal/

--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to