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

On 9/26/2013 2:12 AM, Bruno Marchal wrote:
which for a logician are more demanding than the reals, as the first order theory of the real is NOT Turing complete

Bruno, 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 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.

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.

Reply via email to