On 26 Sep 2013, at 19:41, meekerdb wrote:

## Advertising

On 9/26/2013 2:12 AM, Bruno Marchal wrote:which for a logician are more demanding than the reals, as thefirst order theory of the real is NOT Turing completeBruno, could point to a pedagogical reference on that?

`i deduce it from a Theorem by Tarski which shows that the first order`

`theory of addition and multiplication on the real is decidable. Any`

`polynomial equation, for example, can be solved by Sturm-Liouville`

`method, when Diophantine polynomial can be Turing universal.`

`Think about x^n+y^n = z^n. There are trivially solutions for all n,`

`and the theory is not complex. The same equation on the natural`

`numbers has many non trivial solutions for n = 2 (already known 6000`

`BC, apparently), and it took 300 years, and quite advanced`

`mathematics, to show that there in no such non trivial solutions for n`

`bigger than 2.`

`Note that if you add a trigonometrical real function, you get turing`

`universality, as you can define the natural numbers by pi-scaling zero`

`of sinus, for example. Waves is how real numbers invoke the natural`

`numbers!`

`I am not sure about the reals + addition + multiplication +`

`exponentiation, but I bet it is not yet Turing emulable.`

`But on the complex numbers, reals + addition + multiplication +`

`exponentiation, you get back Turing universality, given that complex`

`exponential can simulate trigonometrical functions.`

`I will try to look for some reference, but beside Tarski's paper, and`

`technical textbook I don't see simple pedagogical references.`

Bruno

thnx, Brent --You received this message because you are subscribed to the GoogleGroups "Everything List" group.To unsubscribe from this group and stop receiving emails from it,send an email to everything-list+unsubscr...@googlegroups.com.To post to this group, send email to everything-list@googlegroups.com. Visit this group at http://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/groups/opt_out.

http://iridia.ulb.ac.be/~marchal/ -- You received this message because you are subscribed to the Google Groups "Everything List" group. To unsubscribe from this group and stop receiving emails from it, send an email to everything-list+unsubscr...@googlegroups.com. To post to this group, send email to everything-list@googlegroups.com. Visit this group at http://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/groups/opt_out.