¿Hay algún resultado en la teoría de la computabilidad que no se relativice?

Estaba leyendo el artículo de Andrej Bauer, Primeros pasos en la teoría sintética de la computabilidad . En la conclusión, señala que

Nuestra axiomatización tiene su límite: no puede probar ningún resultado en la teoría de computabilidad que no se relativice con los cálculos de oráculo. Esto es así porque la teoría puede interpretarse en una variante de los topos efectivos construidos a partir de funciones recursivas parciales con acceso a un oráculo.

Esto me hizo preguntarme acerca de los resultados no relativizantes en la computabilidad. Todos los resultados que conozco de la teoría de la computabilidad se relativizan a la computación con oráculos.

¿Hay resultados en la teoría de la computabilidad que no se relativizan? Es decir, ¿qué resultados son válidos para la computabilidad pero no para la computabilidad en relación con algún oráculo?

Por resultado quiero decir un teorema conocido en la teoría de la computabilidad, no una declaración inventada. Si la noción de relativización no tiene sentido para el resultado, entonces no es lo que estoy buscando.

También es interesante saber si el resultado puede expresarse en el lenguaje de la teoría de la computabilidad sintética o no.

computability relativization Anónimo
fuente

Todos conocen los resultados no relativizantes en la teoría de la complejidad como IP = PSPACE. Estoy preguntando sobre los resultados de la teoría de la computabilidad no relativizante , no los resultados de la teoría de la complejidad .

Anónimo el

@Erfan: Tus comentarios no son relevantes para la pregunta. Mi pregunta es sobre la teoría de la computabilidad, estás hablando de la teoría de la complejidad. Estoy buscando resultados no reletivizantes, el teorema de la jerarquía del tiempo se relativiza. Si tiene una pregunta sobre el teorema de la jerarquía del tiempo y la relativización, puede publicar una pregunta por separado.

Anónimo el

Cosas relevantes: la conjetura de homogeneidad formulada por H. Rogers ha sido refutada en Richard A. Shore; La conjetura de homogeneidad (1979): existe un grado de Turing

tal que

no es isomorfo a

(la estructura de los grados de Turing con orden parcial

). Ver una pregunta similar en lo.logic

a

$\mathbf{a}$

D (\geq a)

$\mathcal{D}(\geq \mathbf{a})$

D

$\mathcal{D}$

\leq_{T}

$\leq_{T}$

Marzio De Biasi

Buena pregunta :-)

Andrej Bauer

@Marzio: Interesante. " Entonces esto significa que hay una oración de primer orden en el lenguaje que solo contiene cual es cierto acerca de los grados de Turing, pero que es falso si relativiza la oración a los grados de Turing para alguna (y, por supuesto, , trabajar en los grados de Turing es equivalente a dar a todas las máquinas de Turing acceso a como un oráculo. Por lo tanto, la prueba de que es verdadero no se puede relativizar a . $\varphi$ $\leq_T$ $\geq_Tx$ $x$ $\geq_Tx$ $x$ $\varphi$ $x$ "Pero

no es realmente un resultado de computabilidad teoría, está preparada para un meta teorema.

φ

$\varphi$

Anónimo

Respuestas:

Teorema de incrustación de Higman: los grupos generados finitamente presentados computacionalmente son precisamente los subgrupos generados finitamente de grupos presentados finitamente. Además, cada grupo presentado de manera computable (incluso los generados de manera contable) es un subgrupo de un grupo presentado de manera finita.

Tenga en cuenta que esta afirmación podría relativizarse a: "Los grupos -computablemente presentados (con algún oráculo ) son precisamente los subgrupos finitamente generados de grupos finamente presentados", pero no lo es, ya que uno puede probar que para algunos no computables hay -grupos computacionalmente presentados que no se presentan computablemente. $O$ $O$ $O$ $O$

De hecho, creo que cualquier resultado no relativización de la teoría de la computabilidad debe tener algo de este sabor, como una parte del resultado o su prueba debe de alguna manera "uñas abajo" verdadera computabilidad de computabilidad con un oráculo . En este caso, es la finitud lo que determina la "computabilidad real". Tenga en cuenta que, como Scott Aaronson solicitó, este resultado es invariable para cualquiera de los modelos habituales de computación (máquina de Turing, RAM, etc.), pero no se relativiza (nuevamente, porque todos los modelos habituales de computación "real" comparten algunos "propiedad de finitud común"). $O$

Por otro lado, se podría argumentar que esto "no cuenta" para esta pregunta, ya que es más parecido a una definición de computabilidad que usa grupos que a un "resultado de la teoría de computabilidad". Por otro lado, es una definición de computabilidad que es robusta para modelar pero que no se relativiza . (En contraste con, digamos, la caracterización de Kleene de las funciones computables que se relativiza fácilmente, simplemente agregando la función característica de su oráculo al conjunto generador de funciones. Parece que no hay una operación análoga para grupos en el contexto de Higman Embedded).

Joshua Grochow
fuente

¿Es la finitud (frente al infinito) lo que distingue su ejemplo, o la contabilidad (frente a la no rendición de cuentas)?

András Salamon

Disculpe mi ignorancia, pero ¿es uniforme el teorema de Higman? Es decir, dado un grupo presentado de manera computable, ¿podemos calcular uniformemente un grupo finito generado que lo contenga?

Andrej Bauer

Vaya, reemplaza "finitamente generado" por "finitamente presentado" en mi pregunta. Ese fue un error trivial. Lo que me pregunto es si podemos reemplazar "presentado de manera finita" con algo un poco más general.

Andrej Bauer

S A T^{O}

$SAT^O$

N P^{O}

$NP^O$

@ AndrewMorgan: De acuerdo. Creo que ese género de nudos sería un buen candidato :).

Joshua Grochow

¡Esto es algo que también me he preguntado a menudo!

Si por "resultados en la teoría de la computabilidad", quiere decir resultados que son invariables con respecto a la elección del modelo de máquina (máquinas Turing, máquinas RAM, etc.), entonces no conozco un solo ejemplo de tal resultado, y yo Definitivamente habría recordado si hubiera visto uno.

Lo más cercano que puedo sugerir a una respuesta es: creo que hay muchas preguntas interesantes en la teoría de la computabilidad que podrían depender del modelo de máquina. Por ejemplo: ¿es la función Busy Beaver, con su definición habitual en términos de máquinas de Turing, infinitamente extraña? ¿El valor de BB (20) es independiente de ZFC? Cualesquiera que sean las respuestas a estas preguntas, seguramente podrían ser diferentes para los análogos relativizados de la función BB.

Scott Aaronson
fuente

Aquí hay un ejemplo más o menos trivial: considere el problema de detención para las máquinas de Turing que están específicamente prohibidas (según la definición del modelo de computación) para acceder a un oráculo. Es indecidible en relación con ningún oráculo y con un oráculo trivial, y sin embargo, es decidible en relación con un oráculo para el problema de detención. (El problema en sí mismo no cambia en relación con un oráculo porque no puede acceder al oráculo, pero la TM (sin restricciones) que decide que el problema se vuelve más poderoso dado el oráculo).

También hay muchos otros ejemplos. Solo juega un poco con el modelo de cálculo y puedes encontrar otros resultados similares.

Philip White
fuente

Solo curiosidad: ¿qué está mal exactamente con esta respuesta? ¿Quizás los votantes negativos no creen que sea posible prohibir que una máquina Turing acceda a un oráculo y requieren una explicación más detallada de esto?

Philip White el

No parece una definición muy justa de relativización permitir que la máquina tenga un oráculo, pero luego no permitir que use el oráculo.

David Eppstein

Interesante aunque no es lo que estoy buscando. Estoy buscando un resultado conocido en la teoría de la computabilidad que no se relativice, no un argumento sobre cómo preparar ese resultado.

Anónimo

Considere la siguiente afirmación: H (problema de detención para máquinas Turing sin oráculos) no es computable. Por otro lado, H es computable en relación con un oráculo de problema de detención. Incluso si consideramos esto como una forma de relativizar el enunciado, no es interesante. Probablemente haya una forma similar de relativizar cualquier afirmación que la haga falsa. Una relativización no es solo adjuntar un oráculo en alguna parte. Una relativización es interesante cuando preserva alguna clase interesante de argumentos, por lo que si una declaración no se relativiza, sabemos que la clase de argumentos no puede probar la declaración.

Kaveh

Tomemos, por ejemplo, el método de relativización en BGS. Es interesante porque conserva argumentos simples de diagonalización para que no puedan resolver P vs. NP. Si una relativización no preserva tales argumentos, entonces probablemente no sea una forma interesante de relativizar las declaraciones. Una buena relativización debe perseverar la mayor cantidad posible de argumentos conocidos y resultados probados, cuanto menos conserva, menos interesante resulta.

Kaveh