Reducibilidad

Una reduccin es una forma de convertir un problema en otro problema de tal forma que la solucin que se le da al segundo problema pueda ser usada para resolver el primero.

Por ejemplo suponiendo que quieres encontrar un camino para una nueva ciudad. T sabes que esto podra ser fcil si t tuvieras un mapa. As t puedes reducir el problema encontrando un camino para ir por la cuidad, al el problema de obtener un mapa para ir por la ciudad. La reducibilidad siempre envuelve dos problemas, a los cuales les podemos llamar A y B, si A se reduce a B, podemos usar la solucin de B para solucionar A. As en nuestro ejemplo A es el problema para encontrar un camino para cruzar la ciudad, y B es el problema de obtener el mapa. Note que la reducibilidad no dice nada acerca de resolver A y B de forma separada, pero si habla acerca de la solucin de A con respecto a obtener la solucin de B. Lo siguiente est ms alejado de los ejemplos de reducibilidad. En la reducibilidad tambin se producen problemas matemticos. Por ejemplo el problema de medicin el rea de un rectngulo se reduce al problema de medir alto por ancho. El problema es solucionado con un sistema lineal de ecuaciones y esto se reduce al problema de invertir una matriz. La reducibilidad juega un importante papel en la clasificacin de problemas por decidibilidad y despus en la complejidad as como en la teora. Cuando A es reducible a B, la solucin de A no puede ser tan difcil que la solucin de B, porque la solucin de B da la solucin de A. En trminos de teora de la computacin si A es reducible a B y B es decidible, A tambin es decidible. Equivalentemente si A es indecidible y reducible a B, B es indecidible. Nuestro mtodo para demostrar que esos problemas son indecidibles puede ser: Mostrar eso uno u otro problema listo, sabiendo que es indecidible reducirlo. 5.1 PROBLEMAS INDECIDIBLES DE TEORIA DE LENGUAJE La indecibilidad de Atm, el problema de determinar si la Maquina de Turing acepta que le den una entrada. Vamos a considerar un problema relacionado, HALT tm, el problema de determinar si la mquina de Turing detiene una entrada. Usamos la indecibilidad de Atm, para probar la indecibilidad de HALT tm, para reducir Atm a HALTtm hicimos: HALTtm={(M,w)/M es un TM y M detiene una estrada de w} TEORTEMA 5.1 HALTtm es indecidible. PRUBA DE IDEA Esta prueba es por contradiccin. Asumimos que HALT es indecidible, contradiciendo el teorema 4.9. La idea principal es mostrar a Atm es reducible a HALT tm. Vamos a asumir eso que tenemos un TM R eso decide a HALT tm. Entonces usamos R para construir S, Un TM decide a Atm. Conseguir un sentimiento para la forma de construir S, pretendiendo eso tu eres S. Tu tarea es decidir Atm tu tienes que dar una entrada de la forma (M,w). Debers aceptar la salida si M acepta a W y debers rechazar la salida si M se cicla o rechaza a w. Trata de simular M en w. Si acepta o rechaza hacer lo mismo. Pero tal vez no eres capaz de determinar si M se est ciclando y en ese caso tu

simulacin no tendr fin. Eso es malo, porque t eres el que decide as nunca permitirs ciclar. Esta idea por s misma no trabaja. En vez de usar la hiptesis que tenemos de que TM R decide a HALTtm. Con R t puedes comprobar si M detiene a w. Si R indica a M detiene a w, rechaza porque (M,w)no estn en Atm. cualquier forma si R indica a M, M detiene a w, puedes hacer la simulacin sin peligro de que se cicle. As si M R existe podemos decidir Atm, pero sabemos que Atm es indecidible. Por virtud de esta contradiccin podemos concluir que R no existe. Por tanto HALTtm es indecidible. PRUEBA Vamos a asumir que los efectos de obtener esa contradiccin TM R decide HALTtm. Construimos TM S decide Atm, con S operando como lo siguiente: S= En las aportaciones(M, w)una codificacin de TM M y a una cadena w: 1. Corre TM R en las aportaciones(M, w) 2. Si R rechaza, rechaza. 3. Si R acepta, simula M en w hasta que se detenga. 4. Si M ha aceptado, acepta, Si M ha rechazado, rechaza. Aclarando si R decide a HALTtm, entonces S decide Atm, porque Atm es indecidible, HALTtm tambin debera ser indecidible. Teorema 5.1: Ilustrada nuestra estrategia para demostrar que el problema es indecidible. Esta estrategia es comn en las pruebas de indecibilidad, excepto por la indecibilidad de Atm misma, la cual es directamente demostrada por el mtodo de diagonalizacin. Ejemplos de reducibilidad para demostrar la indecibilidad. Obtenemos: Etm={(M)/ M es un TM y L(M)=0} TEOREMA 5.2 Etm es indecidible IDEA A PRUEBA Seguimos el patrn adoptado en el teorema 5.1, asumimos la proposicin de obtener una contradiccin Etm es decidible y entonces se muestra Atm es decidible una contradiccin. Obtenemos R es un TM eso decide Etm. Usamos R para construir TM S eso decide Atm. Cmo podr S trabajar cuando recibe una entrada de (M,w). Una idea es para S correr R en entrada (M) y ver si es aceptado, si hace eso nosotros sabemos que L(M) no est vaco y por tanto M no acepta a w. Pero si R rechaza a (M), todo sabemos que L(M) no est vaco y por tanto M acepta alguna cadena, pero si an no sabemos si M no acepta en particular a la cadena w. Necesitamos usar una idea diferente. En vez de correr a R en (M) corremos a R en una modificacin de (M). Modificamos (M) garantizar que M rechaza todas las cadenas excepto w, pero en la entrada de w trabaja comnmente. Entonces usamos R para comprobar si la modificacin a la mquina reconoce el lenguaje vacio. La nica cadena que la mquina puede acepar ahora es la cadena w, ahora este lenguaje podr ser no vacio si y solo si acepta a w. Si R acepta cuando est alimentando una descripcin de la modificacin de la mquina, sabemos que la modificacin de la mquina no acepta ninguna cosa y M no acepta a w. PRUEBA Vamos a escribir la modificacin a la mquina describiendo si nuestra idea a prueba est usando nuestra notacin estndar. Vamos a llamarlo M1. M1=Salida x:

1. Si x no es igual a w, se rechaza 2. Si x es igual a w, corre m en la entrada de w y acepta si M lo hace. Esta mquina tiene una cadena w como parte de esta descripcin. Esto nos conduce a comprobar si x=w en el camino obvio, por exploracin de la entrada y comparando carcter por carcter con w determinar si las cadenas son iguales. Poniendo todo esto junto asumimos que TM R decide Etm y construye TM S eso decide Atm como lo siguiente: S= En la salida (M,w)en codificacin de un TM M y una cadena w. 1. Usa la descripcin de M y w para construir el TM M1, solo describe. 2. Corre R en la entrada M1 3. Si R acepta, rechaza; Si R rechaza, acepta. Notar que S actualmente debe de ser capaz de calcular una descripcin de M1 proviene de una descripcin de M y w. Es capaz de hacer eso porque necesita solo aadir estados extras a M esto comprueba que x=x. Si R estuvo decidida por Etm, S podr ser decidida por Atm. Un decididor por Atm no existe, ahora sabemos que Etm debera se indecidible. Con respecto a la Mquina de turing cosierne a comprobar si dada la Mquina de Turing reconoce un lenguaje que tambin pueda ser reconocido por un simple modelo computacional. Por ejemplo conseguiremos un REGULARtm es el problema de comprobar si dada la mquina de turing tiene el equivalente a un autmata finito. Este problema es algo as como comprobar si la Mquina de Turing reconoce un lenguaje regular. Obtenemos: REGULARtm={(M)/ M es un TM y l(M) es un lenguaje regular} TEOREMA 5.3 REGULARtm es indecidible. IDEA A PRUEBA Usualmente para los teoremas de indecibilidad es para reduccin de Atm. Asumimos que REGULARtm es decidible por TM R y usa esta aceptacin para construir TM S eso decide Atm. Menos obvio ahora es como usar R habilidad para asistir a S en su tarea. No obstante podemos hacer eso. La idea para S es tomar la entrada (M,w)y modifica M as que eres resultado TM reconoce un lenguaje regular y solo si M acepta a w. Vamos a llamar a la segunda modificacin de la mquina M2.Designamos M2 a reconocer el lenguaje no regular{0n 1n|n0} si M no acepta a w y el lenguaje regular si M acepta w. Deberamos especificar como S puede construir tal que M2 de M y w. Aqu, M2 trabaja para aceptar automticamente todas las cadenas en {0n 1n|n0}. Adems si M acepta a w, M2 acepa todas las cadenas. PRUEBA Obtenemos R que es un MT eso decide a REGULAR MT y construye MT S que decide AMT. Entonces S trabaja de la siguiente manera: S=Entrada (M,w)donde M es una MT y w es una cadena: 1. Construye la siguiente MT M2. M2= Entrada x: 1. Si x tiene la forma 0n 1n, acepta. 2. Si x no tiene esta forma, corre M en la entrada w y acepta si M acepta w 2. Corre R en la entrada (M2) 3. Si R acepta, acepta, Si R rechaza, rechaza. Hasta ahora para comprobar los lenguajes indecidibles envuelve una reduccin de AMT. Algunas veces se reduce de algn otro lenguaje indecidible tal como EMT, es ms conveniente cuando nosotros mostramos

que algunos lenguajes son indecidibles. El siguiente teorema muestra la prueba de equivalencia de dos mquinas de Turn en un indecidible problema. Podramos probar eso mediante una reduccin de ATM, pero usamos esta oportunidad para dar un ejemplo de indecibilidad para probar la reduccin en ETM. Obtenemos: EQTM= {(M1, M2)|M1 y M2 son MTs y L(M1)=L(M2)}. TEOREMA 5.4 EQTM es indecidible IDEA A PRUEBA Mostramos que si EQTM fuera decidible, ETM tambin debera ser decidible dando una reduccin de ETM a EQTM. La idea es simple. ETM esel problema de comprobar si el lenguaje de la MT esta vacio. EQ TM es el problema de comprobar si los lenguajes de las MTs son similares. Si uno de estos lenguajes pasa a ser 0, terminamos con el problema de comprobar si el lenguaje de la otra mquina esta vacio, esto es, el problema ETM. As en un sentido el problema ETM es un caso especial del problema EQTM donde una de las mquinas est fijada a reconocer el lenguaje vacio. Esta idea hace dar una fcil reduccin. PRUEBA Obtenemos MT R que decide a EQTM y construye MT S que decide a ETMcomo lo siguiente: S= En la entrada (M) donde M es una MT 1. Corre R en la entrada (M, M1), donde M1 es una MT y esto rechaza todas las entradas. 2. Si R acepta, acepta; Si R rechaza, rechaza. Si R decide EQTM, S decide a ETM. Pero ETM es indecidible por el teorema 5.2 as que EQTM tambin debera ser indecidible. REDUCCIN ATRAVES DE LA HISTORIA DE LA COMPUTACIN El mtodo de la historia de la computacin es una importante tcnica para probar que ATM es reducible a lenguajes ciertos. Este mtodo es a menudo muy utilizado cuando el problema es mostrado como indecidible involucra comprobar la existencia de algo. En Computacin las historias de secuencias son finitas. Si M no detiene en w, no acepta o rechazo de la historia existe para el clculo de M w. En la mayora de las mquinas tienen una historia de la computacin en cualquier entrada. Las mquinas pueden tener muchas historias en una sola entrada, que corresponden a las diversas ramas de la computacin.Nuestro primer indecibilidad la prueba utilizando el mtodo de clculo de la historia se refiere a un tipo de mquina llamada unos autmatas lineales delimitados. DEFINICIN 5.6 Un autmata lineal limitada es un tipo restringido de la mquina de Turn que la cinta de la cabeza no est autorizado a desplazarse fuera de la porcin de la cinta que contiene la entrada. Si la mquina trata de mover su cabeza uno de los extremos de la entrada, la cabeza permanece donde est, de la misma manera que la cabeza no se mueve fuera de la parte izquierda del fin de una mquina de Turn ordinaria de la cinta. Una autmata lineal delimitada es una mquina de Turn con una cantidad limitada de memoria, como se muestra esquemticamente en la figura siguiente. Slo puede resolver problemas que requieren de memoria que puede encajar dentro de la cinta utilizada para la entrada. El uso de un alfabeto de cinta ms grande que el alfabeto permite la entrada de la memoria disponible que se incremente hasta un factor constante. Por lo tanto, decir que para una entrada de longitud n, la cantidad de memoria

disponible

es

lineal

en

n-de

ah

el

nombre

de

este

modelo.

FIGURA 5.1 A pesar de sus limitaciones de memoria, autmatas lineales son bastante limitadas poderosos. Por ejemplo, los decidores de ADFA, ACFG, LUFA y ECFG todos LBAS. Cada CFL puede decidirse por un LBA. De hecho, viene con un decidible idioma que no puede ser decidido por un LBA toma algn trabajo. Desarrollamos las tcnicas para hacerlo en el Captulo 9. En este caso, ALBA es el problema de comprobar si uno acepta su entrada LBA. A pesar de ALBA es el mismo que el cajero automtico indecidible problema cuando la mquina de Turn se limita a ser una LBA, podemos demostrar que es ALBA decidible. Obtenemos ALBA = {(M, w) \ M es un LBA que acepte cadena w}. Antes de probar el decidibilidad encontramos el siguiente lema til. Dice que uno slo puede tener LBA un nmero de configuraciones cuando una cadena de longitud n es la entrada LEMA 5.7 Vamos M ser un LBA con q g estados y smbolos en la cinta alfabeto. Hay exactamente qngn diferentes configuraciones de M para una cinta de longitud n. Recordemos que la prueba de una configuracin de M es como una instantnea en el centro de su clculo. Una configuracin consiste en el estado del control, la posicin de la cabeza, y el contenido de la cinta. En este sentido, M tiene q estados. La longitud de la cinta es n, de modo que la cabeza puede estar en uno de n posiciones, y gn posibles cadenas de cinta smbolos aparecen en la cinta. El producto de estas tres cantidades es el nmero total de diferentes configuraciones de M con una cinta de longitud n. Teorema 5.8 ALBA es decidible. IDEA A PRUEBA Con el fin de decidir si acepta la entrada de LBA M w, que simulan M en w. En el curso de la simulacin, si M se detiene y acepta o rechaza, se acepta o rechaza en consecuencia. El problema se produce si M bucles en w. Tenemos que ser capaces de detectar un bucle para que podamos detener y rechazar. La idea de detectar cundo M bucle es que, como se calcula sobre la M w, que va desde la configuracin a la configuracin. Si M se repite una configuracin cada vez que vaya a repetir esta configuracin una y otra vez y, por tanto, estar en un bucle. Porque M es una causa de LBA, el importe de la cinta a su disposicin son limitados. Si M no se ha detenido entonces, se debe recorrer. PRUEBA El algoritmo que decide a ALBA es como lo siguiente: L=Entrada (M,w) donde M es un LBA y w es una cadena: 1. Simulando que M en w por los pasos qngn hasta que se detenga.

2. Si M est detenida acepta, si ha aceptado y rechazado. Si no ha parado se rechaza Si M en w no ha detenido dentro de qngn pasos, se debe repetir una configuracin conforme al teorema 5.7 y por lo tanto bucle. Por ello, nuestro algortmo rechaza el ejemplo. El teorema 5.8 muestra que LBAS e IMS difieren en un modo esencial: Para LBAS problema es la aceptacin decidible, pero para memorias de traduccin no lo es. Sin embargo, algunos otros problemas siguen siendo los problemas que afectan a LBAS indecidible. Uno de ellos es el vaco problema ELBA M = {() | M es un LBA donde L (H] 0}. Para probar que es de aplicacin del LBA es indecidible, damos una reduccin de clculo que utiliza el mtodo de la historia. TEOREMA 5.9 ELBA es indecidible IDEA A PRUEBA Esta prueba es por la reduccin de la ATM nos muestran que, si. ELBA es decidable, ATM tambin. Supongamos que ELBA es decidible. Cmo podemos utilizar este supuesto para decidir ATM? Para una TM M y una entrada w podemos determinar si acepta M con w por cierto construye LBA B y, a continuacin, comprobar si L (B) est vaca. El lenguaje que reconoce B comprende todas las historias de computacin que acepta M en w. Si M acepta w, este lenguaje contiene una cadena y lo es vacio. Si M no acepta w, esta lengua est vaca. Si podemos determinar si la lengua B est vaca, podemos claramente determinar si M acepta w. Ahora se describe cmo construir B de M y W. Tenga en cuenta que tenemos que mostrar ms que la mera existencia de B. Tenemos que mostrar cmo una mquina de Turn puede obtener una descripcin de las descripciones dadas B de M y W. Construimos B a aceptar su entrada A; o si, es una aceptacin de la historia de la computacin M en w. Recordemos que la aceptacin de una historia de la computacin es la secuencia de configuraciones, C 1, C2,... , Cn M que pasa por cierto, ya que la cadena w. A los efectos de esta prueba vamos a suponer que la aceptacin de la historia de la computacin se presenta como una nica cadena, con las configuraciones separados entre s por el smbolo #, como se muestra en la siguiente figura.

FIGURA 5.2 Una posible entrada al B. El LBA B funciona de la siguiente manera. Cuando se recibe una entrada x, B, se supone que si uno acepta: es un clculo de la aceptacin de M en w. En primer lugar, B rompe x de acuerdo con los delimitadores en C 1, C2,... , Cn. A continuacin, comprueba si el B, C1 cumplen las tres condiciones de un clculo de la historia. 1. Ci es el inicio de configuracin para M en w. 2. Cada Ci+1 legalmente sigue de Ci. 3. Ci es la aceptacin de una configuracin para M. El inicio de configuracin C1 para M en w es la cadena q0, w1, w2, wn, donde q0 es el comienzo del Estado de M en w. En este caso, B tiene esta cadena en directamente construido, por lo que es capaz de verificar la primera condicin. Aceptar una configuracin es la que contiene el qaceptado estado, por lo que B puede comprobar la tercera condicin de la

exploracin Ci para gaceptado. La segunda condicin es la ms difcil de comprobar. Para cada par de configuraciones adyacentes, si los controles de B Ci+1 legalmente sigue de C . Este paso implica la verificacin de que C y D + i son idnticos excepto para las posiciones bajo y junto a la cabeza en la C . Estas posiciones deben actualizarse de acuerdo con la transicin funcin de M. Entonces, B comprueba que la actualizacin se realiz correctamente en zig-zagging entre las posiciones correspondientes de Ci y Ci + i, mantener el crack de las posiciones actuales, mientras que zigzagging, conservando su actual posicin con puntos en la cinta. Por ltimo, si las condiciones 1,2, y 3 se satisfacen, B acepta su entrada. Tenga en cuenta que el LBA B no se construye con el fin de que realmente ejecuta en algunos de entrada una confusin comn. Construimos B nicamente para el fin de alimentar a una descripcin de B en el partido decisivo para ELBA ^ 3AT nave que supone que existe. Una vez que este decisivo devuelve su respuesta que se puede invertir para obtener la respuesta a la pregunta de si M acepta w. Por lo tanto, podemos decidir en cajeros automticos, un contradiccin. PRUEBA Ahora estamos listos para la reduccin del estado de la ATM a ELBA TM-R Suponga que decide ELBA construir TM S ATM que decide lo siguiente. S = "Sobre la entrada (M, w), donde M es una TM y w es una cadena: 1. ELBA construye B de M y w como se describe en la idea de la prueba. 2. Ejecutar corrida de entrada (B). 3. Si R rechaza, acepta, si acepta R, rechaza".

FIGURA 5.3 LBA B TM comprobar un historial de clculo. Si R acepta (B), entonces L(B) = 0. Por lo tanto M no tiene la aceptacin de clculo en la historia w y M no acepta w. En consecuencia rechaza 5 (M, w). Del mismo modo, si R rechaza (B), la lengua de B es no vacio. La nica cadena que puede aceptar es una historia de computacin M en w. Por lo tanto debe aceptar H w. Consecuentemente, S acepta (H, w). Figura 5.3 muestra un cheque de un clculo TM historia. Tambin podemos utilizar la tcnica de clculo de reduccin de historias a travs de establecer la indecidibilidad de ciertos problemas relacionados con el contexto gramatical libre y autmatas. Recuerde que en el Teorema 4.7 presentamos un algoritmo para decidir si un contexto libre de cualquier cadena genera la gramtica, es decir, si L (G) = 0. Ahora nos muestran que un problema relacionado con que es indecidible. Es el problema de comprobar si un contexto libre de gramtica genera todas las cadenas. Demostrando que este problema es indecidible es el principal paso en el que demuestra que la equivalencia problema para gramticas libres de contexto es indecidible. Se obtiene
ALLCFG= {{G}\ G

es un CFG y L(G] = *}.

TEOREMA 5.10
ALLCFG es indecidible.

PRUEBA Esta prueba es por contradiccin. Obtener la contradiccin asumimos que ALLCFG es decidible y utilizar esta hipteisi para demostrar que ATM es decidible.Se describe cmo utilizar un procedimiento de decisin ALLCFG para decidir ATM. Para una TM M y una entrada w que construir una CFG G genera todas las cadenas si y slo si M no acepta w. Por lo tanto, si M acepta w, G no generar algunos cadena. Esta cadena es lo quesupongo-la aceptacin de clculo en la historia de M w. Esto es, G est diseada para generar todas las cadenas no aceptar el cmputo de las historias de M w. Para hacer el CFG G generar todas las cadenas que no se acepte una clculos sobre la historia de M w, utilizamos la siguiente estrategia. Una cadena puede dejar de ser un clculo de aceptar la historia por varias razones. La aceptacin de un clculo en la historia de M w aparece como C1 # C2# Ci # , donde C, es la configuracin de las fusiones en el de paso de la computacin en w. Entonces, G genera todas las cadenas 1. no se inician con C i, 2. no terminan con la aceptacin de una configuracin, o 3. donde algunos d no correctamente rendimiento C + i con arreglo a las normas de M. Si M no acepta w, no aceptar el cmputo historia existe, por lo que no todas las cadenas de una manera u otra. G, por lo tanto, generar todas las cadenas que, segn lo desee. Ahora tenemos a la construccin de G. En lugar de construir, que construir un PDA D. Sabemos que podemos utilizar en la construccin de Teorema 2.12 reales en la pgina 106 a convertir a un CFG. Lo hacemos porque, para nuestros propsitos, el diseo de un PDA es ms fcil que disear un CFG. En este caso, se iniciar por D no determinar la ramificacin y adivinar cul de las tres condiciones anteriores, para comprobar. Una rama de los controles sobre si el inicio de la cadena de entrada es C i acepta y si no lo es. Otra rama de los controles de entrada si la cadena termina con una configuracin que contiene el estado aceptar, y acepta si no lo es. La tercera rama se supone si algunos Ci no aceptan correctamente rendimiento ci+ 1 Acta sobre el escaneo de entrada hasta que no dereministico decide que ha llegado a Ci. A continuacin, empuja Ci en la pila hasta que llega a la final marcado por el smbolo #. A continuacin, aparece la pila D comparar con C + i Se supone que coinciden alrededor de la cabeza, salvo cuando la diferencia de posicin est dictada por la transicin de la funcin M. Por ltimo, D acepta si resulta un desequilibrio o una inadecuada actualizacin. El problema con esta idea es que, cuando C empuja D fuera de la pila, es reverso en orden y no es adecuado para la comparacin con C i+ 1. En este punto el giro en la prueba aparece: Nosotros escribimos la historia de la aceptacin de clculo diferente. Todos los dems configuraciones figura en el orden inverso. El extrao posiciones siguen siendo escrito en la orden de avanzar, pero las posiciones an estn escritos atrs. Por lo tanto, un clculo que acepta la historia, aparecer como se muestra en la siguiente figura.

FIGURA 5.4 Configuracin de todos los dems escritos en orden inverso En esta forma modificada de la PDA es capaz de empujar una configuracin de modo que cuando se apareci la orden es adecuado para la comparacin con la siguiente. Diseamos D a aceptar cualquier cadena que no es aceptar la historia en el clculo modificada. En el Ejercicio 5.1 se puede utilizar Teorema 5.10 para demostrar que EQCFG es indecidible. Un individuo domin parece

Una coleccin que parece domin :

La tarea es hacer una lista de estos dominos (repeticiones permitidas), de modo que la cadena que recibimos por la lectura de los smbolos en la parte superior es la misma que la cadena de smbolos en la parte inferior. Esta lista se llama un partido. Por ejemplo, la siguiente lista es un partido de este rompecabezas.

La Lectura de la parte superior tenemos a, b, ca, a, abc cadena, que es el mismo que la lectura de la parte inferior. Tambin podemos describir este partido por la deformacin del domin de manera que los correspondientes smbolos de la parte superior e inferior de la lnea.

Para algunas colecciones de domin encontrar un partido no puede ser posible. Por ejemplo, la coleccin.

No puede contener un partido porque cada cadena de arriba es ms largo que el correspondiente fondo de cadena El Post correspondiente problema es determinar si una coleccin de domin tiene un partido. Este problema es insoluble por algoritmos. Permite el estado precisamente del problema y entonces se expresa como un lenguaje. Una instancia de PCP es una coleccin P de domins:

Y coincide esta secuencia i1, i2, in. donde ti1,ti2.....tn=bi1,bi2..bin. El problema es determinar si P ha coincidido. PCP={(P)/ P es una instancia de problema postcorrespondiente con coincidencia} TEOREMA 5.11 PCP es indecidible. IDEA A PRUEBA. Conceptualmente esta prueba es simple. Aunque tiene detalles muy tcnicos. La tcnica principal es la reduccin de ATM mediante la aceptacin de historias de la computacin. Mostramos esa forma como TM M y entrada w podemos construir una instancia P donde una coincidencia es aceptar una historia de computacin de M en w. Si pudiramos determinar si la instancia es una coincidencia, deberamos ser capaces de determinar si M acepta a w. MPCP={(P)/P es una instancia de problemas pos-correspondiente con una coincidencia que comienza en el primer domino} Obtenemos detalles de la prueba y designamos P para simular M en w. PRUEBA Obtenemos TM R decide al PCP y construye a S que decide ATM Obtenemos:

Donde Q, , y son el conjunto del Estado, el alfabeto de entrada, cinta alfabeto, y transicin de la funcin de M, respectivamente. En este caso, S construye una instancia de la PCP P que tiene un partido si y slo si M acepta w. Para hacer que el S construye una primera instancia P 'de la MPCP. Se describe la construccin en siete partes, cada una de las cuales logra un aspecto particular de la simulacin de M en w. Para explicar lo que estamos haciendo nosotros entrelace la construccin con un ejemplo de la construccin en la accin.
Parte 1.

La construccin comienza de la siguiente manera.

Dado que P ' es una instancia de la MPCP el partido debe comenzar con este domin. Por lo tanto, la parte inferior cadena comienza correctamente con C1 = q0 w 1 w 2 w n, de la primera configuracin de la aceptacin de clculo en la historia de M ow, como se muestra en la siguiente figura.

FIGURA A partir de la coincidencia MPCP

5.5

La parte inferior de cadena consiste de # q0w 1 w 2 w n # y la parte superior de la cadena consiste nicamente #. Para obtener un partido que tenemos que extender el principio de cadena para que coincida con la parte inferior cadena. Ofrecemos domin adicional para permitir esta ampliacin. La causa ms domin Ms configuracin prxima a aparecer en la ampliacin de la parte inferior de cadena por obligar a una sola fase de simulacin de M. En las partes 2, 3 y 4, se aade a P' domin que realizan la parte principal de la simulacin. Parte 2 se ocupa de las mociones cabeza hacia la derecha, la parte 3 se ocupa de las mociones cabeza a la izquierda, y la parte 4 se ocupa de la cinta no clulas adyacentes a la cabeza. Para cada uno, a, b y todos los q, r Q donde q qreject,if (q,a) = (r, b, R),[qr /br] puesto en P '.
Parte 2.

Para cada uno, a, b y todos los q, r Q donde q qreject,if (q,a) = (r, b, L), [ cqa/] puesto en P '.
Parte 3. Parte 4.

Para cada uno , poner [a/a] puesto P.

Ahora constituyen un ejemplo hipottico para ilustrar lo que hemos construido hasta ahora. Deje que = (0, 1, 2, ). Decir que es la cadena w0100 y que el inicio del Estado de M es q0. En estado q0, la lectura de un 0, decir que la transicin exige que la funcin M entra en estado q7, escribe un 2 en la cinta, y su cabeza se mueve hacia la derecha. En otras palabras, (q0, 0) = (q7, 2, R). Coloca a la Parte I de domin [#/#]=[t1/b1]

En P, y comienza el partido:

Adems, coloca a la parte 2 de domin

[q00/2q7]

Como (q0, 0) = (q7, 2, R) y parte 4 lugares el domin [0/0],[1/1],[2/2],y[u/u] En P ', tal como 0, 1, 2, y u son los miembros de . Que, junto con la parte 5, nos permite extender el partido de la siguiente manera.

Por lo tanto, el domin de las partes 2, 3 y 4 vamos a prorrogar el partido mediante la adicin de la segunda configuracin despus de la primera. Queremos que este proceso contine, la adicin de la tercera configuracin, luego el cuarto, y as sucesivamente. Para que ello ocurra tenemos que aadir una ficha ms para atar el smbolo #.
Parte 5.

put[#/#][#/#]en

El primero de estos domin nos permite copiar el smbolo # que aparece en la separacin de las configuraciones. Adems, domin el segundo nos permite aadir un smbolo u blanco al final de la configuracin para simular lo infinitamente muchos espacios a la derecha que se suprimen cuando se escriba la configuracin. Continuando con el ejemplo, digamos que en estado q7, la lectura de un 1, una va al estado q5, escribe un 0, y mueve la cabeza hacia la derecha. Es decir, (q7, 1) = (q5, O, R). Luego tenemos el domino. [q71/0q5]en p As que la ltima correspondencia parcial se extiende a

Entonces, supongamos que en las costillas q5 la lectura de un 0, M va al estado q9, escribe un 2, y mueve su cabeza hacia la izquierda. As que (q 5, 0) _ (q9 ,2, L). Entonces tenemos el domin

El primero de ellos es importante, ya que el smbolo a la izquierda de la cabeza es una 0. Laanterior correspondencia parcial se extiende a

Tenga en cuenta que, como la construccin de un partido, nos vemos obligados a simular Mentrada en w. Parte 6. Para cada uno ,

Esta medida tiene el efecto de la adicin de "pseudo-medidas" de la mquina de Turing ha detenido despus de que, cuando la cabeza "come" smbolos adyacentes hasta la izquierda no hay ninguna. Contina con el ejemplo anterior, si la coincidencia parcial hasta el momento en que la mquina se detiene en un estado es de aceptar

El domin que acaba de agregar permitir que contine el partido;

Parte 7.

Por ltimo, aadir el domin

y completar el partido:

Que llega a la conclusin de la construccin de P'. Recordemos que P' es una instancia de la cual el partido MPCP simula el clculo de M en w. Para terminar la prueba, recordar que el MPCP difiere de la PCP en que el partido est obligado a comenzar con el primer domin en la lista. Si consideramos que P 'como una instancia de la PCP en lugar de la MPCP, que obviamente tiene un partido, independientemente de si se detiene en la M w. Puedes encontrarlo? (Pista: Se ve corto). Ahora s para convertir P' a P, un ejemplo de que todava el PCP simulando M en hacerlo con un truco un poco tcnico. La idea es construir, este proceso contina hasta que llega a una detencin de la FVR estado. En caso de aceptar un estado, queremos dejar que la parte superior de la coincidencia parcial "ponerse al da" con el fondo para que el partido completo. Podemos arreglar para que eso ocurra, aadiendo ms domin. La obligacin de comenzar con la primera ficha directamente en el problema de manera que indique el requisito explcito se convierte en innecesaria. Nosotros tenemos la necesidad de introducir alguna notacin para este propsito. Permitir u =u1u2un. Cualquier cadena de longitud n. Definir *u, u *, y * u *

que se las tres cadenas.

En este caso, u * aade el smbolo * antes de cada personaje en u, u * aade una despus de cada carcter en la u, y * u * aade un tanto antes como despus de cada personaje en u. Para convertir P'a P, un ejemplo de la PCP, que haga lo siguiente. Si P'era la coleccin

Dejamos que sea la coleccin P

Considerando P como una instancia de la PCP, vemos que el nico domin que podra comenzar un partido es la primera.

Porque es el nico donde tanto la parte superior y la parte inferior de inicio con el mismo smbolo, a saber, *. Adems de forzar el partido a partir del primer domin, la presencia de la * s no afecta a las posibles coincidencias, ya que simplemente con el original entrelace de smbolos. El original de los smbolos se produce actualmente en las posiciones, incluso la del partido. El domin [*t/t] Est ah para permitir que la parte superior para aadir el extra * al final del partido.
5.3 CARTOGRAFIA REDUCIBILIDAD

La nocin de la reduccin de un problema a otro puede definirse formalmente en una de varias maneras. La eleccin de cul utilizar depende de la aplicacin. Nuestra eleccin es un simple tipo de reducibilidad llamada cartografa reducibilidad.Ser capaz de reducir un problema a problema B por medio de un mapeo reducibilidad significa que existe una funcin computable que convierte en un problema de posiciones a los casos de problema B. Si tenemos una funcin de conversin, llamado una reduccin, que puede resolver con un solucionador de B. La razn es que cualquier instancia de A puede ser resuelta en primer lugar mediante la reduccin de la conversin a una postura de B-y, a continuacin, aplicar el solucionador de B.A Una definicin precisa de la cartografa sigue reducibilidad en breve.
FUNCIONES COMPUTABLES

Una mquina de Turing calcula una funcin a partir de la entrada a la funcin de la cinta y poner fin con la salida de la funcin en la cinta. DEFINICIN 5,12 Una funcin f:E*->E* es una funcin computable si algunos de mquina de Turing M, en cada entrada w, slo se detiene con f (w) en su cinta.

EJEMPLO 5.13

Todas las operaciones aritmticas habituales en enteros son computables funciones. Por ejemplo, podemos hacer una mquina que tiene entrada (m, n) y devuelve m + n, ni la suma de y n. No damos ningn detalle aqu, lo que les deja como ejercicios.
EJEMPLO 5.14

Computables funciones que las transformaciones de las descripciones mquina. Por ejemplo, una funcin f computables w toma de entrada y devuelve la descripcin de una mquina de Turing (H'), si w = (M) es una codificacin de una mquina de Turing M. La mquina M es una mquina que reconoce el mismo el idioma como U, pero nunca-en la tentacin de trasladar su cabeza la parte izquierda del final de su cinta. La funcin f tienta esta tarea mediante la adicin de varios estados a la descripcin de M. La funcin devuelve e w si no es una codificacin jurdica de una mquina de Turing.
Definicin formal de CARTOGRAFIA REDUCIBILITY

Ahora definimos la cartografa reducibilidad. Como computacional que representan problemas de idiomas.
DEFINICIN 5.15

de

costumbre

Un lenguaje de mapeo es reducible a la lengua B, escrito A m B, si existe una funcin computable f:E*->E*donde para cada w, w E a<->f(w)E B La funcin f se llama la reduccin de A a B. La siguiente figura ilustra la cartografa reducibility.

FIGURA La reduccin de la funcin f de A a B

5.6

Una cartografa de la reduccin de A a B proporciona una manera de convertir las preguntas sobre la membreca de prueba en un ensayo a la adhesin en la parte B. Para probar si a la w A, que utilizamos para la reduccin fmapa w para f (w) y probar si f (w) E B. El trmino proviene de la reduccin de la cartografa de la funcin o la cartografa que proporciona los medios de hacer la reduccin.

Si un problema es reducible a una cartografa en segundo lugar, problema resuelto con anterioridad, con lo que podemos obtener una solucin a la captura original problema, Tenemos esa idea en el siguiente teorema.
Teorema 5.16

Si A m B y B es decidable, entonces A es decidable. PRUEBA Dejamos lbf decisivo es que la B y f es la reduccin de A B. Se describen en N para una de la siguiente manera. N = en la entrada w: Compute el f (w) Ejecute M en el f (w) de la entrada y fuera los rendimientos cualquier puesto Claramente, si w A, entonces el f(w) B porque f es una reduccin de un B as M recibe el f(w) siempre que w A. por consiguiente N trabaja como deseado. N=entrada en w: 1. Calcular f(w) 2. Ejecute M en la entrada f (w) y sea cual sea la salida M salidas." Evidentemente, si un w B porque F es una reduccin de A a B. Por lo tanto acepta M f (w) cuando w A. Por lo tanto las obras como desee. El siguiente corolario de Teorema 5.16 ha sido nuestra principal herramienta para demostrar indecidibilidad. COROLARIO 5.17 Si m y B es indecidible, entonces B es indecidible Ahora revisar algunas de nuestras pruebas antes de que la reducibilidad del el mtodo utilizado para obtener ejemplos de la cartografa sean reducibles. EJEMPLO 5.18 En el Teorema 5.1 que utiliza una reduccin de los cajeros automticos para demostrar que es un HALTTM decidible. Esta reduccin mostr cmo un partido decisivo para HALTTM podra ser utilizado para dar un decisivo para HALTTM podemos demostrar una cartografa de reducibilidad ATM a HALTTM de la siguiente manera. Para ello tenemos que presentar un computables funcin o que tenga la forma de entrada (M, w) y devuelve la salida de la forma (M ', w'), donde: (M,w) ATM si y solo si (M ', w') HALTTM. La siguiente mquina F calcula la reduccin de f. F = "Sobre la entrada (M, w): 1. Construir la siguiente mquina M '. M '= "El x de entrada: 1. Ejecutar M en x. 2. Si M acepta, aceptar. 3. Si M rechaza, entrar en un bucle. " 2. Salida (M ', w). EJEMPLO 5.19 La prueba de la indecidibilidad de la correspondencia postal problema en Teorema 5.11 reducciones contiene dos mapas. En primer lugar, muestra que ATM MPCP y, a continuacin, muestra que MPCP

EJEMPLO 5.20 Una reduccin de la cartografa a ETM a EQTM radica en la prueba del Teorema 5.4. En este caso, la reduccin o mapas de la entrada (M) a la salida (M, M 1), donde M1 es la mquina que rechaza todas las entradas. EJEMPLO 5.21 La prueba del Teorema 5.2 que muestra que ETM es indecidible ilustra la diferencia entre la nocin de la cartografa oficial reducibilidad que hemos definido en esta seccin y en el concepto de reducibilidad que hemos usado anteriormente en este captulo. La prueba muestra que TM es indecidible ATM mediante la reduccin a la misma. Vamos a ver si podemos convertir esta reduccin en una reduccin de la cartografa. Reduccin de la original fcilmente podemos construir una funcin o que tenga de entrada (M, w) y produce la salida (Mi), donde MI es la mquina de Turn de que se describen en la prueba. Sin embargo, M acepta w si y slo si (Mi) no es tan vaco ATM de reduccin de la cartografa a ETM Sigue ETM muestra que es capaz indecidibilidad porque no se ve afectada por la complementacin, pero no da una reduccin de la cartografa de ATM a ETM En realidad, no existe tal reduccin, como se le pide que mostrar en el Ejercicio 5.5. La sensibilidad de la cartografa de la reducibilidad es importante a la complementacin en el uso de reducibilidad para probar el no reconocimiento de determinados idiomas. Tambin podemos utilizar la cartografa reducible para mostrar que los problemas no son Turn. El siguiente teorema es anlogo a Teorema 5.16 TEOREMA 5.22 Si AmB B es un Reconocible-Turn entonces A es un Turn-reconocible. La prueba es el mismo que el del Teorema 5.16, excepto que M y N, se reconocen en lugar de decidir. COROLARIO 5.23 Si AmB y A n o es un Reconocible-Turn, entonces B no es un reconocibleTurn. En una tpica aplicacin de este corolario, nos permiten ser un ATM, el complemento de la ATM Sabemos que ATM no es reconocible a partir del corolario de Turn 4.17. La definicin de la cartografa de la reducibilidad implica que A TEOREMA 5.24 EQTM No es no Turn- reconocible ni Turn-noreconocible PRUEBA. En primer lugar, la prueba de demostrar que no es Turing ETTMes reconocible. Lo hacemos porque demuestra que ATM es reducible a EQTM. La reduccin de funciona como sigue. F = "Sobre la entrada (M, w) donde M es una TM Y W es una cadena : 1. La construccin de las siguientes dos mquinas de M1 y M2 M1 = "En cualquier entrada: 1. Rechazar. M2 = En cualquier entrada: 1. Ejecute M en w. Si acepta, acepta 2. De salida (M1, M2). " Aqu, M1 acepta nada. Si M acepta w, M2 acepta todo, y as las dos mquinas no son equivalentes. Por el contrario, si M1 no acepta w, M2acepta nada, y que sean equivalentes. Por lo tanto ATM reduce ATM a EQTM como lo desee. Para demostrar que EQTM Turn no es reconocible damos una reduccin de los cajeros automticos para el complemento de EQTM, a saber, EQTM. Aqui

nos muestran que ATM funcin g.

TM

. Los siguientes TM G calcula la reduccin de la

C = "La entrada (M, w), donde M es una cadena de TM y w una cadena. 1. La construccin de las siguientes dos mquinas M1 y M2 M1 = "En cualquier entrada: 1. Aceptar". 2. M2 =" En cualquier entrada 1. Ejecutar M en w, 2. Si acepta, aceptar". 2. Salida (M1, M2)."
La nica diferencia entre g y F se encuentra en la mquina M1. En M1 a siempre rechaza, mientras que en g siempre acepta. En ambos f y g, M acepta w si y slo si M2 acepta siempre. En g, M acepta w si y slo si M1 y M2 son equivalentes. Esa es la razn por la g es una reduccin de la ATM a EQTM