reducción de Turing

En la teoría de la computabilidad , una reducción de Turing a partir de un problema de decisión.${\displaystyle A}$a un problema de decisión${\displaystyle B}$es una máquina oráculo que decide problemas${\displaystyle A}$dado un oráculo para${\displaystyle B}$(Rogers 1967, Soare 1987) en un número finito de pasos. Puede entenderse como un algoritmo que podría usarse para resolver${\displaystyle A}$si tuviera acceso a una subrutina para resolver${\displaystyle B}$El concepto puede aplicarse de forma análoga a problemas de funciones .

Si una reducción de Turing de${\displaystyle A}$a${\displaystyle B}$existe, entonces cada algoritmo para${\displaystyle B}$^{[ a ]} ​​se puede utilizar para producir un algoritmo para${\displaystyle A}$, insertando el algoritmo para${\displaystyle B}$en cada lugar donde se encuentra la máquina de cálculo oráculo${\displaystyle A}$consulta al oráculo para${\displaystyle B}$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 cualquiera de los algoritmos para${\displaystyle B}$o la computación de la máquina oráculo${\displaystyle A}$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 .

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 a este concepto.

Dados dos conjuntos${\displaystyle A,B\subseteq \mathbb {N} }$de números naturales, decimos${\displaystyle A}$¿Es Turing reducible a?${\displaystyle B}$y escribir

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

si y solo si existe 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 -recursivo 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${\displaystyle A}$¿Es Turing equivalente a?${\displaystyle B}$y escribir${\displaystyle A\equiv _{T}B\,}$si ambos${\displaystyle A\leq _{T}B}$ y${\displaystyle B\leq _{T}A.}$Las clases de equivalencia de conjuntos equivalentes de Turing se denominan grados de Turing . El grado de Turing de un conjunto${\displaystyle X}$está escrito${\displaystyle {\textbf {grados}}(X)}$.

Dado un conjunto${\displaystyle {\mathcal {X}}\subseteq {\mathcal {P}}(\mathbb {N} )}$, un conjunto${\displaystyle A\subseteq \mathbb {N} }$se llama Turing difícil para${\displaystyle {\mathcal {X}}}$si${\displaystyle X\leq _{T}A}$ a pesar de${\displaystyle X\in {\mathcal {X}}}$. Si además${\displaystyle A\in {\mathcal {X}}}$entonces${\displaystyle A}$se denomina Turing completo para${\displaystyle {\mathcal {X}}}$.

Dejar${\displaystyle W_{e}}$denotemos el conjunto de valores de entrada para los cuales la máquina de Turing con índice e se detiene. Entonces los conjuntos${\displaystyle A=\{e\mid e\in W_{e}\}}$y${\displaystyle B=\{(e,n)\mid n\in W_{e}\}}$son equivalentes de Turing (aquí${\displaystyle (-,-)}$denota una función de emparejamiento efectiva ). Una reducción que muestra${\displaystyle A\leq _{T}B}$se puede construir utilizando el hecho de que${\displaystyle e\en A\Leftrightarrow (e,e)\en B}$Dado un par${\displaystyle (e,n)}$, un nuevo índice${\displaystyle i(e,n)}$puede construirse utilizando el teorema S m n   de tal manera que el programa codificado por${\displaystyle i(e,n)}$ignora su entrada y simplemente simula el cálculo de la máquina con índice e en la entrada n . En particular, la máquina con índice${\displaystyle i(e,n)}$o bien se detiene con cada entrada o bien se detiene sin ninguna entrada. Por lo tanto${\displaystyle i(e,n)\in A\Leftrightarrow (e,n)\in B}$Se cumple para todo e y n . Debido a que la función i es computable, esto demuestra${\displaystyle B\leq _{T}A}$Las reducciones que se presentan aquí no son solo reducciones de Turing, sino también reducciones de muchos a uno , que se analizan más adelante.

• Cada conjunto es Turing equivalente a su complemento.
• Todo conjunto computable es Turing reducible a cualquier otro conjunto. Dado que cualquier conjunto computable puede calcularse sin oráculo, puede ser calculado por una máquina de oráculos que ignore el oráculo dado.
• La relación${\displaystyle \leq _{T}}$es transitivo: si${\displaystyle A\leq _{T}B}$y${\displaystyle B\leq _{T}C}$entonces${\displaystyle A\leq _{T}C}$. Además,${\displaystyle A\leq _{T}A}$se cumple para cada conjunto A , y por lo tanto la relación${\displaystyle \leq _{T}}$es un pedido anticipado (no es un pedido parcial porque${\displaystyle A\leq _{T}B}$y${\displaystyle B\leq _{T}A}$no implica necesariamente${\displaystyle A=B}$).
• Hay pares de conjuntos${\displaystyle (A,B)}$ de tal manera que A no es reducible por Turing a B y B no es reducible por Turing a A. Por lo tanto${\displaystyle \leq _{T}}$no es un pedido total .
• Existen secuencias decrecientes infinitas de conjuntos bajo${\displaystyle \leq _{T}}$Por lo tanto, esta relación no está bien fundamentada .
• 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.

Dado que cada reducción de un conjunto${\displaystyle A}$a un conjunto${\displaystyle B}$tiene que determinar si un solo elemento está en${\displaystyle A}$En tan solo un número finito de pasos, solo puede realizar un número finito de consultas de pertenencia al conjunto.${\displaystyle B}$. Cuando la cantidad de información sobre el conjunto${\displaystyle B}$utilizado para calcular un solo bit de${\displaystyle A}$Se discute 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${\displaystyle n}$al mayor número natural${\displaystyle m}$cuya pertenencia al conjunto${\displaystyle B}$fue consultado por la reducción mientras determinaba la pertenencia${\displaystyle n}$en${\displaystyle A}$.

Hay dos formas comunes de producir reducciones más fuertes que la reducibilidad de Turing. La primera consiste en limitar el número y la forma de realizar consultas al oráculo.

• Colocar${\displaystyle A}$es reducible a muchos uno${\displaystyle B}$si existe una función computable total${\displaystyle f}$de tal manera que un elemento${\displaystyle n}$está en${\displaystyle A}$si y solo si${\displaystyle f(n)}$está en${\displaystyle B}$. Dicha función puede utilizarse para generar una reducción de Turing (calculando${\displaystyle f(n)}$consultando al oráculo y luego interpretando el resultado).
• Una reducción de tabla de verdad o una reducción débil de tabla de verdad debe presentar todas sus consultas al oráculo simultáneamente. En una reducción de tabla de verdad, la reducción también proporciona una función booleana (una tabla de verdad ) que, al recibir las respuestas a las consultas, produce la respuesta final de la reducción. En una reducción débil de tabla de verdad, la reducción utiliza las respuestas del oráculo como base para cálculos posteriores que dependen de dichas respuestas (pero sin utilizar el oráculo). De forma equivalente, una reducción débil de tabla de verdad es aquella cuyo uso está limitado por una función computable. Por esta razón, las reducciones débiles de tabla de verdad 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 usar el programa que implementa la reducción de Turing. Estos límites en la complejidad computacional de la reducción son importantes cuando se estudian clases subrecursivas como P. Un conjunto A es reducible en tiempo polinomial a un conjunto${\displaystyle B}$si existe una reducción de Turing de${\displaystyle A}$a${\displaystyle B}$que se ejecuta en tiempo polinomial. El concepto de reducción de espacio logarítmico es similar.

Estas reducciones son más robustas 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. Por consiguiente, son más difíciles de encontrar. Puede que no exista forma de construir una reducción de muchos a uno de un conjunto a otro, incluso cuando exista una reducción de Turing para los mismos conjuntos.

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.${\displaystyle A}$Se dice que es aritmético en${\displaystyle B}$si${\displaystyle A}$se puede definir mediante una fórmula de aritmética de Peano con${\displaystyle B}$como parámetro. El conjunto${\displaystyle A}$es hiperaritmético en${\displaystyle B}$ si hay un ordinal recursivo${\displaystyle \alpha }$de tal manera que${\displaystyle A}$es computable a partir de${\displaystyle B^{(\alpha )}}$, el salto de Turing iterado α de${\displaystyle B}$. La noción de constructibilidad relativa es una noción de reducibilidad importante en la teoría de conjuntos .

• Reducción de Karp

• 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 la metamatemática. Ámsterdam: North-Holland.
• SC Kleene y EL Post , 1954. "El semirretículo superior de grados de irresolubilidad recursiva". Annals of Mathematics , vol. 2, n.º 59, págs. 379-407.
• Post, EL (1944). "Conjuntos recursivamente enumerables de enteros positivos y sus problemas de decisión" ( PDF ) . Boletín de la Sociedad Matemática Americana . 50 (5): 284–316 . doi : 10.1090/s0002-9904-1944-08111-1 . Recuperado el 17 de diciembre de 2015 .
• A. Turing , 1939. «Sistemas de lógica basados ​​en ordinales». Actas de la Sociedad Matemática de Londres , serie 2, vol. 45, págs.  161-228. Reimpreso en «Lo indecidible», M. Davis (ed.), 1965.
• H. Rogers , 1967. Teoría de las funciones recursivas y la 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) . Notices of the American Mathematical Society . 53 (10): 1218–1219 . Recuperado el 16 de enero de 2008 .

• Diccionario de algoritmos y estructuras de datos del NIST: Reducción de Turing
• Universidad de Cambridge, Andrew Pitts, Tobias Kohn: Teoría de la computación
• Página web del profesor Jean Gallier