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 hpco...@hpcoders.com.au 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 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.