On Sat, Feb 15, 2014 at 09:20:43AM -0800, 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)? >
You could try your luck with Wikipedia: http://en.wikipedia.org/wiki/Diophantine_equations http://en.wikipedia.org/wiki/Matiyasevich's_theorem#Matiyasevich.27s_theorem Cheers -- ---------------------------------------------------------------------------- Prof Russell Standish Phone 0425 253119 (mobile) Principal, High Performance Coders Visiting Professor of Mathematics [email protected] University of New South Wales http://www.hpcoders.com.au ---------------------------------------------------------------------------- -- 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.
