On 15 Feb 2014, at 18:20, meekerdb wrote:
On 2/15/2014 1:38 AM, Bruno Marchal wrote:
You might keep in mind that astonishing truth (deducible from
Matiyasevitch):
- The polynomial on the reals are not Turing universal (you cannot
simulate an exponential with such polynomials)
- the polynomial on the integers are Turing universal, you can
simulate exponential, and indeed all Turing machine with them. You
can simulate the function sending the integers x on
x^(x^(x^(x^...))) x times with a integers polynomial of dgree
four!, but you cannot with any polynomials on the reals.
That is astonishing. Where can I read a proof (without having to
learn too much background)?
I would recommend the book by Matiyasevich(*). It is very good. You
don't need a background (except "17 is prime", of course).
But you will need to do some work, of course. It took 70 years to
Davis, Putnam, Robinson and Matiyasevich to prove this. The so called
DPRM theorem. Many logicians thought they would not succeed.
Bruno
(*) You will find many accounts when googling on "matiyasevich
hilbert's tenth problem".
+ "amazon.com" for the references.
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.
