Reducción de Turing

Concepto en la teoría de la computabilidad

En 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 oráculo que decide un problema dado un oráculo para (Rogers 1967, Soare 1987). Puede entenderse como un algoritmo que podría usarse para resolver si tuviera a su disposición una subrutina para resolverlo . El concepto puede aplicarse análogamente a problemas de funciones . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$

Si existe una reducción de Turing de a , entonces cada algoritmo para ^[a] puede usarse para producir un algoritmo para , insertando el algoritmo para en cada lugar donde la máquina oráculo que calcula consulta al oráculo para . Sin embargo, debido a que la máquina oráculo puede consultar al oráculo una gran cantidad de veces, el algoritmo resultante puede requerir más tiempo asintóticamente que el algoritmo para o que la máquina oráculo que calcula . Una reducción de Turing en la que la máquina oráculo se ejecuta 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 . Más tarde, 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 Turing es reducible a y escribimos ${\displaystyle A,B\subseteq \mathbb {N} }$ ${\displaystyle A}$ ${\displaystyle B}$

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

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

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

Decimos que Turing es equivalente a y escribimos si ambos y Las clases de equivalencia de los conjuntos equivalentes de Turing se denominan grados de Turing . El grado de Turing de un conjunto se escribe . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A\equiv _{T}B\,}$ ${\displaystyle A\leq _{T}B}$ ${\displaystyle B\leq _{T}A.}$ ${\displaystyle X}$ ${\displaystyle {\textbf {deg}}(X)}$

Dado un conjunto , un conjunto se llama Turing duro para si para todos . Si además entonces 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 entre la completitud de Turing y la universalidad computacional

La completitud de Turing, tal como se acaba de definir más arriba, 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 completo en muchos-uno para el conjunto de conjuntos recursivamente enumerables. Por lo 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 . Insuficiente porque todavía puede darse el caso de que el lenguaje aceptado por la máquina no sea en sí mismo recursivamente enumerable. ${\displaystyle {\mathcal {X}}}$ ${\displaystyle {\mathcal {X}}}$

Ejemplo

Sea el conjunto de valores de entrada para los cuales la máquina de Turing con índice e se detiene. Entonces los conjuntos y son equivalentes de Turing (aquí denota una función de emparejamiento efectiva). Se puede construir una reducción que muestre usando el hecho de que . Dado un par , se puede construir un nuevo índice usando el teorema s mn de modo que el programa codificado por ignore su entrada y simplemente simule el cálculo de la máquina con índice e en la entrada n . En particular, la máquina con índice se detiene en cada entrada o se detiene en ninguna entrada. Por lo tanto, se cumple para todos los e y n . Debido a que la función i es computable, esto muestra . Las reducciones presentadas 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 equivalente de Turing a su complemento.
• Todo conjunto computable es reducible por Turing a cualquier otro conjunto. Como cualquier conjunto computable puede calcularse sin ningún oráculo, puede calcularse mediante una máquina de oráculos que ignore el oráculo dado.
• La relación es transitiva: si y entonces . Además, se cumple para cada conjunto A , y por lo tanto la relación es un preorden (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 tales que A no es reducible de Turing a B y B no es reducible de Turing a A. Por lo tanto, no es un orden total . ${\displaystyle (A,B)}$ ${\displaystyle \leq _{T}}$
• Existen infinitas sucesiones decrecientes de conjuntos bajo . Por lo tanto, esta relación no está bien fundada . ${\displaystyle \leq _{T}}$
• Todo 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á en solo un número finito de pasos, solo puede hacer un número finito de consultas de pertenencia al conjunto . Cuando se analiza la cantidad de información sobre el conjunto utilizada para calcular un solo bit de , esto se precisa mediante la función de uso . 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 en el conjunto fue consultada por la reducción al determinar la pertenencia de en . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle B}$ ${\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 es limitar la cantidad y la forma de realizar consultas al oráculo.

• Un conjunto es reducible a varios por uno si existe una función computable total tal que un elemento está en si y solo si está en . Una función de este tipo 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 oráculo al mismo tiempo. En una reducción de tabla de verdad, la reducción también proporciona una función booleana (una tabla de verdad ) que, cuando se le proporcionan 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 utiliza las respuestas del oráculo como base para realizar cálculos posteriores en función de las respuestas proporcionadas (pero sin utilizar 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 este motivo, las reducciones de tabla de verdad débil a veces se denominan reducciones de "Turing limitadas".

La segunda forma de producir una noción de reducibilidad más fuerte 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 cuando se estudian clases subrecursivas 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 en el 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 precisa entre clases de equivalencia y satisfacen requisitos más restrictivos que las reducciones de Turing. En consecuencia, dichas 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 exista 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. Sin embargo, también se consideran reducciones más débiles. Se dice que un conjunto es aritmético en si es definible por una fórmula de aritmética de Peano con como parámetro. El conjunto es hiperaritmético en si hay un ordinal recursivo tal que es computable a partir de , el salto de Turing α -iterado de . La noción de constructibilidad relativa es una noción de reducibilidad 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}$

Véase también

• Reducción de Karp

Notas

1. Es posible que B sea un problema indecidible para el que no existe ningún algoritmo.

Referencias

• M. Davis, ed., 1965. Lo indecidible: documentos básicos sobre proposiciones indecidibles, problemas irresolubles y funciones computables , 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 semired superior de grados de irresolubilidad recursiva". Anales de Matemáticas, vol. 2, n.º 59, 379-407.
• Post, EL (1944). «Conjuntos enumerables recursivamente de números enteros positivos y sus problemas de decisión» ( PDF ) . Boletín de la American Mathematical Society . 50 (5): 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 Mathematical Society , serie 2, vol. 45, págs. 161-228. Reimpreso en "The Undecidable", ed. M. Davis, 1965.
• H. Rogers , 1967. Teoría de funciones recursivas y computabilidad efectiva. McGraw-Hill.
• R. Soare , 1987. Conjuntos y grados enumerables recursivamente, Springer.
• Davis, Martin (noviembre de 2006). "¿Qué es... la reducibilidad de Turing?" (PDF) . Notices of the American Mathematical Society . 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
• Universidad de Cambridge, Andrew Pitts, Tobias Kohn: Teoría de la computación
• Página de inicio del profesor Jean Gallier