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 el problema dado un oráculo para (Rogers 1967, Soare 1987). Puede entenderse como un algoritmo que podría utilizarse para resolversi 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 .
Si una reducción de Turing de a existe, entonces cada algoritmo para B [a] puede usarse para producir un algoritmo para, insertando el algoritmo para en cada lugar donde la máquina oráculo que computa A consulta al oráculo para. Sin embargo, debido a que la máquina de Oracle puede consultar el Oracle un gran número de veces, el algoritmo resultante puede requerir más tiempo de forma asintótica que el algoritmo para o la computación de la máquina oráculo . Una reducción de Turing en la que la máquina oráculo funciona 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 al concepto.
Definición
Dados dos conjuntos de números naturales, decimos es Turing reducible a y escribe
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 es Turing equivalente a y escribe 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 está escrito .
Dado un conjunto , un conjunto se llama Turing duro por Si para todos . Si adicionalmente luego se llama Turing completo para.
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 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 el conjunto. de conjuntos recursivamente enumerables.
Ejemplo
Dejar denotar 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 a Turing (aquí denota una función de emparejamiento eficaz). Una reducción que muestra se puede construir utilizando el hecho de que . Dado un par, un nuevo índice se puede construir usando el teorema s mn de manera que el programa codificado porignora 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 índicese detiene en cada entrada o se detiene en ninguna entrada. Por lo tantoes válido para todos los e y n . Debido a que la función i es computable, esto muestra. Las reducciones que se presentan aquí no son solo reducciones de Turing, sino reducciones de muchos uno , que se analizan a continuación.
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 transitivo: si y luego . Es más,se cumple para cada conjunto A , y por lo tanto la relaciónes un pedido anticipado (no es un pedido parcial porque y no implica necesariamente ).
- Hay pares de conjuntos de tal manera que un reducibles no se Turing a B y de B no es Turing reducible a una . Por lo tantono es un pedido total .
- Hay infinitas secuencias decrecientes de conjuntos bajo . Por tanto, esta relación no está bien fundada .
- 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 en solo un número finito de pasos, solo puede realizar un número finito de consultas de pertenencia al conjunto . Cuando la cantidad de información sobre el conjunto utilizado para calcular un solo bit de 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 al mayor número natural cuya membresía en el conjunto B fue cuestionada por la reducción al determinar la membresía de en .
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.
- Colocar es muchos-uno reducible asi hay una función computable total tal que un elemento es en si y solo si es en . Esta función se puede utilizar para generar una reducción de Turing (calculando, consultar el oráculo y luego interpretar el resultado).
- 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 utiliza 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 polinomial. El concepto de reducción del espacio logarítmico es similar.
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. Colocarse dice que es aritmético en Si es definible por una fórmula de la aritmética de Peano concomo parámetro. El conjuntoes hiperaritmético en si hay un ordinal recursivo tal que es computable a partir de , el salto de Turing con iteración α de . La noción de constructibilidad relativa es una noción de reductibilidad importante en la teoría de conjuntos.
Ver también
Notas
- ^ Es posible que B sea un problema indecidible para el que no existe un algoritmo.
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 . CS1 maint: parámetro desalentado ( enlace )
- 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 . CS1 maint: parámetro desalentado ( enlace )
enlaces externos
- Diccionario NIST de algoritmos y estructuras de datos: reducción de Turing