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 [email protected].
To post to this group, send email to [email protected].
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 [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/groups/opt_out.
