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)?
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.
