Yuri Matijasevich, Steklov Inst. of Math., Saint-Petersbourg et LRI

Modelling primitive recursive functions by exponential diophantine equations

It is known since 1970 that every partial recursive function $f$ has a representation of the form $$y=f(x_1,\ldots,x_m)\qquad\hbox{iff}\qquad\exists z_1\cdots z_n ~~y=P(x_1,\ldots,x_m,z_1,\ldots,z_n)$$ where $P$ is a polynomial. So far two essentially different techniques were known for constructing such a $P$ for given $f$. One technique was based on arithmetization of $f$ and further elimination of universal quantifiers; the other one proceeded by constructing Turing or register machine calculating $f$, and further simulating the machine by Diophantine equations. The talk will be about a direct technique new recently discovered by the speaker for constructing such a $P$. Actually, a detailed proof will be given for a bit weaker result (known since 1961 due to M.~Davis, H.~Putnam and J.~Robinson) with $f$ being primitive recursive and $P$ being an exponential polynomial.