Mientras tratando de limpiar Wikipedia, la prueba de dibujo de Tennenbaum del teorema (no es computable no-modelo estándar de la Aritmética de Peano), la siguiente estrategia ocurrido a mí. Ya que parece ser más simple que la de los presentados en Kaye papel de 2006 -- en particular, se evita cualquier referencia a la recepción de principio, creo que debo haber pasado por alto alguna sutileza. Pero, ¿qué?
Seleccione dos recursivamente enumerable, pero de forma recursiva inseparable subconjuntos disjuntos $A, B$$\mathbb N$. Por lo concreto, supongamos $A$ es el índice de máquinas de Turing que detener en un número impar de pasos en una cinta vacía y $B$ es el índice de máquinas de Turing que detener en un número par de pasos.
Entonces existen funciones recursivas primitivas $f$ $g$ tal que $A$ es el rango de $f$ $B$ es el rango de $g$. Por otra parte, al menos con la opción anterior, podemos optar $f$ $g$ tales que PA demuestra que los rangos de $f$ $g$ son disjuntas.
Ahora, dada una contables no estándar del modelo de $M$ de PA, elegir cualquier elemento no estándar $c\in M$, y vamos a $$ C = \{ n\in\mathbb N \mid M\vDash {\exists x<c: f(x)=\bar n} \}$$ A continuación, $A\subseteq C \subseteq \mathbb N\setminus B$ porque primitivas de funciones recursivas dar los resultados usuales para los elementos de serie, y la gama completa de $f$ $M$ es disjunta de la gama de $g$, por lo que, en particular, de $B$. Por lo tanto, $C$ no es recursiva.
Sin embargo, todos los de $C$ es codificada por un único elemento de $M$, es decir, $a=\prod_{x<c} p_{f(x)}$ donde $p_n$ $n$th prime. PA demuestra que este producto debe existir dentro de$M$, incluso a pesar de que es un "infinito" producto cuando nos ven desde el exterior.
Ahora, exactamente como en la Kaye papel (Threorem 2.8), si además de en $M$ eran computables, podríamos decidir $C$ (dividiendo $a$ $p_n$ con el resto de $M$ por búsqueda de fuerza bruta). Pero $C$ no es recursiva, por lo $M$'s además no es computable.
Estoy suponiendo que esto no funciona, porque Kaye, un experto en el tema, recurre a una manera más indirecta a discutir (parte superior de la página 9) que "Tennenbaum-tipo de resultados puede ser probado por otros medios de recepción". Pero ¿dónde está la brecha?
