Reducción de Turing - Turing reduction

En la teoría de la computabilidad , una reducción de Turing de un problema de decisión a un problema de decisión es una máquina de oráculo que decide un problema dado un oráculo para (Rogers 1967, Soare 1987). Se puede entender como un algoritmo que podría ser utilizado para resolver si tenía a su disposición una subrutina para la solución B . El concepto se puede aplicar de forma análoga a los problemas funcionales . ${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle A}$

Si existe una reducción de Turing de a , entonces todos los algoritmos para se pueden usar para producir un algoritmo para , insertando el algoritmo para en cada lugar donde la máquina del oráculo consulta el oráculo . Sin embargo, debido a que la máquina oracle puede consultar el oráculo una gran cantidad de veces, el algoritmo resultante puede requerir más tiempo de forma asintótica que el algoritmo o la computación de la máquina oracle . Una reducción de Turing en la que la máquina oráculo funciona en tiempo polinomial se conoce como reducción de Cook . ${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle B}$${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle B}$${\ Displaystyle A}$

La primera definición formal de computabilidad relativa, entonces llamada reducibilidad relativa, fue dada por Alan Turing en 1939 en términos de máquinas oráculo . Posteriormente, en 1943 y 1952, Stephen Kleene definió un concepto equivalente en términos de funciones recursivas . En 1944, Emil Post utilizó el término "reducibilidad de Turing" para referirse al concepto.

Definición

Dados dos conjuntos de números naturales, decimos que es Turing reducible a y escritura ${\ Displaystyle A, B \ subseteq \ mathbb {N}}$${\ Displaystyle A}$${\ Displaystyle B}$

${\ Displaystyle A \ leq _ {T} B}$

si hay una máquina oráculo que calcula la función característica de A cuando se ejecuta con oráculo B . En este caso, también decimos que A es B -recursivo y B -computable .

Si hay una máquina de Oracle que, cuando se ejecuta con Oracle B , calcula una función parcial con el dominio A , entonces se dice que A es B - recursivamente enumerable y B - computablemente enumerable .

Decimos está Turing equivalente a y escribir si ambos y las clases de equivalencia de conjuntos equivalentes de Turing se denominan Turing grados . Se escribe el grado de Turing de un conjunto . ${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle A \ equiv _ {T} B \,}$${\ Displaystyle A \ leq _ {T} B}$${\ Displaystyle B \ leq _ {T} A.}$${\ Displaystyle X}$${\ Displaystyle {\ textbf {grados}} (X)}$

Dado un conjunto , un conjunto se llama Turing dura para si para todos . Si, además , se llama Turing completo para . ${\ Displaystyle {\ mathcal {X}} \ subseteq {\ mathcal {P}} (\ mathbb {N})}$${\ Displaystyle A \ subseteq \ mathbb {N}}$${\ Displaystyle {\ mathcal {X}}}$${\ Displaystyle X \ leq _ {T} A}$${\ Displaystyle X \ in {\ mathcal {X}}}$${\ Displaystyle A \ in {\ mathcal {X}}}$${\ Displaystyle A}$${\ Displaystyle {\ mathcal {X}}}$

Relación de la completitud de Turing con la universalidad computacional

La completitud de Turing, como se acaba de definir anteriormente, corresponde sólo parcialmente a la completitud de Turing en el sentido de universalidad computacional. Específicamente, una máquina de Turing es una máquina de Turing universal si su problema de detención (es decir, el conjunto de entradas para las que finalmente se detiene) es de muchos uno completo . Por tanto, una condición necesaria pero insuficiente para que una máquina sea computacionalmente universal es que el problema de detención de la máquina sea Turing completo para el conjunto de conjuntos recursivamente enumerables. ${\ Displaystyle {\ mathcal {X}}}$

Ejemplo

Vamos a denotar el conjunto de valores de entrada para el que la máquina de Turing con el índice de correos se detiene. Entonces los conjuntos y son equivalentes de Turing (aquí denota una función de emparejamiento efectiva). Se puede construir una muestra de reducción usando el hecho de que . Dado un par , se puede construir un nuevo índice usando el teorema s _{mn de} manera que el programa codificado por ignore su entrada y simplemente simule el cálculo de la máquina con el índice e en la entrada n . En particular, la máquina con índice se detiene en cada entrada o se detiene en ninguna entrada. Así es válido para todo e y n . Debido a que la función i es computable, esto se muestra . Las reducciones que se presentan aquí no son solo reducciones de Turing, sino reducciones de muchos uno , que se analizan a continuación. ${\ Displaystyle W_ {e}}$${\ Displaystyle A = \ {e \ mid e \ in W_ {e} \}}$${\ Displaystyle B = \ {(e, n) \ mid n \ in W_ {e} \}}$${\ Displaystyle (-, -)}$${\ Displaystyle A \ leq _ {T} B}$${\ Displaystyle e \ in A \ Leftrightarrow (e, e) \ in B}$${\ Displaystyle (e, n)}$${\ Displaystyle i (e, n)}$${\ Displaystyle i (e, n)}$${\ Displaystyle i (e, n)}$${\ Displaystyle i (e, n) \ in A \ Leftrightarrow (e, n) \ in B}$${\ Displaystyle B \ leq _ {T} A}$

Propiedades

• Cada conjunto es Turing equivalente a su complemento.
• Cada conjunto computable es Turing reducible a cualquier otro conjunto. Debido a que cualquier conjunto computable puede calcularse sin Oracle, puede ser calculado por una máquina de Oracle que ignore el oráculo dado.
• La relación es transitiva: si y luego . Por otra parte, se mantiene para cada conjunto A , y por lo tanto la relación es un orden previo (no es un orden parcial porque y no implica necesariamente ).${\ Displaystyle \ leq _ {T}}$${\ Displaystyle A \ leq _ {T} B}$${\ Displaystyle B \ leq _ {T} C}$${\ Displaystyle A \ leq _ {T} C}$${\ Displaystyle A \ leq _ {T} A}$${\ Displaystyle \ leq _ {T}}$${\ Displaystyle A \ leq _ {T} B}$${\ Displaystyle B \ leq _ {T} A}$${\ Displaystyle A = B}$
• Hay pares de conjuntos de tal manera que A no es Turing reducible a B y B no está Turing reducible a A . Por tanto, no es un orden total .${\ Displaystyle (A, B)}$${\ Displaystyle \ leq _ {T}}$
• Hay infinitas secuencias decrecientes de conjuntos debajo . Por tanto, esta relación no está bien fundada .${\ Displaystyle \ leq _ {T}}$
• Cada conjunto es Turing reducible a su propio salto de Turing , pero el salto de Turing de un conjunto nunca es Turing reducible al conjunto original.

El uso de una reducción

Dado que cada reducción de un conjunto a un conjunto tiene que determinar si un solo elemento está dentro en solo un número finito de pasos, solo puede realizar un número finito de consultas de pertenencia al conjunto . Cuando se analiza la cantidad de información sobre el conjunto utilizado para calcular un solo bit de , la función de uso lo hace más preciso. Formalmente, el uso de una reducción es la función que envía cada número natural al número natural más grande cuya pertenencia al conjunto B fue cuestionada por la reducción al determinar la pertenencia de en . ${\ Displaystyle B}$${\ Displaystyle A}$${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle B}$${\ Displaystyle A}$${\ Displaystyle n}$${\ Displaystyle m}$${\ Displaystyle n}$${\ Displaystyle A}$

Reducciones más fuertes

Hay dos formas comunes de producir reducciones más fuertes que la reducibilidad de Turing. La primera forma es limitar el número y la forma de las consultas de Oracle.

• El conjunto es muchos-uno reducible a si hay una función computable total tal que un elemento está en si y solo si está en . Esta función se puede utilizar para generar una reducción de Turing (calculando , consultando el oráculo y luego interpretando el resultado).${\ Displaystyle A}$${\ Displaystyle B}$ ${\ Displaystyle f}$${\ Displaystyle n}$${\ Displaystyle A}$${\ Displaystyle f (n)}$${\ Displaystyle B}$${\ Displaystyle f (n)}$
• Una reducción de tabla de verdad o una reducción de tabla de verdad débil debe presentar todas sus consultas de Oracle al mismo tiempo. En una reducción de tabla de verdad, la reducción también da una función booleana (una tabla de verdad ) que, cuando se dan las respuestas a las consultas, producirá la respuesta final de la reducción. En una reducción de tabla de verdad débil, la reducción usa las respuestas del oráculo como base para el cálculo adicional dependiendo de las respuestas dadas (pero sin usar el oráculo). De manera equivalente, una reducción de tabla de verdad débil es aquella en la que el uso de la reducción está limitado por una función computable. Por esta razón, las reducciones débiles de la tabla de verdad a veces se denominan reducciones de "Turing acotado".

La segunda forma de producir una noción de reducibilidad más sólida es limitar los recursos computacionales que puede utilizar el programa que implementa la reducción de Turing. Estos límites a la complejidad computacional de la reducción son importantes en el estudio de las clases subrecursive tales como P . Un conjunto A es reducible en tiempo polinómico a un conjunto si hay una reducción de Turing de a que se ejecuta en tiempo polinómico. El concepto de reducción del espacio logarítmico es similar. ${\ Displaystyle B}$${\ Displaystyle A}$${\ Displaystyle B}$

Estas reducciones son más fuertes en el sentido de que proporcionan una distinción más fina en clases de equivalencia y satisfacen requisitos más restrictivos que las reducciones de Turing. En consecuencia, tales reducciones son más difíciles de encontrar. Puede que no haya forma de construir una reducción de muchos-uno de un conjunto a otro incluso cuando existe una reducción de Turing para los mismos conjuntos.

Reducciones más débiles

Según la tesis de Church-Turing , una reducción de Turing es la forma más general de una reducción efectivamente calculable. No obstante, también se consideran reducciones más débiles. Se dice que el conjunto es aritmético en si se puede definir mediante una fórmula de la aritmética de Peano con un parámetro. El conjunto es hyperarithmetical en si hay un ordinal recursiva tal que es computable a partir de la α-iterada Turing salto de . La noción de constructibilidad relativa es una noción de reductibilidad importante en la teoría de conjuntos. ${\ Displaystyle A}$ ${\ Displaystyle B}$${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle A}$ ${\ Displaystyle B}$ ${\ Displaystyle \ alpha}$${\ Displaystyle A}$${\ Displaystyle B ^ {(\ alpha)}}$${\ Displaystyle B}$

Ver también

• Reducción de karp

Notas

Referencias

• M. Davis, ed., 1965. The Undecidable — Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions , Raven, Nueva York. Reimpresión, Dover, 2004. ISBN  0-486-43228-9 .
• SC Kleene, 1952. Introducción a las metamatemáticas. Amsterdam: Holanda Septentrional.
• SC Kleene y EL Post, 1954. "La semi-celosía superior de grados de insolubilidad recursiva". Annals of Mathematics v. 2 n. 59, 379–407.
• Publicar, EL (1944). "Conjuntos recursivamente enumerables de números enteros positivos y sus problemas de decisión" ( PDF ) . Boletín de la American Mathematical Society . 50 : 284–316. doi : 10.1090 / s0002-9904-1944-08111-1 . Consultado el 17 de diciembre de 2015 .
• A. Turing, 1939. "Sistemas de lógica basados ​​en ordinales". Actas de la London Mathematics Society , ser. 2 v. 45, págs. 161–228. Reimpreso en "The Undecidable", M. Davis ed., 1965.
• H. Rogers, 1967. Teoría de funciones recursivas y computabilidad efectiva. McGraw-Hill.
• R. Soare, 1987. Conjuntos y grados recursivamente enumerables, Springer.
• Davis, Martin (noviembre de 2006). "¿Qué es ... la reducibilidad de Turing?" ( PDF ) . Avisos de la Sociedad Matemática Estadounidense . 53 (10): 1218-1219 . Consultado el 16 de enero de 2008 .

enlaces externos

• Diccionario NIST de algoritmos y estructuras de datos: reducción de Turing