reducción de turing

Concepto en la teoría de la computabilidad.

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 oráculo que decide el problema dado un oráculo (Rogers 1967, Soare 1987). Puede entenderse como un algoritmo que podría usarse para resolver si tuviera disponible una subrutina para resolver . El concepto se puede aplicar de manera análoga 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 computadora de la máquina Oracle consulta al oráculo para . Sin embargo, debido a que la máquina Oracle puede consultar al Oracle una gran cantidad de veces, el algoritmo resultante puede requerir más tiempo asintóticamente que el algoritmo para la computación de la máquina Oracle . Una reducción de Turing en la que la máquina Oracle funciona en tiempo polinómico 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 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 Oracle que calcula la función característica de A cuando se ejecuta con Oracle B. En este caso, también decimos que A es B recursivo y B computable .

Si hay una máquina 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 que Turing es equivalente a y escribimos si ambos y Las clases de equivalencia de conjuntos equivalentes de Turing se denominan grados de Turing . 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 {deg}}(X)}$

Dado un conjunto , un conjunto se llama Turing difícil si fuera para todos . Si además entonces se le llama Turing completo . ${\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, tal como se acaba de definir, 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 cuales 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 completo de Turing para . Insuficiente porque aún 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

Denotemos el conjunto de valores de entrada para los cuales se detiene la máquina de Turing con índice e . Entonces los conjuntos y son equivalentes de Turing (aquí denota una función de emparejamiento efectiva). Se puede construir una reducción que muestra utilizando 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 el índice e en la entrada n . En particular, la máquina con índice se detiene con cada entrada o se detiene cuando no hay ninguna entrada. Así es válido para todos e y n . Como la función i es computable, esto muestra . Las reducciones presentadas aquí no son sólo 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. Debido a que cualquier conjunto computable se puede calcular sin un oráculo, se puede calcular mediante una máquina oráculo que ignore el oráculo dado.
• La relación es transitiva: si y entonces . Además, es válido para todo conjunto A y, por 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}}$
• Hay infinitas secuencias decrecientes de conjuntos bajo . 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á en un número finito de pasos, solo puede realizar un número finito de consultas sobre la pertenencia al conjunto . Cuando se analiza la cantidad de información sobre el conjunto utilizado para calcular un solo bit , 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 al conjunto fue consultada por la reducción mientras se determina la pertenencia de in . ${\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 forma es limitar el número y la forma de las consultas de Oracle.

• Set es reducible en muchos uno 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 la tabla de verdad o una reducción de la 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 proporciona una función booleana (una tabla de verdad ) que, cuando se le den 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 cálculos adicionales dependiendo de las respuestas dadas (pero sin utilizar el oráculo). De manera equivalente, una reducción de tabla de verdad débil es aquella para la cual el uso de la reducción está limitado por una función computable. Por esta razón, las reducciones débiles de las tablas de verdad a veces se denominan reducciones "de Turing acotadas".

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 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 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 entre 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 manera 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 si se puede definir mediante una fórmula de aritmética de Peano con como parámetro. El conjunto es hiperaritmético si hay un ordinal recursivo tal que sea computable a partir del salto de Turing iterado en α 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}$

Ver 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: artículos básicos sobre proposiciones indecidibles, problemas insolubles y funciones computables , Raven, Nueva York. Reimpresión, Dover, 2004. ISBN  0-486-43228-9 .
• SC Kleene, 1952. Introducción a las metamatemáticas. Ámsterdam: Holanda Septentrional.
• SC Kleene y EL Post, 1954. "La semired superior de grados de insolubilidad recursiva". Anales de Matemáticas v. 2 n. 59, 379–407.
• Correo, EL (1944). "Conjuntos recursivamente enumerables de números enteros positivos y sus problemas de decisión" ( PDF ) . Boletín de la Sociedad Matemática Estadounidense . 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 Sociedad Matemática de Londres , 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, Martín (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
• Universidad de Cambridge, Andrew Pitts, Tobias Kohn: Teoría de la Computación
• Página de inicio del Prof. Jean Gallier