Hay muchos ejemplos. Muy rápidamente se complican, por ejemplo, creo que el Teorema de la base baja puede no ser pedagógicamente apropiado - pero sí hay ejemplos.
En particular, la prueba más fácil (en mi opinión) de que hay grados de Turing incomparables es un argumento de forzamiento. En concreto, se demuestra que para cualquier par de cadenas binarias finitas $\sigma,\tau$ y cualquier $e\in\mathbb{N}$ Hay extensiones $\sigma'\supseteq\sigma$ y $\tau'\supseteq\tau$ tal que no hay secuencias binarias infinitas $f\supseteq\sigma', g\supseteq\tau'$ con $\Phi_e^f=g$ . Esto nos permite construir inductivamente un par de secuencias binarias infinitas que son incomparables de Turing, diagonalizando contra posibles reducciones (la frase "extensiones finitas" se utiliza a menudo aquí). El teorema de Friedberg-Muchnik mejora esto haciendo que los grados sean c.e. al pasar del forzamiento "puro" al escenario más complicado de los argumentos de prioridad; véase esta vieja pregunta .
Ahora bien, usted ha sacado a relucir la cuestión de lo "genérico" frente a lo "genérico". para alguna colección específica de conjuntos densos " (por ejemplo, las r.e.). Existe una rica jerarquía de "niveles de genericidad" en la teoría de la computabilidad, y éste es también el caso de las nociones de forzamiento no-Cohen (desgraciadamente, la palabra "genérico" en la teoría de la computabilidad suele significar genérico-Cohen). En particular, examinando el argumento anterior vemos lo siguiente:
-
Los conjuntos densos que queremos conocer son los de la forma "Ninguna extensión infinita de la cadena de la izquierda (resp. de la derecha) computa cualquier extensión infinita de la cadena de la derecha (resp. de la izquierda) mediante $\Phi_e$ ."
-
A primera vista, cada una de ellas es bastante complicada, a saber, $\Pi^1_1$ . Aún así, sólo hay un número contable de conjuntos densos de este tipo, por lo que podemos cumplir trivialmente con todos ellos.
-
... ¡Pero también podríamos querer ver lo simple que podemos ser! Hay dos formas en las que un cálculo puede "fallar": puede cometer un error, o puede no dar ninguna respuesta. Esto nos permite redefinir los conjuntos densos que nos interesan: "O bien ya hay algún $n$ tal que $\Phi_e^{left}(n)$ se detiene, $right(n)$ se define, y $\Phi_e^{left}(n)\not=right(n)$ O hay algo de $n$ tal que ninguna extensión de la cadena de la izquierda hace $\Phi_e^?(n)$ detener". (Y del mismo modo, intercambiando "izquierda" y "derecha").
-
Se puede comprobar fácilmente que esta definición es $\Sigma^0_2$ . Así que tenemos:
Si $x, y\in 2^{\omega}$ son mutuamente $\Sigma^0_2$ -Cohen genérico - es decir, si el conjunto $\{(\sigma,\tau)\in 2^{<\omega}\times 2^{<\omega}: \sigma\prec x, \tau\prec y\}$ es un filtro que cumple con cada $\Sigma^0_2$ subconjunto denso de $2^{<\omega}\times 2^{<\omega}$ - entonces $x$ y $y$ son incomparables de Turing.
He aquí otro ejemplo. No estoy seguro de que esto encaje en el proyecto -la prueba es bastante complicada si uno no se ha sentido ya cómodo con el forzamiento en la teoría de la computabilidad-, pero el forzamiento en sí es sencillo, la pregunta es fácil de enunciar (aunque la respuesta es un poco complicada), y toda la situación es bastante interesante.
Digamos que queremos construir una función de rápido crecimiento $\omega\rightarrow\omega$ . Hay un forzamiento natural que salta a la mente (hay muchas variaciones de esta idea) :
-
Las condiciones son pares $(p, f)$ con $p$ un mapa desde algún subconjunto finito de $\omega$ a $\omega$ y $f:\omega\rightarrow\omega$ es total con $p\subseteq f$ .
-
La ordenación viene dada por $(p, f)\le (q, g)$ (recuerde, " $\le$ " significa "es más fuerte que") si:
Básicamente, lo que ocurre aquí es lo siguiente. Estamos tratando de construir una función $\omega\rightarrow\omega$ . En una condición $(p, f)$ El $p$ -parte es la cantidad de la función que hemos construido hasta ahora, y la $f$ parte es una "promesa" de que a partir de ahora la función que estamos construyendo crecerá al menos tan rápido como $f$ .
Esto se llama Hechler forzando . No es el único forzamiento que añade una función de crecimiento rápido, por supuesto, pero es en mi opinión el más natural (y tiene algunas buenas propiedades de universalidad en teoría de conjuntos - por ejemplo, Truss demostró que si $V[d]$ es una extensión de forzamiento del modelo de suelo $V$ donde $d:\omega\rightarrow\omega$ domina todas las funciones de $V$ y $c\in\omega^\omega$ es el genérico de Cohen sobre $V[d]$ entonces $d+c$ es Hechler genérico sobre $V$ ) .
Ahora, una clase importante de preguntas en la teoría de la computabilidad son de la forma:
Supongamos que puedo calcular un real con una determinada propiedad. ¿Cuáles son las específico reales que soy garantizado para poder computar?
Por ejemplo, no es difícil (pensando en el argumento anterior) mostrar que dos reales genéricos de Cohen suficientemente mutuos no computan nada en común además de los conjuntos computables (forman un "par mínimo"), por lo que no hay reales específicos que "siendo suficientemente genéricos de Cohen" me permitan computar.
Una pregunta particularmente natural de esta forma, formulada en el contrapositivo, es:
Supongamos que $x$ es calculable a partir de cualquier función de crecimiento suficientemente rápido, es decir, existe alguna $f:\omega\rightarrow\omega$ de manera que cualquier $g$ dominante $f$ calcula $x$ . ¿Qué sabemos sobre $x$ ?
Resulta que el conjunto de tales reales tiene una caracterización muy acertada:
Teorema . Un verdadero $x$ es calculable a partir de cualquier función de crecimiento suficientemente rápido si es hiperaritmética .
Los conjuntos hiperaritméticos son esencialmente aquellos que se pueden calcular tomando repetidas Saltos de Turing - posiblemente infinitos saltos, pero sólo "computablemente muchos". (También hay muchas otras caracterizaciones.) Definir esto con precisión es complicado, pero no es demasiado difícil $(i)$ demuestran que "el $\omega$ el salto de $0$ "tiene una definición obvia y $(ii)$ argumentar que las cosas se ponen muy raras si tratamos de tomar la $\alpha$ el salto de $0$ para un ordinal contable realmente complicado $\alpha$ (es decir, cualquiera que no tenga una copia computable).
La demostración del teorema anterior -debido a Solovay si no recuerdo mal- es bastante bonita. Demostrar que todo real hiperaritmético es computable a partir de una función de crecimiento suficientemente rápido es una prueba por inducción transfinita, utilizando una noción generalizada de las funciones de Busy Beaver. La dirección interesante es la inversa, e implica un análisis inteligente de $\Vdash_{Hechler}$ . Si te interesa, La tesis de Peter Gerdes es un buen lugar para empezar a leer si no recuerdo mal.
