¿Cómo el uso de las máquinas Oracle Turing no conduce a contradicciones?

¿Cómo podemos asegurarnos de que continuamos haciendo declaraciones válidas y válidas sobre las clases de complejidad cuando usamos las máquinas Oracle Turing? Según mi entendimiento (basado en las definiciones dadas en los libros de texto introductorios sobre el tema) las máquinas Oracle Turing pueden determinar el estado de membresía de una cadena con respecto a un lenguaje Oracle en un solo paso de cálculo. Sin embargo, los lenguajes de oráculo que se usan con frecuencia son imposibles de resolver en tiempo constante (tome un oráculo EXPTIME-complete, por ejemplo). Para mí, esto parece "abrir la puerta" a las contradicciones y, después de todo, cualquier cosa se deriva de una contradicción.

Hay varias maneras de ver esto.

Una es que en las pruebas, la implicación es como una función, que toma como entrada una prueba de algo y genera una prueba de otra cosa.

Podemos escribir funciones que operan en valores que no tenemos.

Por ejemplo, consideremos el número de detención , que no es computable. Puedo escribir la funcion$h$

$haltingPlusOne : \{h \} \rightarrow \mathbb{N}$

$haltingPlusOne(x) = x + 1$ .

Esta función toma como entrada el número de detención y devuelve el número de detención más uno. Claramente, esta es una función bien definida: si le damos la entrada correcta, da la salida correcta. El hecho de que no podamos encontrar la entrada correcta no hace que una transformación sea menos válida.

Veo pruebas con oráculos como similares. Básicamente son funciones que dicen, dame una máquina de Turing que resuelva el problema , y daré como resultado una prueba de algún teorema.$X$

También es importante darse cuenta de que cuando decimos algo como "No hay una máquina de Turing que pueda decidir el problema de detención", es decir, no hay TM que coincida con la definición estándar de una TM que decide el problema de detención.

Básicamente, un oráculo dice "Supongamos que tenemos una TM que coincide con la definición normal, excepto que también suponemos que podemos resolver algún problema". Por lo tanto, no hay contradicción, ya que no estamos asumiendo que hay una TM normal que acepta el problema, estamos asumiendo que hay una TM especial que acepta el problema.

En una analogía muy informal, piense así. Si puedo demostrarte que ningún ser humano sin superpoderes puede volar, no hay contradicción en decir que hay un superhéroe que puede volar.

Estos oráculos son objetos puramente lógicos. No sabemos cómo construir máquinas físicas que las emulen, como podemos hacerlo con las máquinas de Turing, pero hasta donde sabemos, no hay contradicción inherente entre sus definiciones y nuestros axiomas básicos. Como objetos lógicos, estos oráculos existen. Sabemos que no son máquinas Turing estándar ni términos de cálculo Lambda ni funciones recursivas parciales. La tesis de Church-Turing dice que no hay un modelo más poderoso, pero no es un teorema, es solo una conjetura, y es demasiado informal como para probarlo.

$A$$B$$B=B^A$

Entonces, ¿cuál es el punto de usar un oracle TM? Diría que nos permite principalmente consideraciones teóricas sobre el (grado de) dureza de los problemas. El oráculo incluso puede ser indecidible. En este caso, puede definir una jerarquía completa de problemas indecidibles (grado de Turing). Por supuesto, si su oráculo es el problema de detención, no puede convertir su oracle TM en una TM tradicional.

El concepto oracle TM también es importante para definir una forma fuerte de reducciones (reducciones de Turing).

$\sf P$$\sf NP$

$w$$|w|$