Computable processes which produce any desired output in the right nonstandard model
This is a talk at the special session "Computability Theory: Pushing the Boundaries" of 2017 AMS Eastern Sectional Meeting in New York, May 6-7.
This talk will be a very condensed version of the talk with a similar title I gave last spring at MOPA Seminar in CUNY. Abstract: A total computable function will produce the same output on the standard natural numbers regardless of which model of arithmetic it is evaluated in. But a (partial) computable function can be the empty function in the standard model $\mathbb N$, while turning into a total function in some nonstandard model. I will discuss some extreme instances of this phenomena investigated recently by Woodin and Hamkins showing that there are computable processes which can produce any desired output by going to the right nonstandard model. Hamkins showed that there is a single ${\rm TM}$ program $p$ (computing the empty function in $\mathbb N$) with the property that given any function $f:\mathbb N\to \mathbb N$, there is a nonstandard model $M_f\models{\rm PA}$ so that in $M_f$ $p$ computes $f$ on the standard part. Even more drastically, Woodin has shown that there is a single index $e$ (for the empty function in $\mathbb N$), for which ${\rm PA}$ proves that $W_e$ is finite, with the property that for any finite set $s$ of natural numbers, there is a model $M_s\models{\rm PA}$ in which $W_e=s$. It follows for instance, by the MRDP theorem, that there is a single Diophantine equation $p(n,\bar x)=0$ having no solutions in $\mathbb N$, for which ${\rm PA}$ proves that there are finitely many $n$ with a solution, and given any finite set $s$, we can pass to a nonstandard model in which $p(n,\bar x)=0$ has a solution if and only if $n\in s$.Here are links to blog posts by myself and others on this topic: