teoria de la computacion via palindromos - carolina mejia

5/6/2018 Teoria de La Computacion via Palindromos - Carolina Mejia - slidepdf.com

http://slidepdf.com/reader/full/teoria-de-la-computacion-via-palindromos-carolina-mejia 1/76

This is page iPrinter: Opaque this

Teoria de la Computacion: via palindromos

Carolina Mejia, Juan Andres Montoya

Febrero 2009



ii

ABSTRACT En este breve libro hemos intentado estudiar algunos de losconceptos basicos de la Teoria de la Computacion. Para ello hemos decididoestudiar diferentes aspectos computacionales del lenguaje de los palindro-

mos sobre un alfabeto dado: su decidibilidad, su lugar en la jerarquia deChomsky, su complejidad temporal, su relacion con el no-determinismo,algunas de sus aplicaciones en, por ejemplo, el reconocimiento de patronesy en la bioinformatica



This is page iiiPrinter: Opaque this

Contents

1 Problemas y lenguajes vii

1.1 Problemas y lenguajes . . . . . . . . . . . . . . . . . . . . . vii1.2 Modelos de computacion . . . . . . . . . . . . . . . . . . . . viii

2 Automatas regulares xiii

2.1 Automatas …nitos y lenguajes regulares . . . . . . . . . . . xiii2.2 El lema de bombeo para lenguajes regulares . . . . . . . . . xv

2.3 Automatas no deterministicos . . . . . . . . . . . . . . . . . xvii2.4 Automatas de doble via: equivalencias . . . . . . . . . . . . xix2.4.1 El teorema de Myhill-Nerode . . . . . . . . . . . . . xx2.4.2 Prueba de la equivalencia . . . . . . . . . . . . . . . xxi

2.5 Ejercicios capitulo 2 . . . . . . . . . . . . . . . . . . . . . . xxii

3 Automatas de pila xxiii

3.1 Automatas de pila . . . . . . . . . . . . . . . . . . . . . . . xxiii3.2 Automatas de pila no deterministicos y lenguajes libres de

contexto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxvi3.3 Ejercicios capitulo 3 . . . . . . . . . . . . . . . . . . . . . . xxviii

4 Maquinas de Turing xxxi

4.1 Maquinas de Turing con una cinta . . . . . . . . . . . . . . xxxi4.1.1 La tesis de Church y la jerarquia de Chomsky . . . . xxxiii4.1.2 Turing computabilidad de los lenguajes libres de con-

texto . . . . . . . . . . . . . . . . . . . . . . . . . . . xxxv



iv Contents

4.2 Tiempo de computo: analisis de algoritmos . . . . . . . . . xxxvi4.3 Lenguajes no computables . . . . . . . . . . . . . . . . . . . xxxviii4.4 Maquinas universales . . . . . . . . . . . . . . . . . . . . . . xxxix

4.5 Ejercicios capitulo 4 . . . . . . . . . . . . . . . . . . . . . . xlii

5 Una introduccion a la complejidad computacional xlv

5.1 Una cota inferior para P al: secuencias de cruce . . . . . . . xlvi5.2 Maquinas de Turing multicinta . . . . . . . . . . . . . . . . xlviii5.3 Maquinas multidimensionales . . . . . . . . . . . . . . . . . lii

5.3.1 Una cota inferior . . . . . . . . . . . . . . . . . . . . lvi5.3.2 Una cota superior . . . . . . . . . . . . . . . . . . . lviii

5.4 Otros modelos: la tesis de Church fuerte . . . . . . . . . . . lx5.4.1 Maquinas de Turing probabilisticas . . . . . . . . . . lx5.4.2 Maquinas cuanticas . . . . . . . . . . . . . . . . . . lxx

5.5 Ejercicios capitulo 5 . . . . . . . . . . . . . . . . . . . . . . lxxi

6 Aplicaciones lxxiii6.1 Reconocimiento de patrones: Listado de palindromos aprox-

imados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . lxxiii

References lxxv



This is page vPrinter: Opaque this

Prefacio

Este pequeño libro pretende ser una introduccion agil y sencilla a la teoriade la computacion (o mejor, a unos pocos temas de la teoria de la com-putacion). El libro fue escrito desde la perspectiva de un practicante de lacomplejidad computacional. Creemos que un libro completamente difer-ente habria surgido de manos de un practicante de algotra de las muchasareas que constituyen las ciencias de la computacion. Creemos tambienque este libro puede ser de gran ayuda, si se le utiliza como lectura previaal estudio en profundidad de la teoria de la complejidad computacional, y

precisamente ese es y ha sido el objetivo de los autores.A lo largo del libro hemos usado, a manera de Drosophila, para ilustrarla mayor parte de los conceptos introducidos problemas computacionalesrelacionados con el lenguaje de los palindromos.

El librillo esta organizado a lo largo de seis capitulos. El capitulo 1pretende ser una introduccion informal a las problematicas y conceptos dela teoria de la computacion. En el capitulo 2 se estudian los automatasregulares. En el capitulo 3 los automatas de pila. El capitulo 4 introduceel modelo de maquinas de Turing. El capitulo 5 pretende ser una breveintroduccion a la Complejidad computacional. En el capitulo 6 se estudianalgunas aplicaciones en el Reconocimiento de patrones y la Bioinformatica.

El lector interesado puede pro…ndizar en algunos topicos de la teoriade la computacion usando las excelentes referencias [6] y [10]. El lector

interesado en la teoria de la Complejidad computacional puede consultarla referencia [8].



vi Contents



This is page viiPrinter: Opaque this

1

Problemas y lenguajes

En este breve capitulo introducimos los conceptos basicos y parte de lanotacion que emplearemos con frecuencia en el texto

1.1 Problemas y lenguajes

A lo largo del texto el simbolo sera usado para denotar conjuntos …nitos,

y mas especi…camente para denotar conjuntos …nitos de caracteres a losque llamaremos alfabetos . Dado = fa1;:::;ang un alfabeto, el conjunto es el conjunto de todas las palabras …nitas construidas con los simbolosde ; esto es el conjunto es igual al conjunto de todos las cadenas …nitasde simbolos de :

Advertencia. El conjunto contiene palabras de todas las longitudes …nitas incluyendo una unica palabra de longitud cero, la palabra vacia, a la que denotaremos con el simbolo :

De…nición 1 Un -lenguaje es un conjunto L :

En lo que sigue, (cuando el contexto lo permita), evitaremos usar eltermino -lenguaje y a cambio usaremos simplemente el termino lenguaje .

Ejemplo 2 Sea P al el lenguaje de los -palindromos, esto es el conjuntode todas las cadenas …nitas de simbolos de que se leen igual de izquierda a derecha que de derecha a izquierda.



viii 1. Problemas y lenguajes

Dada x = x1x2:::xn una palabra en el alfabeto (esto es x1x2:::xn 2 ),el simbolo x denotara el reverso de x; es decir la palabra xnxn1:::x1: Noteque el lenguaje de los palindromos es igual a

fx 2 : x = xg

Pregunta. ¿Es P al un lenguaje computable?Es claro que una respuesta a la pregunta anterior implica de…nir antes,

de manera precisa, el signi…cado de la expresion: lenguaje computable. In-tuitivamente un lenguaje es computable si y solo si existe un procedimientomecanico que permite reconocer los elementos del lenguaje.

De…nición 3 L es decidible (o computable) si y solo si existe un algoritmo M tal que dado x 2 ; el algoritmo M acepta x si y solo si x 2 L.

La de…nicion anterior no es muy diferente a la de…nicion intuitiva delenguaje computable, y al igual que esta, nos obliga a aclarar primero elsigni…cado de algunos de los terminos utilizados, en particular el signi…cadodel termino algoritmo.

Pregunta (La pregunta central de la teoria de la computacion). ¿Quees un algoritmo?

Respuesta. Un algoritmo es una maquina computadora.Muy probablemente la respuesta que acabamos de dar a la pregunta

central de la teoria de la computacion es un respuesta que deja insatisfechoa mas de un lector. Los lectores mas condecendientes aceptaran que estaes una buena respuesta si podemos aclarar (de una vez por todas) que esuna maquina computadora. Bueno, de alguna manera, este es el objetivocentral del presente libro.

1.2 Modelos de computacion

Uno de los objetivos de este libro es estudiar algunos de los muchos modelosde computacion que han sido propuestos como respuestas parciales a lapregunta: ¿que es una maquina computadora? La de…nicion y el analisisde modelos concretos los pospondremos hasta los capitulos subsiguientes.En esta breve seccion tan solo intentaremos acotar el posible signi…cadode la expresion: modelo de computacion. Para empezar podemos decirque, …jando el alfabeto , un modelo de computacion es un dispositivo queprocesa elementos de y que posee las siguientes caracterisiticas

1. Puede leer el input, esto es dado x 2 ; una maquina computadoraal procesar x tiene la habilidad de leer cada uno de los caracteres dex:



1.2 Modelos de computacion ix

2. Aunque podria almacenar una cantidad ilimitada de informacion, encada instante de la computacion la maquina computadora tan solopuede usar una cantidad …nita y acotada de informacion.

3. Las operaciones que la maquina ejecuta en un instante dado estancompletamente determinadas por: los caracteres de x, el input, quela maquina se encuentra leyendo en ese instante y por el fragmentode la informacion almacenada que la maquina se encuentra leyendoen ese instante.

Para dotar a un dispositivo de computo de estas tres habilidades podemosimaginar que la maquina cuenta con:

1. Una cabeza lectora que lee a lo mas un caracter en cada instante dela computacion.

2. Una memoria, representada por: un conjunto …nito de estados, que

pueden ser usados para almacenar una cantidad …nita de informacion(cantidad esta que es proporcional al tamaño del conjunto de esta-dos); y posiblemente un dispositivo externo de memoria que podriaalmacenar una cantidad ilimitada de informacion, pero de la cual soloes posible usar una cantidad acotada en cada instante de la computa-cion.

3. Una tabla …nita de transiciones o tabla de mando, la cual determina,en cada instante de la computacion, la operacion que la maquina hade realizar. Tal decision ha de tomarse teniendo en cuenta (unica yexclusivamente) el caracter que lee la cabeza lectora en ese instante yel fragmento de la informacion, almacenada en el dispositivo externo,que la maquina usa en ese instante. Ademas, las operaciones que la

maquina puede realizar se limitan a: cambiar de estado, reemplazara lo mas un caracter del input y escribir (o borrar) una cantidadacotada de caracteres en el dispositivo externo de memoria (si es elcaso que la maquina posee uno).

Podemos imaginar una maquina computadora como un dispositivo com-puesto por: un numero …nito de cintas semi-in…nitas, una cabeza lectora (olecto-escritora) por cada una de las cintas, un dispositivo interno de memo-ria y una tabla de mando. Cada cinta semi-in…nita esta compuesta por unacoleccion enumerable y bien ordenada de celdas que podemos identi…car,o etiquetar, con los numeros naturales. Cada una de las celdas, en cadainstante de la computacion, puede o estar ocupada por un caracter o estarvacia. supondremos que el alfabeto de la maquina contiene un simbolo

especial, digamos , para indicar celdas vacias (o, lo que es lo mismo, es-pacios en blanco). Supondremos que al inicio de la computacion el inputx se encuentra escrito en el extremo izquierdo de una de las cintas de lamaquina, esto es si x = x1:::xn; supondremos entonces que x ocupa las



x 1. Problemas y lenguajes

primeras n-celdas de una de sus cintas, a la que llamaremos cinta de en-trada . Por otro lado, supondremos que las celdas a la derecha de la n-esima,en la celda de entrada, se encuentran ocupadas por espacios en blanco, (esto

es por el caracter ): Cada cinta cuenta con una cabeza lecto(escritora)que en algunos casos se podra mover en las dos direcciones (de izquierda aderecha y de derecha a izquierda) y que en otros casos solo se podra moverde izquierda a derecha. Cada cabeza lectora puede leer el contenido dela celda sobre la que se halla ubicada, si la cabeza es lecto-escritora po-dra, adicionalmente, reemplazar dicho caracter por algotro cualquiera delos caracteres del alfabeto de la maquina. Una transicion de la maquinaconsiste en:

1. Leer los caracteres de las celdas sobre las que se hallan las cabezaslectoras.

2. Reemplazar cada uno de estos caracteres, por un caracter diferente o

por el mismo (i.e. no realizar reemplazo alguno).3. Mover cada una de las cabezas lectoras a alguna de las celdas con-

tiguas a la celda sobre la que actualmente se encuentra. Dado i 2 Nlas celdas contiguas a la celda i-esima son la i 1-esima, la i-esima yla i + 1-esima.

4. Cambiar de estado.

Que transicion realiza la maquina dependera de la con…guracion en laque se encuentre la maquina, donde una con…guracion esta constituida por

El estado interno de la maquina. La maquina cuenta con un conjunto de estados, su dispositivo interno de memoria, el cual le permitecodi…car informacion referente a: que acciones(transiciones) acaba de

realizar y que acciones pretende realizar.

Los caracteres que estan siendo leidos en ese instante.

Dado que el alfabeto de la maquina es …nito, el conjunto de estados es…nito y el numero de cintas es …nito, tenemos que el numero de las posiblescon…guraciones es …nito.

La maquina cuenta, adicionalmente, con una tabla …nita de mandoque especi…ca para cada con…guracion de la maquina, cual es la tran-sicion que esta debe realizar.

Lo anterior esta muy lejos de ser una de…nicion de maquina computa-dora. Aun asi lo anterior nos permite desde ya decir algunas cosas no

evidentes acerca de maquinas computadoras. Es posible argumentar, apartir de la discusion precedente, que el numero de las maquinas computa-doras es enumerable, y de ello podemos concluir que existen lenguajes nocomputables.



1.2 Modelos de computacion xi

Teorema 4 Dado un alfabeto no vacio, existe L tal que L no es decidible.

Proof. Note simplemente que el cardinal del conjunto de todos los -lenguajes es igual a 2@0 : Recuerde que @0 2@0 ; por lo que existen maslenguajes a ser decididos que maquinas que puedan decidirlos. Tenemosentonces que existe una cantidad no enumerable de lenguajes no decidibles.

Dado que existen lenguajes no decidibles, es posible que P al sea uno deellos. Es claro que existen procedimentos, a los que informalmente podemosllamar algoritmos, que pueden ser usados para reconocer el lenguaje Pal:No es di…cil diseñar un programa que pueda ser usado para reconocer palin-dromos (ejercicio: diseñe un tal programa). Toda nocion formal de com-putabilidad debe capturar de manera adecuada la nocion intuitiva de com-putabilidad, y en consecuencia todo lenguaje intuitivamente computabledebe ser computable si se considera una nocion formal de computabilidad

que quepa considerar adecuada. En los capitulos siguientes introducire-mos diferentes modelosde computacion, o lo que es lo mismo diferentesnociones de computabilidad, y estudiaremos el lenguje P al a la luz de estasde…niciones formales.



xii 1. Problemas y lenguajes



This is page xiiiPrinter: Opaque this

2

Automatas regulares

En este capitulo estudiaremos la clase de los automatas regulares. Losautomatas regulares son, en cierto sentido, las maquinas computadorasmas elementales que podamos imaginar. Es por ello, entre otras cosas,que su poder de computo es muy limitado. Un automata regular es undispositivo de computo que: carece de un dispositivo externo de memoria,cuenta con una cabeza de solo lectura la cual, ademas, solo puede moverseen una direccion.

2.1 Automatas …nitos y lenguajes regulares

Advertencia. A partir de este punto, en lo que queda del libro, supon-dremos …jado un alfabeto : Podemos suponer, como es costumbre en teoria de la computacion, que es igual a f0; 1g :

Un automata regular M es un cuadrupla (Q; q 0; F ; ) ; donde:

1. Q es un conjunto …nito, el conjunto de estados del automata M:

2. q 0 2 Q; es un elemento distinguido de Q; que sera llamado el estadoinicial del automata M:

3. F Q es el conjunto de estado …nales o estados de aceptacion delautomata M:

4. ; la funcion de transicion , es una funcion de Q en Q.



xiv 2. Automatas regulares

Dado un alfabeto y dado M un -automata regular supondremos queM posee una cinta semiin…nita constituida por una cantidad enumerable deceldas, supondremos ademas que la cinta se extiende de izquierda a derecha

empezando en una celda inicial. Cada celda de M tiene la capcidad dealbergar un unico caracter del conjunto [ fg ; donde es un caracterespecial que denota espacio en blanco o, lo que es lo mismo, celda vacia. Alcomienzo de la computacion el input x = x1x2:::xn se encuentra ubicadoen el extremo izquierdo de la cinta ocupando los primeros n caracteres. Alcomienzo de la computacion la cabeza lectora de la maquina se encuentraubicada sobre la primera celda leyendo el caracter x1 y el estado de lamaquina es el estado interno inicial q 0: Al comenzar la computacion lacabeza lectora de la maquina se dezplaza a la derecha, de celda en celdaleyendo de a un caracter. La computacion termina cuando la maquinaencuentra la primera celda ocupada por un caracter ; esto es cuando lacabeza lectora llega al …nal del input. El caracter sera usado para denotarel espacio en blanco y para indicar que la computacion debe terminar. Alterminar la computacion la maquina se encuentra en un estado internoq 2 Q: Si q 2 F; la maquina acepta el input, en caso contrario lo rechaza.

De…nición 5 1. L (M) = fx 2 : M acepta xg : Dado M; diremos que L (M) es el lenguaje reconocido por el automata M:

2. Dado L ; diremos que L es un lenguaje regular si y solo si existe M, un automata regular, tal que L = L (M) :

Comentario 6 La de…nicion de automata regular implica que el tiempo de computo empleado por un tal automata al procesar un input x es igual a jxj(el simbolo jxj denota la longitud del input x), donde el iempo de computode M al procesar x es simplemente el numero de transiciones realizados por

la maquina durante la computacion. Tenemos entonces que todo automata regular M reconoce el lenguaje regular L (M) en tiempo real. Reconocer un lenguaje no trivial usando una maquina secuencial (es decir, una maquina que no realiza mas de una transicion de manera simultanea) requiere, comominimo, tiempo real. Lo anterior implica que los automatas regulares son maquinas secuenciales optimas, cuando de reconocer lenguajes regulares se trata, el problema es que los lenguajes computables mas interesantes y mas importantes no son regulares.

Sea = f0; 1g : Dada x 2 ; el simbolo kxk0 denotara el numerode caracteres de x que son iguales a 0; reciprocamente kxk1 denotara elnumero de unos.

Ejemplo 7 Sea L = fx 2 : kxk0 1(mod2) y kxk1 1(mod2)g : El

lenguaje L es un lenguaje regular. Sea M = (Q; q 0; F ; ) el automata regular de…nido por

1. Q =

q 1000; q 1001; q 1100q 1101

:



2.2 El lema de bombeo para lenguajes regulares xv

2. q 0 = q 1000:

3. F =

q 1101

4. es la funcion de transicion de…nida por

0; q 1000

= q 1001;

0; q 1001

= q 1000;

0; q 1100

= q 1101

0; q 1101

= q 1100;

1; q 1000

= q 1100;

1; q 1001

= q 1101

1; q 1100

= q 1000;

1; q 1101

= q 1001:

Es facil convencerse de que L = L (M) :

Note que, en el ejemplo anterior, el lenguaje L es regular esencialmenteporque la informacion relevante relativa a los fragmentos iniciales de unainstancia de L puede ser codi…cada usando un numero acotado de bits,especi…camente dos: un bit que codi…ca la paridad del numero de unosleidos y un segundo bit que codi…ca la paridad del numero de ceros leidos(los bits a la derecha de los subindices y superindices que hemos usadocomo distintivos de los elementos de Q). El teorema de Myhill-Nerode(que estudiaremos mas adelante), indica que un lenguaje L es regular si ysolo si la informacion relevante, referente a los segmentos iniciales de lasinstancias de L; puede ser codi…cada usando un numero acotado de bits (oequivalentemente de estados, note que los estados son el unico dispositivode memoria con que cuenta un automata regular). En el caso de lenguajesregulares generales, la informacion relevante relativa al fragmento inicial,que del input la maquina ha leido, es la etiqueta (o numero) de la clasede equivalencia a la que pertenece este fragmento. El teorema de Myhill-Nerode a…rma precisamente que L es regular si y solo si el numero de estas

clases de equivalencia es …nito (si y solo si es posible decribir la etiqueta decada clase usando una cantidad acotada de bits).

2.2 El lema de bombeo para lenguajes regulares

El lema de bombeo es una herramienta poderosa que puede ser usada paraprobar no regularidad.

Teorema 8 (lema de bombeo para lenguajes regulares)Dado L un lenguaje regular, existe K 2 N tal que si x 2 L y jxj K;

existen entonces u;v;w 2 para las cuales se satisface lo siguiente

1. x = uvw:

2. jvj 0 y juvj K

3. Para todo n 2 N se tiene que uvnw 2 L:



xvi 2. Automatas regulares

Proof. Sea M = (Q; q 0; F ; ) un automata regular que reconoce el lenguajeL: Al automata M podemos asociarle un digrafo etiquetado G [M] el cualesta de…nido por

V (G [M]) = Q:

Dados q; p 2 V (G [M]) y dado a 2 ; existe una arista de q a p conetiqueta a si y solo si ((a; q )) = p:

Note que una computacion de M es simplemente un camino …nito enG [M] con origen en q 0: Note tambien que todo camino …nito con origenen q 0 es una computacion de M; y que las computaciones aceptantes estanen correspondencia biyectiva con los caminos de este tipo que tienen suvertice …nal dentro del conjunto F V (G [M]) :

A…rmamos que el K en el enunciado del teorema es igual a jQj + 1:Dado que el grafo G [M] tiene tamaño jQj ; todo camino de longitud mayor

o igual que jQj + 1 debe pasar al menos dos veces por un mismo vertice,digamos p Podemos partir un tal camino en tres fragmentos a saber.

1. Fragmento inicial, que va de q 0 hasta la primera visita al vertice p:

2. Fragmento intermedio, el bucle que va de la primera visita a p hastala segunda visita a p:

3. Fragmento …nal, desde la segunda visita al vertice p hasta el vertice…nal.

Dada x 2 L; si jxj jQj + 1 el camino determinado por x; al quedenotaremos x, puede partirse en tres fragmentos, el inicio, el bucle y el…nal. Estos tres fragmentos corresponden a fragmentos de x; digamos u; v

y w: Dado n 2 N, el camino determinado por la palabra uvn

w tiene lasiguiente estructura.

1. El inicio es identico al inicio del camino x:

2. El fragmento intermedio corresponde a recorrer n veces el fragmentointermedio de x (recuerde que este fragmento intermedio es un bucle,y por lo tanto es posible recorrer este bucle tantas veces como seanecesario).

3. El fragmento …nal es identico al fragmento …nal de x (o mejor, delcamino determinado por x)

Ahora, dado que x 2 L el vertice …nal de x pertenece a F: Note que el

vertice …nal del camino uvnw es identico al vertice …nal del camino x; porlo que la computacion de M con input uvnw es tambien una computacionaceptante y esto implica que uvnw 2 L. Note …nalmente que es posibletomar u y v de tal forma que juvj K; esto es asi dado que todo fragmento



2.3 Automatas no deterministicos xvii

inicial, del camino x; que tenga una longitud mayor o igual que jQj + 1debe contener un bucle

A continuacion probaremos que P al no es regular.

Corolario 9 (Primera cota inferior para L)No existe un automata regular que pueda reconocer el lenguaje Pal:

Proof. Suponga que P al es regular y sea K como en el enunciado del lemade bombeo. Considere x = 1K +101K +1: El lema de bombeo a…rma queexisten palabras u;v; y w tales que x = uvw; juvj K y tales que dadoi 2 la palabra uviw 2 Pal: Note que la desigualdad juvj K implicaque v esta totalmente contenido en el fragmento izquierdo de x constituidopor K + 1 unos. Tenemos entonces que uviw = 1K +jvjijvj01K que no esun palindromo dado que jvj 1

Del corolario anterior hemos dicho que es una cota inferior para P al, dadoque este corolario establece que los recursos computacionales que de…nen

la clase de los automatas regulares no son su…cientes para reconocer ellenguaje Pal; para ello se requiere algo mas, se necesita mayor poder decomputo.

No es de extrañar que el lenguaje P al no pueda ser reconocido por unautomata regular. Note que, en la de…nicion de automata regular, hemosimpuesto demasiadas limitaciones al poder de computo de este tipo dedispositivos, algunas de las mas prominentes limitaciones son las siguientes:

La cabeza lectora solo puede moverse en una direccion, esto es deizquierda a derecha.

La maquina no tiene un dispositivo de memoria externo.

La maquina no tiene funciones de escritura

La maquina no puede marcar (o transformar) fragmentos o caracteresdel input.

En lo que sigue estudiaremos modelos que podemos concebir como obtenidosa partir de nuestro modelo basico (la clase de los automatas regulares) elim-inando una o varias de estas (y otras) limitaciones.

2.3 Automatas no deterministicos

En esta seccion estudiaremo un segundo modelo de computacion, obtenidoa partir del modelo basico, adicionando a este una habilidad: transiciones

no deterministicas.Un automata regular no deterministico es un automata M = (Q; q 0; F ; )

para el cual la relacion de transicion no necesariamente es funcional, estoes M esta constituido por un conjunto de estados Q; un estado inicial q 0, un



xviii 2. Automatas regulares

conjunto de estados aceptantes F y una relacion de transicion QQ:Es discutible que el no-determinismo sea una habilidad computacional y quelas maquinas no deterministicas sean mas potentes que las deterministicas

(para el caso de maquinas de Turing de tiempo polinomial la pregunta: ¿elno-determinismo incrementa el poder de computo? No es otra cosa que lafamosa, y casi mistica, pregunta: ¿es P igual a NP ?). Existen al menosdos maneras de pensar el nodeterminismo:

Una maquina no deterministica es una maquina capaz de realizaradivinanzas afortunadas.

Una maquina no deterministica es una maquina capaz de realizar enparalelo un gran numero de computaciones.

Es claro que desde cualquiera de las dos perpectivas anteriores el no-determinismo aparece como una habilidad adicional (un recurso computa-

cional) que puede (y debe) incrementar el poder de nuestras maquinas.Sea M = (Q; q 0; F ; ) un automata no deterministico.

De…nición 10 Dado x = x1:::xn un input de M; una computacion de Mcon input x es una secuencia q 0q 1:::q n de elementos de Q tal que para todoi n se tiene que (xi; q i1; q i) 2 :

Una computacion es entonces una secuencia …nita y ordenada de con- …guraciones que adicionalemente satisface la siguiente condicion: todo parde con…guraciones consecutivas estan conectadas por una transicion de lamaquina.

La nocion de con…guracion depende del modelo de computacion. Intu-itivamente, una con…guracion es una descripcion completa del estado dela computacion en un instante dado. En el caso de los automatas regu-lares es su…ciente especi…car el estado (estado interno, elemento de Q) enel que se encuentra la maquina para describir completamente el estado dela computacion. Esto es asi dado que en el instante t de la computacionla cabeza lectora de la maquina se encuentra sobre la t-esima celda de sucinta (leyendo el t-esimo caracter) y el contenido de la cinta en este in-stante es identico al contenido de la cinta en el instante 0: Esto implicaque el unico parametro que nosotros podriamos desconocer es precisamenteel estado interno de la maquina, y es este parametro (y es precisamente lodesconocido) lo que la con…guracion describe y debe describir.

De…nición 11 Dado M un automata regular no deterministico y dadox 2 ; diremos que M acepta x si y solo si existe una computacion de Mcon input x que termina en un estado de aceptacion.

En esta seccion probaremos que los automatas regulares no deterministi-cos y los automatas regulares deterministicos tienen exactamente el mismopoder de computo.



2.4 Automatas de doble via: equivalencias xix

Teorema 12 Todo automata regular no deterministico puede ser simuladopor un automata regular.

Proof. Sea L un lenguaje reconocible mediante un automata regular nodeterministico y sea M = (Q; q 0; F ; ) un tal automata que reconoce L:

Considere el automata regular Mdet =

Qdet; q det0 ; F det; det

de…nido por:

1. Qdet = P (Q) :

2. q det0 = fq 0g :

3. F det = fA Q : A \ F 6= ?g :

4. La funcion det es de…nida por

det ((a; A)) = fq 2 Q : 9 p 2 A ( ((a; p)) = q )g

Es facil veri…car que L (M) = L Mdet :El siguiente corolario es una consecuencia inmediata de los dos teoremas

anteriores

Corolario 13 (Segunda cota inferior para P al)No existe un automata regular no deterministico que pueda reconocer el

lenguaje Pal:

2.4 Automatas de doble via: equivalencias

En esta seccion introduciremos un clase de maquinas aparentemente maspoderosas que los automatas regulares, a esta clase de maquinas las llamare-mos automatas de doble via (2way-automata). Los automatas de doble viason automatas regulares provistos de una cabeza lectora que puede moverseen las dos direcciones. Es de esperar que esta habilidad adicional con…eramayor poder de computo a estas maquinas, y es de esperar que tal poderadicional sea su…ciente para reconocer el lenguaje Pal: Intuitivamente, sila cabeza lectora de la maquina puede moverse de izquierda a derecha y dederecha a izquierda, puede entonces moverse varias veces a lo largo de lacinta en las dos direcciones y veri…car (o, reciprocamente, veri…car que no esel caso) que para todo i jxj ; el caracter i-esimo y el caracter jxj i-esimocoinciden. Sorprendentemente este no es el caso. El teorema principal deesta seccion a…rma que los automatas de doble via tienen exactamente elmismo poder de computo que los automatas regulares (y en consecuencia

los automatas de doble via son incapaces de reconocer el lenguaje P al).De…nición 14 Un automata de doble via es una quintupla

M = (Q; q 0; F ; A ; )



xx 2. Automatas regulares

tal que Q es un conjunto …nito de estados, q 0 2 Q es el estado inicial,F A Q y es una funcion de Q en Q f!; g :

Dado a 2 y q 2 Q; si la maquina se encuentra leyendo el caracter a, enel estado q y (a; q ) = (!; p) ; entonces la cabeza de la maquina se desplazauna posicion a la derecha y el estado interno de la maquina cambia de q a p:Por el contrario si (a; q ) = (; p) ; la cabeza de la maquina se mueve unaposicion a la izquierda. Dado que la cabeza de la maquina podria llegaral extremo derecho de la maquina y devolverse a la izquierda, nada nosgarantiza que la computacion de la maquina terminara en algun momento,es por ello que en la de…nicion de automata de doble via hemos agregado elparametro A: La idea es que si el estado interno de la maquina pertenecea A la maquina para.

2.4.1 El teorema de Myhill-Nerode

El teorema de Myhill-Nerode puede ser entendido como una caracterizacionalgebraica de los lenguajes regulares. Caracterizaciones de este tipo siempreson utiles en Matematicas. Como lo vermos mas adelante, el teorema deMyhill-Nerode puede ser usado para probar algunos hechos importantesreferentes a los lenguajes regulares.

De…nición 15 Dado L ; podemos de…nir una relacion de equivalencia sobre asociada a L: La relacion RL se de…ne por

xRLy si y solo si 8w (xw 2 L , yw 2 L)

Teorema 16 (Myhill-Nerode)

L es regular si y solo si

RL es …nito.

Proof. Sea L tal que la relacion RL es de indice …nito, (es decir el

conjunto RL

es …nito). Sea M = (Q; q 0; F ; ) el automata regular de…nidopor:

Q =

RL:

q 0 = []RL:

F =

[x]RL: x 2 L

:

La funcion : Q ! Q esta de…nida por

a; [x]RL = [xa]RL

Es claro que M es un automata regular, adicionalmente es facil probarque L (M) = L:



2.4 Automatas de doble via: equivalencias xxi

Veamos ahora que si L es un lenguaje regular entonces la relacion RL

es de indice …nito. Sea M un automata regular que reconoce L: Dadax 2 ; podemos de…nir una funcion Mx : Q ! Q de la siguiente manera:

Mx (q ) es igual al estado …nal al que accede M, al procesar el input x;empezando en el estado q

Es facil probar que si Mx = My entonces xRLy: Tenemos entonces que RL

jQjjQj :

2.4.2 Prueba de la equivalencia

En esta subseccion probaremos que la clase de los lenguajes regulares coin-cide con la clase de los lenguajes aceptados por automatas de doble via, esdecir probaremos que todo automata de doble via puede ser simulado porun automata regular.

Dado M un automata de doble via de…nimos una relacion de equivalencia

M de la manera siguiente:

x M y si y solo si 8t 2 (M acepta xt si y solo si M acepta yt)

Teorema 17 (Rabin-Scott-Sheperdson)Dado M; un automata de doble via, existe un automata regular M tal

que L (M) = L

M

:

Proof. Lo que nosotros probaremos es que dado M = (Q; q 0; F ; A ; ) unautomata de doble via, el lenguaje aceptado por M; al que denotaremoscon el simbolo L (M) ; satisface las condiciones impuestas en el enunciadodel teorema de Myhill-Nerode.

Dada x 2 , de…nimos una funcion x : Q ! Q [ f0g de la siguiente

manera:

Si q 6= q 0; se de…ne x (q ) como igual al estado al que accede M;si iniciamos la computacion con x como input, con la cabeza lectoraubicada sobre el caracter …nal de x: Si al imponer estas condicionesiniciales el automata M para con la cabeza lectora ubicada en unaposicion diferente al extremo izquierdo de x; o si M no para del todose de…ne x (q ) = 0:

Si q = q 0; de…nimos de manera similar x (q ) ; la unica diferencia esque en este caso asumimos que en el instante inicial la cabeza estaubicada en el extremo izquierdo de x:

A…rmacion. Dadas x; y 2 ; se tiene que x = y implica x L(M) y:

Note que si n = jQj ; la a…rmacion anterior implica entonces que larelacion de equivalencia L(M)esta constituida por a lo mas (n + 1)n clases.En este punto podemos invocar el teorema de Myhill-Nerode para a…rmarque L (M) es regular.



xxii 2. Automatas regulares

Corolario 18 (tercera cota inferior para P al)Ningun automata de doble via puede reconocer el lenguaje Pal:

El corolario anterior indica que, para reconocer el lenguaje Pal; no es su-…ciente con adicionarle a nuestros automatas basicos la habilidad de moversu cabeza lectora en las dos direcciones. ¿Cuales son los recursos computa-cionales necesarios para reconocer el lenguaje P al?

2.5 Ejercicios capitulo 2

1. (Trabajo de lectura) Investigue la nocion de automata regular contransiciones en vacio.

2. Sea L = f1n01n : n 2 Ng ; use el lema de bombeo para probar que Lno es regular.

3. Sea Reg el conjunto de todos los lenguajes regulares. Pruebe que Reg

es cerrado bajo uniones, intersecciones y complementos.

4. Dado L un lenguaje, se de…ne L como el lenguaje

fw1:::wn : n 2 N y w1;:::;wn 2 Lg

Pruebe que si L es regular, entonces L tambien es regular.

5. Diseñe un algoritmo que resuelva el siguiente problema

El problema de la vacuidad

Input: M, donde M es un automata regular . Problema: Decida si L (M) es diferente de vacio.


El problema de la equivalencia

Input: (M; N ), donde M y N son automatas regulares .

Problema: Decida si L (M) = L ( N ) :


El problema de la …nitud

Input: M, donde M es un automata regular .

Problema: Decida si L (M) es …nito.



This is page xxiiiPrinter: Opaque this

3

Automatas de pila

En este capitulo introduciremos un segundo modelo de computacion: losautomatas de pila. Los automatas de pila se diferencian de los automatasregulares en que los primeros poseen un dispositivo externo de memoria (lapila). Es de esperar que este dispositivo externo de memoria incrementeel poder de computo. Es plausible entonces que los automatas de pila, adiferencia de los automatas regulares, sean capaces de reconocer el lenguajePal:

3.1 Automatas de pila

Un automata de pila es una quintupla M = (Q; ; q 0; F ; ) tal que

1. Q es un conjunto …nito, el conjunto de estados de M:

2. es un conjunto …nito, el alfabeto de la pila.

3. q 0 2 Q es el estado inicial de M:

4. F Q es el conjunto de estados de aceptacion.

5. La funcion de transicion es una funcion de ( Q) en Q

que satisface las siguientes condiciones. Dados a; b 2 , w; u 2 yq; p 2 Q;

(a) Si (a;w;q ) = (u; p) ; se tiene entonces que jjwj jujj 2 f0; 1g



xxiv 3. Automatas de pila

(b) Si (a;w;q ) = (u; p) ; se tiene entonces que o u = w o u @ w ow @ u; (el simbolo u @ w denota que u es un fragmento inicialde w).

(c) Dados x1;x2 2 [ fg, se tiene que

(a;wb;q ) = (wx1x2; p) , (a;ub;q ) = (ux1x2; p)

Es decir, si x es el contenido de la pila, la manera en que x afectala computacion del automata esta completamente determinadapor el ultimo caracter de dicha palabra.

Un automata de pila es como un automata regular al que se le ha adi-cionado un dispositivo externo de memoria, la pila. En cada transiciondel automata de pila este puede: o agregar un caracter a la derecha de lapalabra contenida en la pila, o borrar el ultimo caracter de esta palabra,o dejar invariante el contenido de la pila. Lo que el automata escriba en

la pila puede ser usado en la computacion, aunque en cada instante de lacomputacion el automata solo tenga acceso al ultimo caracter del contenidode la pila. La nocion de con…guracion para automatas de pila es un pocomas compleja que la nocion de con…guracion para automatas regulares.Recuerde que una con…guracion es una descripcion completa del estado dela maquina en cada instante de la computacion. En consecuencia una taldescripcion debe declarar, como minimo, lo que del estado de la maquinaes desconocido para el usuario. Dado que el automata de pila no puede es-cribir, borrar caracteres o marcar caracteres en la cinta de entrada, en todoinstante de la computacion el contenido de la cinta es identico al contenidode la cinta en el instante cero. Esto implica que no necesitamos incluiren nuestra nocion de con…guracion informacion referente al contenido dela cinta. Por otro lado, dado que en cada transicion la cabeza lectora se

mueve una posicion a la derecha, en el instante t la cabeza lectora ha deestar ubicada sobre la celda i-esima de la cinta de entrada. Tenemos en-tonces que lo unico que no conocemos de entrada, respecto al estado de lamaquina, es su estado interno y el contenido de la pila.

De…nición 19 Dado M = (Q; ; q 0; F ; ) un automata de pila, una con- …guracion de M es una tripla (w; q; i) 2 Q N:

Dado x = x1:::xn 2 ; la computacion de M con input x es una secuen-cia ordenada y …nita de con…guraciones (; q 0; 1) ; (w1; p1; 2) :::; (wn; pn; n + 1)que satisface la siguiente condicion: para todo i n se tiene que

(xi; wi1; pi1) = (wi; pi)

De…nición 20 Dado M = (Q; ; q 0; F ; ) un automata de pila, dado x =x1:::xn 2 y dada

(; q 0; 1) ; (w1; p1; 1) :::; (wn; pn; n + 1)



3.1 Automatas de pila xxv

la computacion de M con input x; diremos que M acepta x si y solo si wn = y pn 2 F:

De…nición 21 Dadas z; v 2 , dada x 2 y dados q; p 2 Q el simbolo(z; q ) Mx (v; p) indica que si inicializaramos el automata M con x comoinput, q como estado interno y z como contenido de la pila, al terminar de leer x el automata M estaria en el estado p y con v como contenido de la pila.

Teorema 22 Los automatas de pila son incapaces de reconocer El lenguaje P al.

Proof. Suponga que M = (; ; Q ; F ; q 0; ) es un automata de pila quereconoce el lenguaje P al. Suponga ademas que F = f p1;:::;pN g y quetodos los estados en F son accesibles. Dado que el conjunto es in…nito,existen x; y 2 y existe i; j N tales que:

1. x 6= y:

2. (; q 0) Mxx (; pi) :

3. (; q 0) Myy (; pi)

4. (; pi) Myy (; pj ) :

5. xxyy =2 Pal:

Dado que xxxx y yyyy son palindromos, se tiene que pi; pj 2 F: Noteque:

(; q 0) Mxxyy (; q 2)

Y esto implica que el automata M acepta la palabra xxyy; pero dadoque xxyy =2 Pal; podemos concluir que M no reconoce el lenguaje Pal:

Aunque los automatas de pila (deterministicos) son incapaces de recono-cer Pal; es facil probar que los automatas de pila son estrictamente maspotentes que los automatas regulares. Note primero que todo automataregular es un automata de pila que no usa la pila. Por otro lado es facilveri…car que el lenguaje P al = f1n01n : n 2 Ng puede ser reconocido porun automata de pila, por otro lado es facil veri…car (usando el lema debombeo) que el lenguaje P al no es regular

Ejercicio 23 1. Pruebe que P al no es regular.

2. Pruebe que P al puede ser reconocido por un automata de pila.



xxvi 3. Automatas de pila

3.2 Automatas de pila no deterministicos ylenguajes libres de contexto

En esta seccion estudiaremos los automatas de pila no deterministicos. Adiferencia de lo que sucede en el caso regular, el no-determinismo incre-menta estrictamente el poder de computo de los automatas de pila. Comoveremos mas adelante el lenguaje P al puede ser reconocido por un au-tomata de pila no deterministico, recuerde que P al no puede ser reconocidopor un automata de pila deterministico.

Un automata de pila no deterministico es una quintupla M = (Q; ; q 0; F ; )tal que

1. Q es un conjunto …nito, el conjunto de estados de M:

2. es un conjunto …nito, el alfabeto de la pila.

3. q 0 2 Q es el estado inicial de M:

4. F Q es el conjunto de estados de aceptacion.

5. La relacion de transicion es un subconjunto de ( Q) ( Q) que satisface las siguientes condiciones. Dados a 2 ,w;u;v 2 y q; p 2 Q

(a) Si (a;w;q;u;p) 2 se tiene entonces que jjwj jujj 2 f0; 1g

(b) Si (a;w;q;u;p) 2 se tiene entonces que o u = w o u @ w ow @ u:

(c) Dados x1; x2 2 [ fg, se tiene que

(a;wb;q;wx1x2; p) , (a;ub;q;ux1x2; p) 2

Es decir, si x es el contenido de la pila, la manera en que x afectala computacion del automata esta completamente determinadapor el ultimo caracter de dicha palabra.

Las nociones de con…guracion, computacion y aceptacion se de…nen demanera similar a como se de…nieron en el caso deterministico.

Ejercicio 24 Da…na de manera precisa las nociones de con…guracion, com-putacion y aceptacion para automatas de pila no deterministicos.

De…nición 25 Dado L diremos que L es libre de contexto si y solo

si existe un automata de pila no deterministico que reconoce L:Proposición 26 P al es libre de contexto.

Proof. Considere el automata de pila M = (Q; ; q 0; F ; ) de…nido por:



3.2 Automatas de pila no deterministicos y lenguajes libres de contexto xxvii

1. Q = fq e; q b; q rg

2. = :

3. q 0 = q e:

4. F = fq bg

5. es la funcion de Q en Q de…nida por

(a) Suponga que x = ya, en este caso se tiene que (a;x;q e) =f(xa;q e) ; (y; q b)g :

(b) Suponga que x = yb con b 2 fag ; en este caso se tiene que (a;x;q e) = f(xa;q e) ; (y; q r)g :

(c) Suponga que x = ya, en este caso se tiene que (a;x;q b) =f(y; q b)g :

(d) Suponga que x = yb con b 2 fag ; en este caso se tiene que (a;x;q b) = f(y; q r)g :

(e) Suponga que x = ya, en este caso se tiene que para todo b 2 vale la ecuacion (b;x;q r) = f(y; q r)g :

(f) Suponga que x = ; en este caso se tiene que (b;;q r) =f(; q r)g :

Es facil veri…car que el automata M reconoce el lenguaje P alQue el lenguaje P al sea libre de contexto no debe hacernos pensar que

todo lenguaje es libre de contexto, recuerde que existen lenguajes no com-putables y que los lenguajes libres de contexto son computables. Tampocodebemos pensar que todo lenguje computable es libre de contexto. Es posi-ble establecer un lema de bombeo para lenguajes libres de contexto, el cual

enuciaremos sin prueba a continuacion (la prueba se deja como trabajo delectura para el lector).

Lema 27 (lema de bombeo para lenguajes libres de contexto)Dado L un lenguaje libre de contexto existe K 2 N tal que si x 2 L y jxj

K , entonces la palabra x puede escribirse como uvwxy; satisfaciendose que

1. jvxj 1:

2. jvwxj K:

3. uviwxiy 2 L:

El lema de bombeo, (al igual que el lema de bombeo para lenguajes

regulares), nos permite probar de ciertos lenguajes,que estos no son libresde contexto. Veamos un ejemplo.

Sea el lenguaje f1 p : p es primog ; es claro que el lenguaje es com-putable (en algun sentido).



xxviii 3. Automatas de pila

Corolario 28 El lenguaje no es libre de contexto.

Proof. Suponga que es libre de contexto. Sea K como en el enunciado

del lema de bombeo y sea R un primo mayor que K . Considere la palabra1R: El lema de bombeo a…rma que existen u;v;w;x;y 2 tales que1R = uvwxy y tales que dado i 2 la palabra uviwxiy tambien pertenecea : Sea xi la palabra uviwxiy: Note que jxij es igual a R + (i 1) (jvxj) :Dado i = R + 1; se tiene que jxij = R (1 + jvxj) : Tenemos entonces quexi 2 y que por lo tanto R (1 + jvxj) = jxij es un numero primo, pero estoes imposible dado que R; 1 + jvxj 1

El corolario anterior muestra que los automatas de pila no son omnipo-tentes, es mas, el corolario anterior muestra que los automatas de pilatiene un poder de computo tan bajo que ni siquiera son capaces de re-alizar veri…caciones aritmeticas elementales (note que decidir el lenguaje; corresponde a reconocer numeros primos).


1. (trabajo de lectura) Investigue la nocion de gramatica libre de con-texto y su relacion con los lenguajes libre de contexto.

2. (trabajo de lectura) Investigue la nocion de automata de cola (queueautomata) y su relacion con los automatas de pila. Decida si ellenguaje P al puede ser decidido por un automata de cola.


Parsing problem para lenguajes libres de contexto

Input: (M; x) ; donde M es un automata de pila no determin-istico y x 2 :

Problema: Decida si x es aceptado por M:

Nota. Aunque M es en si mismo un procedimiento que podriaser usado para decidir si M acepta x; el problema con M es queeste podria ser un procedimiento no determinista. Lo que se pide eneste ejercicio es diseñar un procedimiento determinista que resuelva elparsing problem (Ayuda. Investigue acerca del algoritmo de Earley).

4. Pruebe el lema de bombeo para lenguajes libres de contexto.

5. (Lema de Ogden) Sea w una palabra y sea p jwj ; una p-marcacion

de w es una escogencia de al menos p posiciones de w: Pruebe que siL es libre de contexto, existe entonces un numero p 0 tal que paratoda palabra w 2 L de longitud al menos p y para toda p-marcacionde w existen palabras u;v;x;y y z para las cuales se tiene que



3.3 Ejercicios capitulo 3 xxix

w = uvxyz.

x contiene al menos una posicion marcada.

O u y v contienen cada uno al menos una posicion marcada, oy y z contienen cada uno al menos una posicion marcada.

vxy contiene a lo mas p posiciones marcadas.

Para todo i 0 se tiene que uvixyiz 2 L:

6. Use el lema de Ogden para probar que el lenguaje

aibj ckdl : i = 0 o j = k = l

no es libre de contexto.



xxx 3. Automatas de pila



This is page xxxiPrinter: Opaque this

4

Maquinas de Turing

En este capitulo introduciremos y estudiaremos el non plus ultra de losmodelos de computacion: el modelo de maquina de Turing.

Advertencia. A partir de este momento el simbolo log(n) denotara laparte entera del logaritmo en base dos de n:

4.1 Maquinas de Turing con una cinta

Para empezar introduciremos el modelo de maquinas de Turing de una solacinta. Podemos pensar en una maquina de Turing de una sola cinta (paraabreviar, a este tipo de maquinas las llamaremos simplemente maquinasdeTuring) como en un automata regular dotado con una cabeza que puedemoverse en las dos direcciones y que ademas puede escribir en la cinta deentrada. Dado que una maquina de Turing puede escribir en la cinta deentrada, una tal maquina puede usar la cinta de entrada como dispositivoexterno de memoria. Las maquinas de Turing son maquinas que combinanlas habilidades de los automatas de pila y de los automatas de doble via.Es de esperar que esta combinacion de habilidades de como resultado untipo de automata mas poderoso.

De…nición 29 Una maquina de Turing es una sextupla M = (Q; ; q 0; F ; ; A)tal que:

1. Q es un conjunto …nito, el conjunto de estados de la maquina.



xxxii 4. Maquinas de Turing

2. es un conjunto …nito, el alfabeto de la maquina que satisface [fg .

3. q 0 2 Q es el estado inicial de la maquina.

4. F Q es el conjunto de estados …nales de la maquina.

5. La funcion de transicion es una funcion de Q en Q f;; !g :

6. F A Q y si el estado interno de la maquina pertenece a A la maquina para.

Dados a; b 2 ; q; p 2 Q y h 2 f;; !g, si (a; q ) = (b;p;h), cadavez que la maquina se encuentre en el estado q leyendo el caracter a; la

maquina borrara a; escribira a cambio el caracter b (reemplazara a por b),pasara del estado q al estado p y se movera a la derecha, a la izquierda opermanecera en su lugar dependiendo de quien sea h (! indica movimientoa la derecha, indica movimiento a la izquierda y indica que la cabezade la maquina permanece sobre la misma celda, i.e. no se mueve).

Ejemplo 30 Considere el lenguaje de…nido por

f1m : n es primog

Recuerde que en el capitulo 3 probamos, usando el lema de bombeo para lenguajes libres de contexto, que no puede se reconocido por un automata de pila no deterministico. No es facil, pero es posible, diseñar una maquina

de Turing que reconozca el lenguaje :

Del ejempplo anterior tenemos que existen lenguajes que no son libresde contexto pero que pueden ser reconocidos por maquinas de Turing.

De…nición 31 Diremos que L es Turing-computable si y solo si existe una maquina de Turing que reconoce L:

De…nición 32 Una con…guracion de M = (Q; ; q 0; F ; ; A) es una tripla (w; q; i) tal que

1. w 2 (es el contenido de la cinta)

2. q 2 Q (es el estado interno de la maquina).

3. i jwj (es la posicion de la cabeza lectora).



4.1 Maquinas de Turing con una cinta xxxiii

4.1.1 La tesis de Church y la jerarquia de Chomsky

Hasta el momento hemos estudiado esencialmente tres modelos de com-

putacion: automatas regulares, automatas de pila y maquinas de Turing.Considere los siguientes conjuntosComp = fL : L es computablegReg = fL : L es regulargLC = fL : L es libre de contextogT C = fL : L es Turing-computablegAunque el primero de estos conjuntos no esta de…nido de manera formal

podemos aceptar su existencia y conformarnos por ahora con una de…nicioninformal: un lenguje L es computable si y solo si existe un procedimientomecanico …nitista (una maquina discreta) capaz de decidir L:

Da los conjuntos antes de…nidos sabemos que

Reg $ LC $ T C Comp

La tesis de Church a…rma que Comp = T C: La tesis de church no es unaa…rmacion matematica suceptible de prueba, dado que uno de los terminosinvolucrados en la tesis (el termino Comp) no posee una de…nicion formal.La tesis de Church puede ser entendida de diversas maneras:

Como una de…nicion formal (aunque posiblemente inadecuada de lanocion de computabilidad).

Como una a…rmacion semiotica la cual a…rma que la nocion intu-itiva de computabilidad es capturada completamente por un simbolomatematico: Turing-computabilidad.

Como una a…rmacion pragmatica que nos permite evitar las inmensas

di…cultades involucradas en el diseño de una maquina de Turing queresuelva un problema concreto no trivial: la tesis de Church a…rmaque si usted es capaz de exhibir un procedimiento, que quepa llamarmecanico y …nitista, que resuelve el problema L; usted ha probadoque existe una maquina de Turing que resuelve L:

En lo que queda del texto usaremos convenientemente la perspectivapragmatica.

Existe fuerte evidencia a favor de la tesis de Church, tal evidencia sereduce esencialmente a los siguientes hechos:

1. No se conoce un problema que sea calculable en algun sentido y queno sea Turing-calculable.

2. De toda nocion formal de computabilidad propuesta hasta la fechase ha podido probar que esta embebida en la nocion de Turing-computabilidad.



xxxiv 4. Maquinas de Turing

Existen muchos otras clases de lenguajes computables (ademas de los tresestudiados hasta el momento) que son importantes desde el punto de vistateorico. Una tal clase es la clase de los lenguajes sensitivos al contexto,

los cuales pueden ser caracterizados a partir de la nocion de automata linealmente acotado.

De…nición 33 Un automata linealmente acotado M es una septupla

(Q; ; q 0; F ; ; A ; f )

tal que





5. La funcion de transicion es una funcion de Q en Q f;; !g :


7. f es una funcion lienal tal que, cuando la maquina M procesa un input x de tamaño n; ella solo puede usar las celdas ocupadas por los caracteres de x y f (n) celdas adicionales localizadas a la derecha del ultimo caracter de x:

Tenemos entonces que un automata linealmente acotado es una maquinade Turing de una sola cinta a la que se le impone una condicion adi-cional, referente esta a la cantidad de espacio de trabajo disponible para lamaquina.

De…nición 34 Dado L diremos que L es un lenguaje sensitivo al contexto si y solo si existe un automata linealmente acotado M tal que Mreconoce L:

Sea SC = fL : L es sensitivo al contextog :

Teorema 35 SC $ T C:

Del teorema anterior (y aceptando la tesis de Church) tenemos que

Reg $ LC $ SC $ T C = Comp

Esta jerarquia de lenguajes computables (de lenguajes formales) se leconoce como la Jerarquia de Chomsky .



4.1 Maquinas de Turing con una cinta xxxv

4.1.2 Turing computabilidad de los lenguajes libres de contexto

En esta breve subseccion probaremos que todo automata de pila puede sersimulado por una maquina de Turing, esto implica en particular que todolenguaje libre de contexto es Turing-computable.

Sea M = (Q; ; q 0; F ; ) un automata de pila deterministico. Construire-mos una maquina de Turing T (M) = (Q; ; q 0; F ; ; A) capaz de simularel automata M: La maquina M esta dada por:

1. Q = Q [ f!q a : q 2 Q y a 2 g [ fq : q 2 Qg :

2. = [ f(a; 1) : a 2 g [ f#g :

3. La funcion esta de…nida por:

(a) Para todo a 2 f#g y para todo q 2 Q se tiene que (a; q ) =

((a; 1) ; !q a; !) :(b) Para todo a; b 2 y para todo q 2 Q se tiene que (a; !q b ) =

(a; !q b ; !) :

(c) Para todo a 2 y para todo q 2 Q; si $ denota que la celdaactual no contiene caracteres y si (b;wa;q ) = (wz1z2; p), setiene que ($; !q b ) = (z2; p ; ) :

(d) Para todo a 2 y para todo q 2 Q se tiene que (a; q ) =(a; q ; ) :

(e) Para todo a 2 y para todo q 2 Q se tiene que ((a; 1) ; q ) =(a;q; !) :

(f) Para todo q 2 Q; ($; q ) = halt; (esto es, la maquina termina

la computacion en este punto).(g) Para todo q 2 Q y para todo a 2 se tiene que ($; !q a) =

($; !q a; !) :

(h) Para todo q 2 Q; ($; q ) = ($; q ; ) :

Dado x = x1:::xn un input de M; supondremos que la maquina T (M)es inicializada en el estado q 0; con el input x1x2:::xn# escrito en el extremoizquierdo de la cinta. El simbolo # sera usado para indicar el …nal del inputy el comienzo de la pila, la maquina T (M) usara las celdas a la derechadel simbolo # para simular la pila de M: Una transicion

(wa;q;i) !M (wz1z2; p ; i + 1)

sera simulada por la siguiente secuencia de transiciones

(x#wa;q;i) ! (x1:::xi1 (xi; 1) xi+1:::xn#wa; !q xi ; i + 1) ! :::



xxxvi 4. Maquinas de Turing

! (x1:::xi1 (xi; 1) xi+1:::xn#wa; !q xi ; n + 1 + jwj) !

(x1:::xi1 (xi; 1) xi+1:::xn#wz1z2; p ; n + 1 + jwj + ) ! ::::

! (x1:::xi1 (xi; 1) xi+1:::xn#wz1z2; p ; i) !

(x1:::xi1xixi+1:::xn#wz1z2; p ; i + 1)

donde z1z2 2 [ fg y 2 f1; 0; 1g : El valor de esta determinadopor la siguiente regla

Si z1 = a y z2 6= ; entonces = 1:

Si z1; z2 = ; entonces = 1:

Si z1 = a y z2 = ; entonces = 0:

Note que si M es un automata deterministico, la simulacion de la com-

putacion del automata Men el input x consta de a lo mas 2n2 transiciones.Con lo anterior hemos probado el teorema que enunciamos a continuacion.

Teorema 36 Si M es un automata de pila deterministico, la maquina T (M) realiza a lo mas 2n2 transiciones al simular la computacion del automata M en el input x:

El caso de automatas de pila no deterministicos es tecnicamente mascomplicado, dado que tenemos que arreglarnoslas para simular el no-determinismo.Aun asi es posible probar el siguiente teorema

Teorema 37 (Earley)Dado M un automata de pila no deterministico, existe una maquina de

Turing T (M) y existe C 2 N tales que la maquina T (M) es capaz de simular el automata M, ademas se tiene que la maquina T (M) realiza a

lo mas C jxj3 transiciones al simular la computacion del automata M en el input x:

4.2 Tiempo de computo: analisis de algoritmos

Los practicantes de la algoritmia saben que

Para dar por resuelto un problema

no basta con conocer un algoritmo

que resuelva el problema

Esto es asi dado que no todo algoritmo puede ser usado en la practica.algunos algoritmos requieren recursos computacionales de los cuales, en



4.2 Tiempo de computo: analisis de algoritmos xxxvii

la practica, no es posible disponer. Usualmente los algoritmos malos loson o porque requieren demasiada memoria o porque requieren tiempos decomputo astronomicos cuando se procesan inputs grandes.

Dado un algoritmo, es necesario analizar el algoritmo y determinar desdeel analisis teorico si este es suceptible de ser usado en la practica. El primeraspecto que debe analizarse de un algoritmo es su tiempo de computo. Eltiempo de computo mide la velocidad del algoritmo. A cada algoritmo esposible asociarle una funcion, la funcion tiempo de computo, la cual midela manera como el tiempo de computo escala respecto al tamaño de losinputs. La tesis de Church justi…ca el que basemos nuestro analisis dealgoritmos en la nocion de maquina de Turing.

De…nición 38 Dada M una maquina de Turing, la funcion tiempo de computo de M es la funcion T M : N ! N[f1g de…nida por:

1. Dado x 2 un input de M se de…ne T M

(x) como el numero de transiciones que realiza la maquina M al procesar el input x: Si la maquina no para, es decir si el numero de transiciones es in…nito,de…nimos T M (x) = 1:

2. Dado n 2 N se de…ne T M (n) = maxx:jxj=n fT M (x)g :

Dados dos algoritmos (o, lo que es lo mismo, dos maquinas de Turing)M y N que resuelven el mismo problema L; es importante poder decidirdesde la teoria cual de los dos algoritmos es el mas e…ciente. Para ellopodemos intentar comparar el tiempo de computo de los dos algoritmos.Esto nos obliga a de…nir una nocion de orden apropiada para el conjuntoNN: Esta nocion de orden debe tener un caracter asintotico, dado que los

inputs grandes son los inputs para los cuales es importante que el algoritmose comporte de manera e…ciente. En cierto sentido los inputs pequeñosson pan comido, y todo algoritmo puede dar cuenta de ellos de maneraapropiada (los inputs pequeños se pueden resolver a mano).

De…nición 39 (notacion asintotica)

1. Dadas f; g 2 NN; se tiene que f 2 O (g) si y solo si existen C; D 2 Ntales que para todo n C se satisface la desigualdad f (n) Dg (n) :

2. Dadas f; g 2 NN; se tiene que f 2 (g) si y solo si g 2 O (f ) :

La nocion de orden que suele usarse para comparar el tiempo de computode dos algoritmos esta dada por

M M si y solo si T M 2 O (T M)



xxxviii 4. Maquinas de Turing

4.3 Lenguajes no computables

En el capitulo 1 presentamos un argumento informal que garantizaba la

existencia de problemas no computables. En aquel momento era imposiblepresentar un argumento formal, dado que no contabamos con una nocionformal de computabilidad. A estas alturas, contando como lo hacemos conla nocion de Turing-computabilidad, podriamos formalizar el argumento.No vamos a hacerlo dado que, aunque el argumento garantiza que existeuna in…nidad no enumerable de problemas no computables, el argumentono nos permite exhibir un problema concreto no computable. En estaseccion de…niremos un problema concreto (el problema de la parada) delcual mostraremos que es no Turing-computable (y entonces no computablesi la tesis de Church es cierta).

De…nición 40 El problema de la parada es el problema de…nido por

Input: (M; x) donde M es una maquina de Turing y x es un input de M.

Problema: Decida si la maquina M para al procesar el input x; estoes decida si T M (x) 1:

Teorema 41 El problema de la parada no es computable.

Proof. Suponga que N es una maquina de Turing que resuelve el problemade la parada. Esto quiere decir que dada M una maquina de Turing, si a N

se le presenta como input el par

z}|{ M ; x

, (donde

z}|{ M es una codi…cacion

adecuada de la maquina M); entonces sucede lo siguiente

Si M para al procesar el input x; la maquina N imprime 1:

Si M no para al procesar el input x; la maquina N imprime 0:

Podemos diseñar una maquina de Turing, llamemosla N ; tal que

Si N

z}|{ M ;

z}|{ M

= 1; entonces la maquina N al procesar el

input

z}|{ M

entra en un bucle in…nito.

Si N

z}|{

M ;

z}|{ M

= 0; entonces N

z}|{

M

= 0:

Podemos preguntarnos que pasa si a la maquina N le presentamos el

input

z}|{ N ;

z}|{ N

: Note que:



4.4 Maquinas universales xxxix

Si N z}|{

N

= 0 = N

z}|{ N ;

z}|{ N

: Entonces la maquina N

no para al procesar el input z}|{ N

; pero esto es absurdo, dado quela maquina N si para al procesar el input

z}|{ N y al …nal de esta

computacion imprime 0:

Si N

z}|{ N ;

z}|{ N

= 1; entonces la maquina N si para al procesar

el input z}|{

N ; pero esto es absurdo dado que en este caso la maquina N , de acuerdo a su diseño, entra en un bucle in…nito.

Es claro entonces que hemos llegado a una contradiccion insalvable, ydeber ser claro para el lector que la causa de esta contradiccion fue suponerque existe una maquina N que supuestamanente resuelve el problema de laparada Podemos entonces concluir que no existe una maquina de Turing

que resuelva el problema de la parada, (i.e. el problema de la parada noes Turing-computable, y si aceptamos la tesis de Church el problema de laparada no es computable).

4.4 Maquinas universales

Las maquinas que hemos introducido hasta el momento tienen la caracter-istica de ser maquinas de un solo proposito, cada una de las maquinas ycada uno de los automatas que hemos introducido y estudiado sirven, enprincipio, para resolver un unico problema. Esto no se corresponde a laintuicion que tenemos de maquinas computadoras las cuales son maquinas

multiproposito, es decir maquinas que pueden ser programadas para re-solver una gran variedad de problemas.Uno de los resultados fundamentales de la teoria de maquinas de Turing

a…rma que existe una maquina de Turing U , que llamaremos universal, quepuede ser usada para simular cualquier otra maquina de Turing, y entonces(de acuerdo a la tesis de Church) U es una maquina que puede ser usadapara reconocer cualquier lenguaje computable, (o, lo que es lo mismo, pararesolver cualquier problema computacionalmente soluble).

Fijemos un alfabeto : Diremos que U es una maquina de Turing -universal si y solo si U puede ser usada para reconocer todo -lenguajedecidible.

Lema 42 Dado existe K 2 N tal que todo -lenguaje decidible puede

ser reconocido usando una maquina de Turing M = (Q; ; q 0; F ; ) tal que 1. jQj K:

2. = [ fg :



xl 4. Maquinas de Turing

Note que si M es una maquina de Turing como en el enunciado dellema anterior la maquina M puede ser descrita usando una -palabra delongitud h (jj + K ) ; donde h es una funcion conveniente que no depende

ni de ni de K: Dada M una maquina de Turing usaremos el simbolo z}|{ M para indicar el codigo de M:

Teorema 43 Dado un alfabeto, existe una maquina de Turing U la cual es -universal.

Proof. En la prueba de este teorema usaremos la version pragmatica dela tesis de Church, lo cual nos permitira evitar los engorrosos detalles in-volucrados en la construccion explicita de U ; aun asi es importante anotarque es posible presentar una construccion explicita de U ; es un excelenteejercicio para el lector intentar desarrollar una tal construcion.

Sea = [ fg y sea Turing el -lenguaje de…nido por

Turing = z}|{

M x : M es una -maquina de Turing, x 2 y M acepta x

Es claro que el lenguaje Turing es decidible en el sentido en que existeun procedimiento mecanico para reconocer Turing (construya M usando z}|{ M y veri…que que

z}|{ M acepta x). La tesis de Church a…rma que existe

una maquina de Turing, llamemosla U , que reconoce el lenguaje Turing:Note que U puede ser usada para reconocer todo -lenguaje decidible.Sea L un -lenguaje decidible. Considere el siguiente procedimiento.

1. Dado que L es un -lenguaje decidible, existe una maquina de Turing

z}|{ M que decide L; construya una tal M y construya entonces

z}|{ M

(el codigo de z}|{ M ):

2. Dada x una instancia de L; construya z}|{

M x:

3. Use la maquina U en el input z}|{

M x:

Note que U acepta z}|{

M x si y solo si M acepta x si y solo si x 2L: Tenemos entonces que la maquina U puede ser efectivamente usadapara reconocer todo -lenguaje decidible (en este sentido la maquina esuniversal)

El teorema anterior es un paso adelante, pero no es el paso …nal, dadoque aun necesitamos contar con una maquina por cada alfabeto (antes

necesitabamos contar con una maquina por cada problema).Diremos que una maquina de Turing U es una maquina universal si y solo

si U puede ser usada para reconocer todo lenguaje decidible. Probaremosque existe una maquina de Turing universal, la idea se basa en que si …jamos



4.4 Maquinas universales xli

un alfabeto ; podemos recodi…car todo lenguaje L como un -lenguaje, esdecir dado L un lenguaje en un alfabeto arbitrario ; existe una biyeccioncomputable ! de en tal que L es decidible si y solo si ! (L) ;

la imagen de L, es decidible.

Teorema 44 Existe una maquina de Turing U la cual es universal.

Proof. Para empezar …jaremos un alfabeto (por ejemplo = f0; 1g).Sea L un lenguaje decidible en un alfabeto arbitrario y sea U unamaquina de Turing -universal. Mostraremos que es posible usar U paradecidir el lenguaje L: Considere el siguiente procedimiento:

Dada x una instancia de L

1. Calcule ! (x) :

2. Use U para decidir si ! (x) 2 ! (L) :

Note que x 2 L si y solo si ! (x) 2 ! (L) si y solo si U acepta! (x) :

Tenemos entonces que la maquina U es universal dado que puede serusada para decidir todo lenguaje decidible (y entonces para resolver todoproblema computable). Si tomamos U igual a U obtenemos la prueba delteorema

Algunos lectores pueden sentirse decepcionados con el teorema anterior,dado que a la maquina universal U es necesario ayudarle (en cierto sentido)con los calculos que pretendemos que ella realize, especi…camente dado Lun lenguaje computable en un alfabeto arbitrario , a la hora de usar U para decidir si x 2 L es necesario

1. Calcular ! (x) :

2. Diseñar una maquina M que decida ! (L) :

3. Construir z}|{

M el codigo de M:

El lector debe notar que

1. La maquina M se diseña una unica vez, es decir hecho el diseño deM al momento de decidir si x pertenece a L; no es necesario repetirel trabajo de diseño para decidir de otra palabra y si ella perteneceo no a L:

2. El calculo de z}|{

M se realiza una unica vez.

3. El calculo de ! (x) es computacionalmente trivial.

Note que al usar un computador digital para decidir si una palabra xpertenece a un lenguaje L es necesario:



xlii 4. Maquinas de Turing

1. Diseñar un algoritmo A que sea capaz de reconocer L:

2. Implementar el algoritmo A en un lenguaje de programacion ade-

cuado, esto es calcular z}|{ A un codigo computacional de A:

3. Calcular una codi…cacion adecuada de la instancia x; esto es calcular! (x), donde es el alfabeto de L y es el alfabeto de la maquina(por ejemplo f0; 1;g ; o por ejemplo el codigo ASCII).

Tenemos entonces que:

U es el hardware.

M es el algoritmo.

z}|{ M es la implementacion de M en un lenguaje de programacionpre…jado.

! (x) es el codigo computacional de x1 :


1. Pruebe el lema 42.

2. Diseñe una maquina de Turing que reconozca el lenguje P al en tiempoO

n2

:

3. Diseñe explicitamente una maquina de Turing universal.

4. Si fracaso con el desarrollo del ejercicio anterior, intente lo siguiente:diseñe una maquina M que sea capaz de simular toda maquina deTuring con a lo mas dos estados y con alfabeto interno f0; 1;g :

5. Si fracaso con el ejercicio anterior intente algo aun mas facil: diseñeuna maquina de Turing capaz de simular a todo automata de pila.

6. (trabajo de lectura) Investigue la nocion de reduccion entre lenguajescombinatorios y sus aplicaciones en la teoria de la computabilidad(no-computabilidad).

1

Note que el calculo de !

(x) es inevitable en muchos casos, dado que a uncomputador no le podemos introducir cualquier objeto como input de un programa, por

ejemplo si x es un grafo, como input del programa que estemos usando introduciremosm (x) ; la matriz de adyacencia de x; o I (x) la matriz de incidencia o cualquier otro

codigo combinatorio-computacional del grafo x:



4.5 Ejercicios capitulo 4 xliii

7. Decida si el siguiente problema es o no computable, en caso de serlodiseñe un algoritmo que lo resuelva, en caso de no serlo pruebe queel problema no es computable.

El problema de la vacuidad

Input: M, donde M es un automata de pila .

Problema: Decida si L (M) es diferente de vacio.


El problema de la equivalencia

Input: (M; N ), donde M y N son automatas de pila .

Problema: Decida si L (M) = L ( N ) :


El problema de la …nitud

Input: M, donde M es un automata de pila .

Problema: Decida si L (M) es …nito.



xliv 4. Maquinas de Turing



This is page xlvPrinter: Opaque this

5

Una introduccion a la complejidadcomputacional

Este capitulo pretende ser una breve introduccion a la Teoria de la com-plejidad computacional. La complejidad computacional (o la Teoria de lacomplejidad computacional) intenta dar respuestas al siguiente tipo de pre-gunta: ¿dado L un lenguaje computable, cuales son los recursos computa-cionales requeridos para resolver el problema L? La complejidad computa-cional parte del hecho de que todo problema tiene un grado de di…cultadintrinseco, que le es propio, y que por lo tanto toda solucion computa-cional de un problema algoritmico requiere una cantidad minima de recur-

sos computacionales. El concepto de recurso computacional es un conceptoinformal y multifacetico. Recursos computacionales pueden ser: tiempo decomputo, espacio de memoria, habilidades del hardware, recursos aleatorios(bits aleatorios). A lo largo del libro hemos analizado, en cierto sentido, lacomplejidad computacional (esto es: la di…cultad intrinseca) del problemaPal: Hemos establecido cotas inferiores tales como:

1. No es posible resolver P al usando automatas regulares (una cabezalectora unidireccional).

2. No es posible resolver P al usando automatas de pila deterministicos(cabeza lectora unidireccional + dispositivo externo de memoria).

3. No es posible resolver P al usando automatas de doble via (una cabezabidireccional).

Reciprocamente, hemos establecido cotas superiores tales como:



xlvi 5. Una introduccion a la complejidad computacional

Es posible resolver P al usando un automata de pila no determinis-tico (cabeza lectora unidireccional + dispositivo externo de memoria+no-determinismo).

Este tipo de resultados, cotas inferiores y cotas superiores, es el tipode resultados que la complejidad computacional intenta establecer cadavez que se analiza un problema computable. Una cota superior es simple-mente un algoritmo que resuelve el problema. Dado L un problema y dadoM un algoritmo, si M resuelve L entonces los recursos usados por M sonsu…cientes para resolver L: Establecer una cota superior consiste precisa-mente en probar que cierta cantidad de recursos (usados inteligentemente),son su…cientes para resolver L:

el establecimiento de cotas inferiores (tal cantidad de recursos es insu…-ciente, por lo tanto algo mas es necesario), presupone un analisis teoricotanto del problema como de las potencialidades de los recursos en cuestion.Algunas cotas inferiores puden opbtenerse por dos caminos diferentes

Como corolarios de resultados generales concernientes al modelo decomputacion (o conjunto de modelos con acceso a cierta cantidad derecursos) tales como: el lema de bombeo para automatas regulares,la simulabilidad mediante automatas regulares de los automatas reg-ulares no deterministicos y de los automatas de doble via.

Via argumentos combinatorias ad hoc, tales como: el argumento desecuencias de cruce que usaremos en este capitulo para probar queP al requiere tiempo cuadratico cuando se consideran maquinas deTuring de una cinta (45); el argumento combinatorio elemental usadoal probar que P al requiere no-determinismo cuando se consideranautomatas de pila.

En este capitulo presentaremos algunas cotas inferiores y algunas cotassuperiores referentes al lenguaje Pal; y referentes a diferentes modelos demaquina de Turing.

5.1 Una cota inferior para Pal: secuencias de cruce

En esta seccion probaremos una cota inferior para Pal; especi…camente pro-baremos que toda maquina de Turing de una sola cinta capaz de reconocerel lenguaje P al tiene un tiempo de computo por lo menos cuadratico. Laprueba es un argumento combinatoria elemental que se basa en la nocionde secuencia de cruce, nocion que ha sido utilizada con exito para obtener

otras cotas inferiores (vea [2], [11]).

Teorema 45 (Teorema de Hennie)P al requiere tiempo

n2

en una maquina de Turing de una sola cinta



5.1 Una cota inferior para Pal: secuencias de cruce xlvii

Proof. Sea M una maquina de Turing de una sola cinta que reconoce ellenguaje Pal: Considere el subconjunto de P al de…nido por

nx12jxjx : x 2 oDado x12jxjx 2 y dado i 4 jxj ; de…nimos C Mi (x) ; la i-esima se-

cuencia de cruce (crossing sequence) asociada a x y a M de la siguientemanera: C Mi (x) es la secuencia ordenada de estados a los que accede Mcada vez que, procesando el input x12jxjx; cruza la linea que separa la celdai-esima y la celda i + 1-esima. Dado x 2 ; de…nimos C M (x) como

C Mi (x) : jxj i 3 jxj

La observacion fundamental es que dados x; y 2 n; si x 6= y entonces

C M (x) \ C M (y) = ?. Suponga que existe i 2 fn; n + 1; :::; 3ng tal queC Mi (x) = C Mi (y) ; sea z el pre…jo de longitud i de la palabra x12jxjx y sea

w el su…jo de longitud 4n i de la palabra y12jxjy: Es facil convencerse delos siguientes hechos

1. zw =2 P al

2. M acepta la palabra zw

Lo anterior implica que M no puede reconocer el lenguaje Pal; contradi-ciendo con ello la hipotesis inicial. Es claro que la hipotesis auxiliar que nosha llevado a esta contradiccion es suponer que existen n 2 N y x; y 2 n

tales que x 6= y y C M (x) \ C M (y) 6= ?.Dado x 2 el simbolo tx denotara la cantidad mini2fjxj;:::;3jxjg

C Mi (x)

y dado n 2 N el simbolo tn denotara la cantidad maxx2n ftxg :

A…rmacion. tn 2 (n) :Note que la a…rmacion anterior implica que el tiempo de computo de Mes

n2

: Para terminar la prueba es su…ciente probar la a…rmacion.

Note que el numero de M-secuencias de cruce de longitud menor o igualque t esta acotado superiormente por

tXi=0

jQMji=

jQMjt+1 1

jQMj 1

Recuerde que dado n 2 N, y dados x; y 2 n se tiene que C M (x) \C M (y) = ?: Dado que existen 2n palabras en n se tiene que

jQMjtn+1 1

jQMj 1 2n

Esta ultima desigualdad implica que tn 2 (n) ; dado que QM es unacantidad constante que no depende de n:



xlviii 5. Una introduccion a la complejidad computacional

El ejercicio 2 del capitulo 4 pedia veri…car que existe una maquina deTuring de una sola cinta capaz de reconocer el lenguaje P al en tiempoO n2

: Tenemos entonces una cota inferior y una cota superior referentes

al tiempo de computo requerido por una maquina de una sola cinta parareconocer el lenguaje Pal; y tenemos adicionalmente un hecho infrecuenteen ciencias de la computacion: la cota inferior y la superior cazan, o lo quees lo mismo las dos cotas son ajustadas (tight ).

5.2 Maquinas de Turing multicinta

En esta seccion presentaremos el modelo de maquinas de Turing multicinta.Dado k 2 N, una maquina de Turing con k cintas es una maquina de Turingque ademas de contar con la cinta de entrada, en la cual se escribe el inputantes de iniciar el computo, cuenta con k 1 cintas adicionales las cuales

pueden ser usadas como espacio de trabajo adicional. Adicionalmente lamaquina cuenta con k-cabezas lecto-escritoras (una por cada cinta) que semueven de manera independiente.

De…nición 46 Una maquina de Turing con k cintas es una sextupla

(Q; ; q 0; F ; ; A)

tal que:





5. La funcion de transicion es una funcion de ()k Q en ()k Q

f;; !gk:


En lo que sigue probaremos que:

Dada M una maquina con k cintas; existe M una maquina deuna sola cinta que simula M. Adicionalmente se tiene que para todo

n 2 N se satisface la desigualdad T M (n) k (T M (n) + n + 2k)2 :

El lenguaje P al puede ser decidido en tiempo lineal (¡incluso entiempo real!) por una maquina multicinta.



5.2 Maquinas de Turing multicinta xlix

Tenemos entonces que la adicion de hardware (k 1 cintas adicionales)incrementa el poder de computo pero de una manera modesta. Lo incre-menta porque permite decidir algunos lenguajes computables de manera

mas e…ciente. El incremento en poder de computo es modesto dado quelas nuevas maquinas son capaces de decidir exactamente los mismo lengua-

jes y ademas porque el incremento en e…ciencia (aceleramiento, speed up)es de caracter polinomial.

De…nición 47 Dada M = (Q; ; q 0; F ; ; A) una maquina con k-cintas,una con…guracion de M es una tupla (q; w1; p1; w2; p2;:::;wk; pk) ; donde q es el estado interno de la maquina y para cada i k el simbolo wi denota el contenido de la i-esima cinta, mientras que pi denota la posicion de la i-esima cabeza lecto-escritora.

Teorema 48 Dada M una maquina con kcintas; existe M una maquina de una sola cinta que simula M. Adicionalmente se tiene que para todo

n 2 N se satisface la desigualdad T M (n) k (T M (n) + n + 2k)2 :

Proof. Sea M = (Q; ; q 0; F ; ; A) una maquina de Turing con k-cintas.Para simular la maquina M usaremos una maquina de una sola cinta,llamemosla M: La construccion de la maquina M se basa en las sigu-ientes observaciones

Podemos particionar la cinta de M en las k clases de equivalenciamodulo k: Recuerde que podemos pensar en la cinta de M como enuna secuencia ordenada de celdas fi : i 2 Ng : Dado j k; la clase[ j] es la coleccion de celdas fl : l j (mod k)g : Usaremos la clase[ j] para simular los computs de M realizados sobre la cinta j-esima.

Podemos patir cada transicion de M en k-estapas, cada una de ellascorrespondiendo al trabajo que realiza M en cada una de las cintas.

Dado que el movimiento de la cabezas es independiente y no necesari-amente paralelo, en cada instante de la computacion y de cada clase[ j] debemos marcar la celda sobre la que ha de hallarse la j-esimacabeza.

Sea entonces M = (Q; ; q 0; F ; ; A) la maquina de…nida por:

1. Q = Q [ Ql [ Qe; donde

Ql =

nq !a ;i;l : !a 2 ()k y i 2 f0; 1;:::;kg

oy

Qe =n

q !a ;i;e;! : !a 2 ()k

; i 2 f0; 1;:::;kg y ! 2 f1; 0; 1gko

:

2. = [ f(a; i) : a 2 y i 2 f1;:::;kgg :



l 5. Una introduccion a la complejidad computacional

A la funcion no la de…niremos explicitamente, (por resultar increible-mente engorroso), a cambio ilustraremos como la maquina M simula unatransicion de M:

Considere una transicion tipica de M, como por ejemploq 1; w1

1:::w p11 :::w

jw1j1 ; p1;:::;w1

k:::w pkk :::w

jwkjk ; pk

!

q 2; w1

1:::z p11 :::w

jw1j1 ; p1 + 1;:::;w1

k:::z pkk :::w

jwkjk ; pk + k

donde 1;:::;k 2 f1; 0; 1g ; (supondremos sin perdida de generalidad

que 1 p1 ::: pk jw1j; jw1j = ::: = jwkj y 1;:::;k = 1): Parasimular una tal transicion de M usamos la siguiente secuencia de M-transiciones

q 1; w11w1

2:::w1k::: (w p1

1 ; 1) :::: (w pkk ; k) :::wjw1j

1 :::wjw1jk ; p1k + 1

!

(q 1)w

p11:::;1;l ; w1

1w12:::w1

k::: (w p11 ; 1) :::: (w pk

k ; k) :::wjw1j1 :::w

jw1jk ; p1k + 2

! :::

!

(q 1)wp11

wp22:::;2;l ; w1

1w12:::w1

k::: (w p11 ; 1) :::: (w pk

k ; k) :::wjw1j1 :::w

jw1jk ; p2k + 2

! :::

!

(q 1)wp11

wp22

:::wpkk

;k;l ; w11w1

2:::w1k::: (w p1

1 ; 1) :::: (w pkk ; k) :::w

jw1j1 :::w

jw1jk ; pkk

!

(q 2)z

p11

zp22

:::zpkk

;k;e;! ; w11w1

2:::w1k::: (w p1

1 ; 1) ::::z pkk :::wj

w1j1 :::wj

w1jk ; pkk + k1

! :::

!

(q 2)zp11

zp22

:::zpkk

;k;e;! ; w11w1

2:::w1k::: (w p1

1 ; 1) ::::z pkk :::wjw1j

1 :::wjw1jk ; pkk + kk

! :::

! ( (q 2)zp11

zp22

:::zpkk

;k1;e;! ; w11w1

2:::w1k::: (w p1

1 ; 1) ::::z pkk :::

w pk+1

k ; k

::

::wjw1j1 :::wjw1j

k ; pkk + kk) !

( (q 2)zp11

zp22

:::zpkk

;k1;e;! ; w11w1

2:::w1k::: (w p1

1 ; 1) ::::z pkk :::

w pk+1

k ; k

::

::wjw1j1 :::w

jw1jk ; pkk + kk 1) ! :::

! ( (q 2)zp11

zp22

:::zpkk

;1;e;! ; w11w1

2:::w1k:::z p1

1 :::

w p1+11 ; 1

:::z pk

k ::

::

w pk+1k ; k

:::w

jw1j1 :::w

jw1jk ; p1k + k + 1) !

q 2; w1

1w12:::w1

k:::z p11 :::

w p1+11 ; 1

:::z pk

k :::

w pk+1k ; k

:::w

jw1j1 :::w

jw1jk ; p1k + k + 1

La idea es que los estados en Ql son estados de lectura, lo cual quiere

decir que mientras la maquina M esta en un estado q 2 Ql; ella estarecorriendo la cinta recolectando informacion acerca de los k caracteresque esta leyendo la maquina M: La informacion recolectada, que puedeser codi…cada usando a lo mas jj k bits es almacenada usando los estados



5.2 Maquinas de Turing multicinta li

internos de la maquina M: Al terminar la fase de lectura, la maquinacalcula: el vector ! que indica las direcciones de movimiento de las cabezaslecto-escritoras de M; los caracteres z1;:::;zk que habran de reemplazar a

los k caracteres que la maquina M estaba leyendo y p el estado internoal que accede la maquina M: Tras calcular esta informacion, que de porsi determina la transicion de M; la maquina M la almacena dentro deun estado pz1;:::;zk;k;! ;e 2 Qe; el cual es un estado de escritura. Lo quela maquina M debe hacer a continuacion es: realizar los reemplazos decaracteres a lugar, marcar las posiciones de la cinta unidimensional quecorresponden a las posiciones de las k cabezas de M y …nalmente ubicarsu cabeza lectora en una posicion adecuada. Para realizar este trabajo,la unica informacion que M necesita, y que no se ha codi…cado dentrodel estado de la maquina, son las posiciones de las cabezas lectoras; espara ello que se usan caracteres adicionales de la forma (a; i) (con a 2 e i 2 f1;:::;kg), para marcar dichas posiciones.Note que para simular unatransicion de la maquina M se necesitan a lo mas k (T M (n) + n + 2k)transiciones de M por lo que el tiempo de computo de M esta acotadosuperiormente por k (T M (n) + n + 2k)

2

El teorema anterior a…rma que es posible simular velozmente una maquinamulticinta usando una maquina de una sola cinta. Que la simulacion seaveloz quiere decir que el aceleramiento (speed up) que es posible lograr alusar varias cintas no puede ser mas que polinomial.

Teorema 49 El lenguaje P al puede ser decidido en tiempo lineal por una maquina multicinta.Proof. Sea M la maquina de dos cintas de…nida por:

Al comienzo de la computacion, el input x aparece escrito en el ex-tremo izquierdo de la cinta 1; la cinta 2 se encuentra vacia, las dos cabezas lecto-escritoras de la maquina se encuentran ubicadas en el extremo izquierdo de cada cinta.

Supongamos que el input x tiene longitud n: En la primera etapa del computo las dos cabezas se desplazan n posiciones a la derecha.Mientras la cabeza 2 avanza sobre la cinta 2, ella va escribiendo si-multaneamente los caracteres de x (que la cabeza 1 esta leyendo).

En la segunda etapa del computo la cabeza 1 se desplaza al extremoizquierdo de la cinta 1.

En la tercera etapa las dos cabezas se mueven de manera simultanea,la cabeza 1 de izquierda a derecha leyendo el input, la cabeza 2 de

derecha a izquierda. Las dos cabezas van leyendo los contenidos de sus cintas. La cabeza 2 lee x pero de derecha a izquierda, mientras que la cabeza 1 lee x de izquierda a derecha. La maquina compara pasoa paso los caracteres leidos por cada una de las cabezas, si en algun



lii 5. Una introduccion a la complejidad computacional

instante de esta etapa las cabezas se encuentran leyendo caracteres distintos la maquina para y rechaza el input. Si todos los caracteres coinciden la maquina acepta el input.

Es facil convencerse de que la maquina M acepta el lenguaje Pal: Adi-cionalmente es facil convencerse de que el tiempo de computo de M es 3n

Comentario 50 Un importante teorema de Ziv Galil a…rma que existe una maquina multicinta capaz de reconocer el lenguaje P al en tiempo real [4]. Debe ser obvio para el lector que este teorema de Galil esta muy lejos de ser evidente o elemental, al teorema de Galil lo estudiaremos en el capitulo6.

5.3 Maquinas multidimensionales

En esta seccion estudiaremos un modelo de computacion que extiende elmodelo de maquina de Turing.

De…nición 51 Una maquina de Turing bidimenional (para mayor brevedad,simplemente maquina bidimensional) es una sextupla (Q; ; q 0; F ; ; A) tal que:



3. q 0 2 Q es el estado inicial de la maquina.4. F Q es el conjunto de estados …nales de la maquina.

5. La funcion de transicion es una funcion de Q en Q f;; !; "; #g :


Las maquinas bidimensionales son maquinas de Turing que cuentan conuna unica cinta bidimensional, la cual es un semiplano (el semiplano noror-iental) particionado en celdas. Adicionalmente la maquina cuenta con unacabeza lectora capaz de moverse a lo largo y ancho de la cinta. Es por

ello que en la de…nicion de ; el tercer factor del rango de ; que es el conjunto f;; !; "; #g ; incluye cinco parametros: movimientos a derecha,a izquierda, hacia arriba, hacia abajo y permanecer sobre la celda que seacaba de leer.



5.3 Maquinas multidimensionales liii

Dada M una maquina bidimensional y dado x un input de M; supon-dremos que al iniciar el computo, el input aparece escrito en la primera …lay con el primer caracter ocupando el extremo izquierdo de la primera …la.

Podemos pensar en la cinta de M como en el reticulo f(i; j) : i; j 2 Ng :La primera …la de la cinta es el conjunto f(0; j) : j 2 Ng : El origen de lacinta es la celda (0; 0) ; ubicada en el extremo suroccidental de la misma.

Es posible que una cinta bidimensional agregue algun poder de computoa la maquina, es posible que no. Si la tesis de Church es cierta, una cinta.nonos va a permitir decidir un lenguaje que no sea Turing-computable, perolo que si puede pasar es que la bidimensionalidad de la cinta nos permitadecidir algunos lenguajes computables de manera mas e…ciente. Esta ul-tima hipotesis podemos intentar revisarla a la luz de lo que sucede con ellenguje Pal: Antes de esto probaremos que toda maquina bidimensionalpuede ser efectivamente simulada por una maquina bidimensional, y queadicionalmente que el tiempo de computo de la maquina unidimensionalesta acotado por un polinomio en el tiempo de computo de la maquinabidimensional.

De…nición 52 Dada M una maquina bidimensional, una con…guracion de M es una tripla (q;A; (i; j)) ; donde q 2 Q es el estado interno de la maquina; A es el contenido de un subreticulo …nito de N N de la forma f(k; l) : k; l ng y tal que A alcanza a contener todo el contenido de la cinta de M; y …nalmente la pareja (i; j) indica la posicion de la cabeza lecto-escritora de M (se satisface que i; j n 1).

Teorema 53 Suponga que M es una maquina bidimensional que decide L: Existe una maquina unidimensional M1 que decide el lenguaje L:Adicionalmente se tiene que para todo n 2 N se satisface la desigualdad

T M1(n) 2

T M (n)2 + n + 4

2.

Proof. Suponga que M = (Q; ; q 0; F ; ; A) es una maquina bidimensionalque decide L: Probaremos que existe una maquina M1 con 2 cintas uni-dimensionales que reconoce L: La primera cinta sera usada para simular

la cinta bidimensional de M mientras que la segunda cinta se usara comocontador. El primer problema que debemos resolver es el siguiente: ¿comorecorrer, de manera lineal, el reticulo NN? Para resolver este primerproblema podemos usar la bien conocida biyeccion de Cantor entre el con-



liv 5. Una introduccion a la complejidad computacional

junto N y el conjunto N N, la cual se ilustra a continuacion

(0; 3)" &

(0; 2) (1; 2)- &

(0; 1) (1; 1) (2; 1)" & - &

(0; 0) (1; 0) ! (2; 0) (3; 0)

Usaremos la curva de Cantor para simular el desplazamiento de unacabeza lectora sobre una cinta bidimensional usando una cinta unidimen-sional. Note que dada (i; j) ; una celda cualquiera de la cinta bidimensionalde M, se satisface lo siguiente:

1. Si i; j 6= 0 e i + j es un numero par, la curva de Cantor visita (i; j)viniendo de la celda (i + 1; j 1) y llendo a la celda (i 1; j + 1) :

2. Si i; j 6= 0 e i + j es un numero impar, la curva de Cantor visita (i; j)viniendo de la celda (i 1; j + 1) y llendo a la celda (i + 1; j 1) :

3. Si i 6= 0 es un numero par, la curva de Cantor visita (i; 0) viniendode la celda (i 1; 0) y llendo a la celda (i 1; 1) :

4. Si i 6= 0 es un numero impar, la curva de Cantor visita (i; 0) viniendode la celda (i 1; 1) y llendo a la celda (i + 1; 0) :

5. Si j 6= 0 es un numero par, la curva de Cantor visita (0; j) viniendode la celda (1; j 1) y llendo a la celda (0; j + 1) :

6. Si j 6= 0 es un numero impar, la curva de Cantor visita (0; j) viniendode la celda (0; j 1) y llendo a la celda (1; j 1)

Para poder simular la dinamica de la cabeza de M usando una cintaunidimensional debemos usar un alfabeto enriquecido. Lo ideal seria queel caracter ubicado en una celda unidimensional i especi…cara a que celdabidimensional corresponde la celda i; esto es que el caracter ubicado en lacelda i especi…cara el valor de C (i) ; (donde el simbolo C denota la biyeccionde Cantor). Desafortunadamente esto es imposible dado que esto impli-caria usar un alfabeto in…nito. Nosotros nos contentaremos con muchomenos, usaremos un alfabeto tal que, dada i una celda unidimensional,el caracter ubicado en i en cualquier instante de la computacion especi-…ca la direccion asumida por la curva de Cantor al visitar la celda C (i) :

Sea M = (Q; ; q 0; F ; ; A) la maquina con 4 cintas unidimensionalesde…nida por:

Q = Q [ fq : q 2 Qg [ fq : q 2 Qg [ fq : q 2 Qg



5.3 Maquinas multidimensionales lv

= f"; !; -; & g [ f1g :

A la funcion no la de…niremos explicitamente, a cambio mostraremos

como la maquina M1 simula una transicion de la maquina M: Consider-aremos uno de 20 casos posibles. Considere la transicion

0BBBBBB@

q;

26666664

a0n ain ann

......

...a0j aij anj

......

...a00 ai0 an0

37777775

; (i; j)

1CCCCCCA

!

0

BBBBBB@ p;

2

6666664

a0n ain ann

......

...

a0j bij anj......

...a00 ai0 an0

3

7777775 ; (i; j + 1)

1

CCCCCCASupondremos que i; j 6= 0 y que i + j es un numero par. La maquina M1

simula esta transicion por medio de la siguiente secuencia de transiciones

q; (a00; ") (a01; &) (a10; !) ::: (aij ; -) ::: (ann; -) ; C 1 (i; j) ; ; 0

!

p; (a00; ") (a01; &) (a10; !) ::: (bij ; -) ::: (ann; -) ; C 1 (i 1; j + 1) ; 1; 1

!

p; (a00; ") (a01; &) (a10; !) ::: (bij ; -) ::: (ann; -) ; C 1 (i 2; j + 2) ; 11; 2

!

p; (a00; ") (a01; &) (a10; !) ::: (bij ; -) ::: (ann; -) ; C 1 (i i; j + i) ; 1i; i

!

p; (a00; ") (a01; &) (a10; !) ::: (bij ; -) ::: (ann; -) ; C 1 (0; j + i + 1) ; 1i; i ! p; (a00; ") (a01; &) (a10; !) ::: (bij ; -) ::: (ann; -) ; C 1 (1; j + i) ; 1i1; i 1

!

p; (a00; ") (a01; &) (a10; !) ::: (bij ; -) ::: (ann; -) ; C 1 (i; j + 1) ; ; 0

!

p; (a00; ") (a01; &) (a10; !) ::: (bij ; -) ::: (ann; -) ; C 1 (i; j + 1) ; ; 0

Note que, en nuestro caso particular, la segunda cinta se utiliza paracontar el numero de caracteres del tipo (a; -), esto es la maquina M1

cuenta el numero de ‡echas del tipo - agregando un 1 al contenido de lasegunda cinta cada vez que encuentra una tal ‡echa. El conteo de estas‡echas se realiza mientras la maquina esta en el estado p: Este conteopara cuando la maquina se encuentra con un caracter del tipo (a; ") ; en

este instante la maquina pasa al estado p: En la siguiente transicion lamaquina se encuentra por primera vez un caracter del tipo (a; &) ; lo cualla obliga a pasar al estado p y en consecuencia a iniciar el conteo de estetipo de caracteres (i.e. a iniciar el conteo de ‡echas del tipo &). El conteo



lvi 5. Una introduccion a la complejidad computacional

lo realiza borrando un uno (el ultimo caracter) al contenido de la segundacinta cada vez que se encuentra con una ‡echa &. La maquina terminaesta tercera fase al borrar completamente el contenido de la segunda cinta,

entonces pasa al estado p y se prepara para iniciar la simulacion de lasiguiente transicion de M:

Note que la simulacion de una unica transicion del computo de M enel input x; implica realizar a lo mas T M (jxj) transiciones, por lo que el

tiempo de computo de M1 satisface la desigualdad T M1(n) (T M (n))2 :

Ahora, dado que la maquina M1 es una maquina con dos cintas, el teorema48 garantiza que existe una maquina M de una sola cinta que puedesimular el computo de M1 y tal que dado x un input de M1 se tieneque T M (x) 2 (T M1

(x) + jxj + 4)2 : Tenemos …nalmente que existe una

maquina M de una sola cinta que puede simular el computo de M demanera que para todo n 2 N se satisface la desigualdad

T M (n) 2 T M (n)2 + n + 42

5.3.1 Una cota inferior

En esta seccion probaremos que toda maquina de Turing con una unica

cinta bidimensional que acepte P al tiene un tiempo de computo

n2

log(n)

.

El argumento es una adaptacion del argumento via secuencias de cruceusado en el caso unidimensional. Dada M una maquina bidimensional

que acepta Pal; asumiremos que el input esta ubicado en la primera …la,escrito de izquierda a derecha y con su primer caracter ubicado en el origen.Lo primero que debemos hacer para adaptar el argumento es adaptar lanocion de secuencia de cruce al caso bidimensional. Suponga que M esuna maquina de Turing bidimensional que acepta P al, suponga que x esun input de M de longitud n y suponga que i n: La secuencia de cruceC Mi (x) es una secuencia de parejas ordenadas, donde cada pareja estaconstituida por un estado de M y por un numero natural. Cada pareja enla secuencia C Mi (x) contiene informacion acerca de el estado en que estabala maquina al cruzar la linea que separa las columnas i-esima e i + 1-esima,ademas de la columna usada al realizar este cruce. Adicionalmente pedimosque exista una correspondencia entre la secuencia ordenada de parejas deC Mi (x) y la secuencia ordenada de ocasiones en que la cabeza lectora cruzo

tal linea.En lo que sigue …jaremos una maquina bidimensional que acepta Pal:

Los dos lemas a continuacion son la version bidimensional de los dos hechosclaves usados en la prueba del teorema de Hennie (45).



5.3 Maquinas multidimensionales lvii

Lema 54 Suponga que M acepta uv y xy; suponga ademas que jxj = i,juj = j y que C Mi (xy) = C Mj (uv) Tenemos entonces que M acepta la palabra xv.

Dada x 2 el simbolo w (x) denotara el palindromo x0jxjx: Dadom 1; el simbolo Lm denotara el conjunto fw (x) : jxj = mg :

Lema 55 Dadas x 6= y dos palabras de longitud m; y dados i; j 2 fm; :::; 2mgse tiene que C Mi (x) 6= C Mj (y) :

De los lemas anteriores es facil obtener la prueba del siguiente teorema

Teorema 56 Si M es una maquina bidimensional que acepta Pal; el tiempo

de computo de M es

n2

log(n)

:

Proof. El numero de posibles secuencias de cruce de longitud l y quecorresponden a computaciones de M de duracion acotada por n2 esta aco-

tado superiormente por jQj n2l ; donde jQj es el numero de estados de lamaquina M: Dado que Lm tiene exactamente 2m elementos que determi-nan m2m secuencias de cruce distintas dos a dos, se tiene que si l es unacota en la longitud de las secuencias de cruce determinadas por elementos

de Lm; entonces

jQj n2l

2m; y esto implica que

l logjQjn2 2m =m

2log(n) + log (jQj)

De ello se tiene que existe wm 2 Lm tal que wm determina m secuencias

de cruce de longitud

mlog(m)

y esto claramente implica que el tiempo de

computo de M es

n2

log(n); dado que el tiempo de computo de M en el

input wm es mayor o igual que la suma de las longitudes de las secuenciasde cruce determinadas por wm; y esta cantidad es al menos m2

log(m) (recuerde

que jwmj = 3m)

Comentario 57 Note que el argumento usado en la prueba anterior puede ser facilmente adpatado al caso k-dimensional (con k 3).

Ejercicios

1. Prueba los dos lemas que, en esta seccion, se enunciaron y no seprobaron.

2. De…na de manera detallada el concepto de maquina de Turing k-dimensional.

3. Establezca cotas inferiores para el reconocimiento de palindromosusando maquinas de Turing con una sola cinta de k-dimensiones(maquinas k-dimensionales).



lviii 5. Una introduccion a la complejidad computacional

5.3.2 Una cota superior

En esta seccion probaremos que existe una maquina de Turing bidimen-

sional que reconoce P al en tiempo O n2

log(n) : Note que esta cota superior, junto con la cota inferior de la seccion anterior, implica que una maquinade Turing bidimensional que resuelva P al de manera optima (optima en

terminos del tiempo de computo), tiene un tiempo de computo O

n2

log(n)

:

A continuacion presentaremos un algoritmo bidimensional (esto es, unamaquina de Turing bidimensional) que resuelve el problema P al en tiempo

O

n2

log(n)

:

La idea del algoritmo es la siguiente. Supondremos que el vocabulario esf0; 1g : Dado x una instancia de Pal; partimos a x en bloques de longitud y:Interpretamos cada bloque como un numero en el intervalo f0;:::; 2y 1g :Dado N un bloque a la izquierda de x; si el contenido del bloque N es elnumero m; marcamos la …la m-esima. Revisamos el bloque a la derecha

de x que corresponde al bloque N; llamemos N a este bloque. Leemosel contenido de N de derecha a izquierda y lo interpretamos como unnumero, digamos n: Marcamos la columna n; si marcamos dos veces lamisma columna, los bloques N y N son apropiados el uno para el otro.Realizamos este trabajo para cada uno de los bloques que constituyen elinput x: Note que para comparar dos bloques es su…ciente recorrer laprimera …la de la cinta 2 veces. Esto implica que el numero de veces que

debemos recorrer el input es O

ny

: Si escogemos el y de manera adecuada,

obtendremos la cota superior que estamos intentando establecer.A continuacion presentaremos una descripcion detallada del algoritmo.

Asumiremos que la cinta de la maquina tiene un marcador en el origen.Adicionalemente asumiremos que el input esta escrito en la primera …la

empezando en la celda justo a la derecha del origen.

Algoritmo 58 (Algoritmo bidimensional)Sea x una instancia de P al de longitud n:

1. (fase de inicializacion)

Calcule dlog(n)e y escriba el resultado en unario en la segunda …la, utilice ceros para tal …n. (Es posible calcular log(n) en tiempo O (n log(n)) de la siguiente manera: Recorra el input marcando posiciones alternativamente, es decir una si una nouna si..... Repita el proceso hasta que todas las posiciones esten

marcadas. El numero de iteraciones es igual a dlog(n)e + 1)

Calcule log (log (n)) y escriba el resultado en unario en la tercera …la, utilice ceros para tal …n.



5.3 Maquinas multidimensionales lix

Calcule y = log(n) log (log (n)) : Borre los contenidos de la segunda y tercera …la. Escriba y en unario en la segunda …la,utilice ceros para tal …n.

2. (Comparacion de bloques)

Empezando con la segunda …la que contiene la palabra 0y copie repetidamente el contenido de la …la actual en la …la que queda

justo arriba y al contenido de esta nueva …la sumele 1: Pare cuando escriba en alguna …la la palabra 1y: Al …nalizar este proceso la maquina ha escrito todos los numeros entre 0 y 2y 1;en orden ascendente, utilizando el extremos izquierdo de las …las 2; 3; :::; 2y:

lea el primer caracter de x: Suponga que este caracter es igual a x1: Recorra la primera columna entre las …las 2 y 2y: En

cada celda veri…que si el caracter es igual a x1; si es el casoreemplaze el contenido de la celda por el simbolo " : En casocontrario reemplaze el contenido de la celda por el simbolo # :Repita este proceso para todas las columnas entre la primera y la y-esima.

Lea los contenidos de las …las 2 a 2y: Si una de estas …las contiene un simbolo #; reemplaze el contenido de esta …la por #y: Al …nalizar el proceso una unica …la contiene la palabra "y

mientras que todas las demas contienen la palabra #y: Note que con esto hemos marcado la …la que correponde al contenido del primer bloque.

Repita el proceso con el bloque del extremo derecho, pero en esta ocasion, lea el contenido del bloque de derecha a izquierda y es-criba de derecha a izquierda. Veri…que que la …la marcada para el primer y ultimo bloque coinciden. Si no es el caso, pare y rechaze a x: En caso contrario continue. Repita el procesocon el segundo bloque a la izquierda y el segundo bloque a la derecha. Continue despues con los bloques subsiguientes hasta que el par de bloques que usted esta trabajando se intersecten.Cuando esto suceda, veri…que que el fragmento restante (el frag-mento obtenido al suprimir de x los bloques ya analizados) es un palindromo. Note que este fragmento tiene una longitud acotada por 2y 2log(n) : Para veri…car que el bloque restante es un palindromo podemos usar el algoritmo estandard para maquinas unidimensionales, lo cual requiere un tiempo de computo acotado

por log(n)2

:

Es facil veri…car que el tiempo de computo del algoritmo anterior es

O

n2

log(n)

:



lx 5. Una introduccion a la complejidad computacional

Ejercicio 59 Pruebe que el tiempo de computo del algoritmo es O

n2

log(n)

:

5.4 Otros modelos: la tesis de Church fuerte

El lector debe notar que todos los modelos de computacion introducidoshasta el momento poseen la siguiente caracteristica: todos pueden ser sim-ulados en tiempo polinomial por maquinas de Turing de una sola cintaunidimensional. Es importante anotar que esta caracteristica no es unamera casualidad y quer los modelos presentados en este libro no fueronescogidos convenientemente para que se presentara este fenomeno. Este esun fenomeno muy general: de casi cualquier tipo de maquina se ha logradomostrar que pueden ser simuladas en tiempo polinomial por maquinas deTuring de una sola cinta. Lo anterior motiva y justi…ca el enunciado de lasiguiente version fuerte de la tesis de Church.

Hipotesis 60 (Tesis de Church fuerte)Todo modelo de computacion puede ser simulado en tiempo polinomial

usando maquinas de Turing de una sola cinta.

En esta, la ultima seccion del capitulo estudiaremos dos modelos de com-putacion que podrian ser contraejemplos a la tesis anterior, ellos son: lasMaquinas de Turing probabilisticas y las Maquinas cuanticas

5.4.1 Maquinas de Turing probabilisticas

Una maquina de Turing probabilistica es una maquina de Turing de unasola cinta equipada con un generador de bits aleatorios.

De…nición 61 Una maquina de Truing probabilistica es una sextupla M = (Q; q 0;A;F; ; ; ) tal que


2. es el alfabeto de la maquina, del cual supondremos que [fg :

3. A F Q; donde A es el conjunto de los estados de aceptacion y F es el conjunto de los estados …nales.

4. es una funcion de Q f0; 1g en Q f;; !g :

Dada M una maquina de Turing probabilistica, supondremos que entoda computacion y antes de cada transicion la maquina M genera un bit

aleatorio a 2 f0; 1g : Generado el bit a la maquina lee el caracter escrito enla celda que esta siendo escaneada, y entonces decide: que estado asdumir,que caracter escribir y en que direccion moverse. Supondremos ademasque cada maquina M determina una distribucion de probabilidad en el



5.4 Otros modelos: la tesis de Church fuerte lxi

conjunto f0; 1g ; esto es para cada maquina de Turing probabilistica Mexiste p 2 [0; 1] tal que el generador de bits aleatorios de M genera, encada transicion, un 1 con probabilidad p y un 0 con probabilidad 1 p:

Una maquina de Turing probabilistica es una maquina de Turing no de-terministica. Esto implica que dado un input x; la maquina puede realizarmuchos computos distintos con el input x dependiendo de la secuencias debits aleatorios generados durante la computacion.

Dado v 2 una secuencia legal para v es una secuencia 2 f0; 1g parala cual existe una computacion de M con input v; cuyo tiempo de computoes jj ; y tal que la secuencia de bits generados durante esta computacion esprecisamente la secuencia : Sea A (v) =

2 f0; 1g : es legal para v

.

Una maquina M es buena si y solo si para todo input v

X2A(v)

Pr [] = 1

Intuitivamente una maquina M es buena si y solo si para todo input v;la maquina para al procesar v con probabilidad 1. Por otro lado diremosque M es una maquina standard si y solo si antes de terminar la computa-cion la maquina debe: llegar al extremo derecho del contenido de la cinta,recorrer la cinta de derecha a izquierda sin cambiar de estado, llegar al ex-tremo izquierdo y entonces si parar. Dada M una maquina probabilisticasupondremos que M es buena y standard.

De…nición 62 1. Dado v 2 se de…ne

(v) = Pr2A(v)

[la -computacion de M con input v es aceptante ]

2. Diremos que M reconoce L con error " si y solo si para todo v 2

se tiene que

Si v 2 L entonces (v) 1 ":

Si v =2 L entonces (v) ":

3. Dado v 2 se de…ne T M (v) =X

2A(v)

Pr [] jj

4. Dado n 2 N se de…ne T M (n) = maxv:jvj=n

nT M (v)

o:

Comentario 63 Dado que las maquinas probabilisticas son no determinis-ticas, dada M una tal maquina y dado v un input de M, tiene mas sentidohablar del tiempo de computo esperado de M con input v que del tiempo

de computoM con input v: Note que en el item 3 de la de…nicion ante-rior hemos de…nido T M (v) como el valor esperado de la variable aleatoria tiempo de computo. Es natural que en el contexto de las maquinas prob-abilisticas de…namos las cantidades de interes como valores esperados de



lxii 5. Una introduccion a la complejidad computacional

variables aleatorias adecuadas y no como cantidades deterministicas, i.e.como cantidades asociadas a variables deterministicas.

El ob jetivo de esta seccion es establecer las siguientes cotas

(cota superior) Existe una maquina de Turing probabilistica M quereconoce P al con error 1

5 y tal que T M (n) 2 O

n log2 (n)

:

(cota inferior) Si M es una maquina de Turing probabilistica quereconoce el lenguaje P al con error " 2

0; 1

2

; se tiene que existe

c 0 tal que T M (n) cn log(n) :

Para el caso de maquinas probabilisticas las cotas inferior y superiorno son ajustadas dado que existe un gap (una brecha) entre n log(n) yn log2 (n). Aun asi es importante anotar que en el trabajo [11] se referenciaun resultado no publicado de Pippenger, quien supuestamente diseño un

algoritmo probabilistico (o, lo que es lo mismo, una maquina de Turingprobabilistica) que reconoce P al con error 1

3 y en tiempo O (n log(n)) :

La cota superior: el algoritmo de Freivald

En esta seccion presentaremos el algoritmo clasico de Freivald [3] que re-conoce P al en tiempo O

n log2 (n)

con error 1

5 : Los algoritmos prob-abilisticos tiene una larga historia dentro de la teoria de la computacion,ellos presentan desventajas respecto a los algoritmos clasicos(deterministas)dado que pueden cometer errores, pero poseen tambien una gran ventaja:suelen ser mas e…cientes. Existe una larga lista de algoritmos probabilis-ticos que son mas e…cientes que todos los algoritmos clasicos conocidos(obviamente, que resuelven el mismo problema). Una pequeñisima lista

parcial es la siguiente:

1. El algoritmo de Schwartz-Zippel (consulte la referencia [8]) para de-terminar si un polinomio en varias variables es no nulo sobre un campo…nito dado.

2. El algoritmo de Freivalds para multiplicar matrices [3].

3. El algoritmo de Freivalds para reconocer P al [3]

Es importante anotar que todo algoritmo probabilistico puede ser con-vertido en un algoritmo clasico, aunque ello puede implicar un alto costo:el tiempo de computo del algoritmo clasico podria ser exponencial en el

tiempo de computo del algoritmo probabilistico.empezemos recordando dos desigualdades fundamentales de la teoria de

la probabilidad, a saber: La desigualdad de Markov y La desigualdad de Chebyshev.



5.4 Otros modelos: la tesis de Church fuerte lxiii

Teorema 64 (desigualdad de Markov)Si X es una variable aletoria positiva y E [X ] es su valor esperado, se

tiene que para todo a 2 R+

Pr [X a] E [X ]

a

Teorema 65 (desigualdad de Chebyshev)Dada X una varible aleatoria, si E [X ] es su valor esperado y 2

X es su desviacion standard, se tiene que para todo a 2 R+

Pr [jX E [X ]j a] 2

X

a2

Sea x = x1:::xn una palabra de longitud n; si x no es palindromo existei n tal que xi 6= xni: Note que, Prjn [xj 6= xnj ] 2

n. Suponga ahora

que escogemos a numeros en el intervalo f1;:::;ng : ¿Cual es la probabilidad

de escoger, entre esos a numeros, al menos un numero i tal que xi 6= xni?Es claro que si existe mas de un i para el cual xi 6= xni; la probabilidades mayor. Supongamos que jfi n : xi 6= xnigj = 2: El valor esperado,del numero de escogencias aleatorias realizadas, antes de escoger a i o an i es log(n) : Supongamos entonces que escogemos a log(n) numerosentre 1 y n; digamos j1;:::;ja log(n) ¿cual es la probabilidad de que i o n i

pertenezcan al conjunto j1;:::;ja log(n)

?. Note que, si X es la variable

aleatoria: numero de escogencias realizadas antes de escoger por primeravez a i o a n i: La desigualdad de Markov nos dice que

Pr

i =2 j1;:::;ja log(n)

y j =2

j1;:::;ja log(n)

=

Pr [X a log(n)] 1

a

Por lo que

Pr

i 2 j1;:::;ja log(n)

o j 2

j1;:::;ja log(n)

a 1

a

Suponga ahora que nosotros recorremos la palabra x y a cada posicion la

marcamos con probabilidad b log(n)n

(con probabilidad 1 b log(n)n

no mar-camos la posicion). Sea Y la variable aleatoria: numero de posiciones mar-cadas al …nalizar el recorrido. ¿Cual es el valor esperado de Y ? ¿Cual esla desviacion standard de Y ? ¿cual es la probabilidad de que el numero deposiciones marcadas pertenezca al intervalo f(b c)log(n) ; :::; (b + c)log(n)g?

1. E [Y ] =

Pin

b log(n)n

= b log(n) :

2. 2Y = E

Y 2

E [Y ]2 = n

b log(n)

n

b log(n)

n

2=

n

nb log(n)b2 log2(n)n2

= b log(n) b2 log2(n)

n



lxiv 5. Una introduccion a la complejidad computacional

3. La desigualdad de Chebyshev nos dice que

Pr [Y =2 f(b c)log(n) ; :::; (b + c)log(n)g]

Pr [jY E [Y ]j c log(n)] b log(n) b2 log2(n)

n

c2 log2 (n)

b

c2

De todo lo anterior tenemos que: si recorremos la palabra x, y marcamos

cada posicion con probabilidad 10 log(n)n

; con probabilidad al menos 1025 el

numero de posiciones marcadas pertenecera al intervalo

f(5)log(n) ; :::; (15)log (n)g

y esto a su vez implica que la probabilidad de que la posicion i sea una de lasposiciones marcadas es al menos 4

5 : Considere el siguiente procedimientoCon input x = x1:::xn

1. Para cada j 2 f1;:::;ng, decida si marca o no la posicion j: Para ello

arroje una moneda tal que Pr [cara] = 10log(n)n

: Si sale cara marquela posicion, en caso contrario no la marque.

2. Sea fi1;:::;ikg el conjunto de las posiciones marcadas. Para todo j k decida si xij = xnij : Si este es el caso acepte x; en casocontrario, esto es si existe j k tal que xij 6= xnij rechaze x:

Note que

1. Si x 2 P al el procedimiento acepta x con probabilidad 1.

2. Si x =2 Pal; el procedimiento rechaza x con probabilidad

4

5

3. El valor esperado del numero de posiciones marcadas es 10log(n) :

Intuitivamente, el procedimento anterior toma un input x; el cual es unapalabra de longitud n; probabilisticamente transforma x en una palabracorta, llamemosla z (de longitud 10log(n)) y entonces decide si z 2 Pal:Dado que el tiempo de computo de un algoritmo que reconoce Pal; alprocesar el input x; depende de jxj ; el transformar el input x en una palabracorta z puede reducir el tiempo de computo de manera signi…cativa. Elproblema es: ¿como implementar el algoritmo anterior en una maquina deTuring de una sola cinta?

Considere el siguiente problema

Problema 66 (Calculo del caracter dual)

Input: x; donde x es una palabra en el vocabulario [ f1g tal que existe un unico i jxj para el cual xi 2 f1g.



5.4 Otros modelos: la tesis de Church fuerte lxv

Problema: Decida si 1 (xi) = xni; donde para todo a 2 se tiene que 1 (a; 1) = a:

Note que si podemos resolver el problema anterior en tiempo O n log2

(n)usando una maquina de una sola cinta, podemos entonces diseñar unamaquina de Turing probabilistica M que decide P al y tal que para todon 1 se tiene que T M (n) 2 O

n log2 (n)

: Esto es asi dado que en la

primera fase del procedimento anteriormente expuesto se escogen y mar-can O (log (n)) posiciones, y lo que resta entonces por hacer es resolverel problema Calculo del caracter dual para cada una de estas O (log (n))posiciones.

Ejercicio 67 Diseñe una maquina de Turing de una sola cinta, que lla-maremos Dual y que resuelve, en tiempo O (n log(n)) ; el problema: Calculodel caracter dual.

Hecho lo anterior estamos listos para describir el algoritmo de Freivalds.

Algoritmo 68 (Algoritmo de Freivald)con input x

1. Calcule jxj y log (jxj) :

2. Use un generador de bits aleatorios tal que la probabilidad de generar

un 1 es igual a log(jxj)jxj : Para cada posicion i jxj ; decida si marca

la posicion i o no. Use el generador aleatorio, si este genera un 1marque la posicion en caso contrario no la marque.

3. Sea fi1;:::;ikg el conjunto de las posiciones marcadas. Para todo j k decida, simulando la maquina Dual; si xij = xnij : Si este es el caso acepte x; en caso contrario, esto es si existe j k tal que

xij 6= xnij ; rechaze x:

Sea M la maquina de Turing probabilistica que implementa el algoritmoanterior. Es facil convencerse de lo siguiente:

1. T M (n) 2 O

n log2 (n)

:

2. Si x 2 P al la maquina M acepta x con probabilidad 1.

3. Si x =2 Pal; la maquina M rechaza x con probabilidad 45

Ejercicio 69 Veri…que lo anterior.

La cota inferior

En esta seccion probaremos la cota inferior, el argumento en la prueba esuna adaptacion al contexto probabilista del argumento via secuencias decruce.

Sea M una maquina probabilistica y sea v un input de M.



lxvi 5. Una introduccion a la complejidad computacional

De…nición 70 Dado 2 A (v) ; el simbolo S [v; ; j] denotara la secuencia ordenada de los estados asumidos por M al cruzar la linea que separa las celdas i-esima e i + 1-esima, mientras realiza la computacion determinada

por v y por :

Dada S [v; ; j] una secuencia de cruce el simbolo jS [v; ; j]j denotara sulongitud, la longitud esperada(promedio) de las secuencias de cruce deter-minadas por v se de…ne naturalmente como

l (v; j) =X

2A(v)

Pr [] jS [v; ; j]j

Lema 71 Para todo v se tiene que T M (v) P

jjvj l (v; j):

Proof. Dada 2 A (v) se tiene que jj P

jjvj jS [v; ; j]j : De ello setiene que

T M (v) =X

2A(v)

Pr [] jj X

2A(v)

Pr []

0@ X

jjvj

jS [v; ; j]j

1A =

Xjjvj

0@ X

2A(v)

Pr [] jS [v; ; j]j

1A =

Xjjvj

l (v; j)

Suponga que en algun momento del computo la maquina M esta en elestado q; con la cabeza lectora pasando en ese instante de la celda j a lacelda j + 1; y que el contenido de la cinta de la celda j + 1 en adelante es lapalabra u seguida de espacios en blanco. Dados z 2 y p 2 Q se de…ne

g (q;u;p;z) como la probabilidad de que, cuando la cabeza de la maquinacruce nuevamente la linea que separa las celdas j-esima y j + 1-esima (estavez pasando de la celda j + 1 a la celda j), M se encuentre en el estado py con el contenido de la cinta, de la celda j + 1 en adelante, siendo igual ala palabra z seguida de espacios en blanco.

De…nición 72 Dado k 1 y dado u 2 la k-esima signatura izquierda de u es la tupla

Gk (u; s1; t1;:::;sk; tk) : s1; t1;:::;sk 2 Q F y tk 2 F

,

donde

Gk (u; s1; t1;:::;sk; tk) =Xz1;:::;zk2

g (s1; u ; t1; z1) g (s2; z1; t2; z2) :::g (sk; zk1; tk; zk)

Comentario 73 Dado que 0 P

p;z g (q;u;p;z) 1 se sigue que

0 Gk (u; s1; t1;:::;sk; tk) 1



5.4 Otros modelos: la tesis de Church fuerte lxvii

Supongamos ahora que la cabeza de la maquina esta pasando de la celda j + 1 a la celda j; con la maquina en el estado q y con el contendio de lacinta, a la izquierda de la celda j + 1; siendo igual a la palabra u: Se de…ne

h (q;u;p;z) como la probabilidad de que cuando la cabeza de la maquinapase nuevamente sobre la linea separando las celdas j-esima y j + 1-esima(llendo esta vez de j a j + 1) lo haga estando en el estado p y con elcontenido de la cinta, a la izquierda de la celda j + 1; siendo igual a z:

Sea h0 (u;p;z) la probabilidad de que si M visita desde la derecha elextremo izquierdo de u; estando en el estado q 0; cruce por primera vez elextremo derecho de x, digamos la linea que separa la celda n y la celdan + 1; estando en el estado p y con el contenido de la cinta, a la izquierdade n + 1; siendo igual a z:

De…nición 74 Dado k 1 y dado u 2 la k-esima signatura derecha de u es la tupla

H k (u; s1; t1;:::;tk1; sk) : s1; t1;:::;tk1; sk 2 Q F

, donde

H k (u; s1; t1;:::;tk1; sk) =

Xz1;:::;zk2

h0 (u; s1; z1) h (t1; z1; s2; z2) :::h (tk1; zk1; sk; zk)

Es facil veri…car que

0 H k (u; s1; t1;:::;sk; tk) 1

Para …nalizar de…niremos la nocion de patron

De…nición 75 Dado k 1 y dado u 2 el k-esimo patron de u es la tu-pla dI kGi (u; s1; t1;:::sk; tk)e : 1 i k y s1; t1; :::si; ti1 2 Q F y tk 2 F ,

donde I k es igual a (r)k3 y r = jQj 1:

Lema 76 El numero de distintos k-patrones es a lo mas exp

4k3r2k ln (r)

:

Proof. Dado que 0 Gi (u; s1; t1;:::si; ti; sk) 1; las entradas de un k-patron son numeros enteros en el intervalo f0;:::;I kg : Por otro lado cada

k-patron es un vector conP

ik 2 (r 1)2i1

entradas. Tenemos entoncesque el numero de k-patrones esta acotado por

(I k + 1)P

ik 2(r1)2i1

rk3 + 12r2k

exp

4k3r2k ln (r)

en adelante diremos que una secuencia de estados s1; t1; :::sk; tk es legalsi y solo si s1; t1; :::sk 2 Q F y tk 2 F: Sea v = xu un input de M, seaB un conjunto de secuencias legales y sea G (v; jxj ; B) la probabilidad deque la secuencia de cruce de M, con input v; en la posicion jxj ; pertenezca



lxviii 5. Una introduccion a la complejidad computacional

a B: Es facil veri…car que

G (v; jxj ; B) = Xk1

0@ Xs1;t1;:::sk;tk2B

H k (x; s1; t1;:::sk) Gk (u; s1; t1; :::sk; tk)1A

Lema 77 Dadas x;u;w 2 y dados d; m 1 se tiene que: si l (xu; jxj) d y las palabras w y u tienen el mismo md-patron, entonces

(xw)

1 rd2

(xu) m1

2r(m3d3d2md)

Proof. Dado que l (xu; jxj) d; la probabilidad de que la secuencia decruce de M, con input xu; y en la posicion jxj ; tenga longitud mayor quemd esta acotada superiormente por 1

m. Sea BA el conjunto de secuencias

de cruce de longitud acotada por md y tales que el ultimo estado de la

secuencia pertenece a A: De…nimos BR de manera analoga como el conjunto de las secuencias de cruce de longitud a lo mas md para las cuales elultimo estado de la secuencia pertenece a F A: Dado que la maquina esstandard se tiene que

G (xu; jxj ; BA) + G (xu; jxj ; BA) 1 1

m

Y dado que G (xu; jxj ; BA) 1 (xu) se tiene que

G (xu; jxj ; BA) (xu) 1

m[eq:1]

Por otro lado, el lema anterior implica que

G (xw; jxj ; BA) G (xu; jxj ; BA) =X2BA

H jj (x; )

Gjj (w; ) Gjj (u; )

[eq: 2]

donde H jj (x; ) denota la signatura derecha de x determinada por yGjj (z; ) denota la signatura izquierda de z determinada por :

Tenemos entonces que

G (xw; jxj ; BA) G (xu; jxj ; BA) =

X2BA:Gjj(u;) rd

2

Imd

H jj (x; )

Gjj (w; ) Gjj (u; )

+

X2BA:Gjj(u;) rd

2

Imd

H jj (x; )

Gjj (w; ) Gjj (u; )



5.4 Otros modelos: la tesis de Church fuerte lxix

Note que el valor absoluto del primer sumando esta acotado por

jBaj

rd2

I md 2r

md rd2

I md = 2r

(m3d3d2md)

Y note tambien que el valor absoluto del segundo sumando esta acotadopor X

2BA:Gjj(u;) rd2

Imd

H jj (x; )1

I md

X2BA:Gjj(u;) rd

2

Imd

H jj (x; )1

rd2Gjj (u; ) G (xu; jxj ; BA)

1

rd2

De la ecuacion 2 tenemos que

G (xw; jxj ; BA) G (xu; jxj ; BA)

2r(m3d3d2md) rd2G (xu; jxj ; BA) G (xw; jxj ; BA) 1 rd2

G (xu; jxj ; BA) 2r(m3d3d2md)

Finalmente de la desigualdad anterior y de la desigualdad 1 tenemos que

(xw) G (xw; jxj ; BA)

1 rd2

(xu) 1

m

2r(m3d3d2md)

Corolario 78 Dadas x;u;w 2 y dado d 10; si l (xu; jxj) d, (xu) 9

10 y las palabras w y u tiene el mismo 2d-patron, entonces

(xw) 15 :

Lema 79 Ya estamos listos para enunciar y probar el teorema central de esta subseccion.

Teorema 80 Si M es una maquina de Turing probabilistica que reconoce el lenguaje P al con error " 2

0; 1

2

; existe entonces c 0 tal que para

in…nitos n se tiene que T M (n) cn log(n) :

Proof. Supondremos = 110

(si 2110

; 12

podemos usar alguna tecnica

standard para ampli…car probabilidades ). Dado n 2 N de…nimos el lenguajeLn como

f1nww1n : w 2 ng

El cual es un subconjunto de Pal: Mostraremos que para todo i 2f2n + 1; :::; 3n + 1g y para la mayoria de los w 2 n; el valor esperado dela longitud de la secuencia de cruce en i es (log(n)) ; lo cual implica queexiste v 2 Ln tal que T M (v) 2 (n log(n)) :



lxx 5. Una introduccion a la complejidad computacional

Dados n; j 2 N con j 4n + 1 de…nimos

F n;j (d) = nv 2 Ln : l (v; j) doA…rmacion. Para todo 2n + 1 j 3n + 1 se tiene que jF n;j (d)j

exp

32d3r4d ln (r)

:(prueba de la a…rmacion) Dada v 2 Ln podemos escribir v como vv

con jvj = j: Dado w 2 Ln; si v 6= w se tiene que vw =2 Pal: Sila a…rmacion fuera falsa tendriamos que jF n;j (d)j exp

32d3r4d ln (r)

y

entonces, como consecuencia del lema 76, tendriamos que existen v 6= w dospalabras en Ln tales que w y v tienen el mismo 2d-patron. El corolarioanterior implica que (vw) 1

5 contradiciendo el que vw =2 P al y elque supuestamente M reconoce P al con error 1

10 15

:

Sea d = d logn10

e; dado n su…cientemente grande se tiene que

jLn F n;j (d)j 2n exp 32d3r4d ln (r) 2n

2 =jLnj

2

Tenemos entonces que para todo 2n + 1 j 3n + 1

Xv2Ln

l (v; j) d jLnj

2

Por lo que

maxv2Ln

nT M (v)

o

1

jLnj

Xv2Ln

T M (v) 1

jLnj

Xv2Ln

X2n+1j3n+1

l (v; j) =

1

jLnj X2n+1j3n+1

Xv2Ln

l (v; j)

Y esto implica que

maxv2Ln

nT M (v)

o

1

jLnj

X2n+1j3n+1

d jLnj

2=

d (n + 1)

22 (n log(n))

5.4.2 Maquinas cuanticas

Las maquinas cuanticas son el analogo cuantico de las maquinas de Turing.Mientras las maquinas de Turing pueden ser consideradas dispositivos cla-

sicos de computo (en el sentido de que su mecanismo esta controlado porlas leyes de la mecanica clasica), las maquinas cuanticas solo pueden serconsideradas como dispositivos cuanticos de computo, dado que las leyesque controlan su mecanismo son las leyes de la mecanica cuantica. En



5.5 Ejercicios capitulo 5 lxxi

particular las maquinas cuanticas explotan la posibilidad de superponerinformacion en un estado cuantico, y esto les permite a estas maquinasrealizar una gran cantidad (una cantidad exponencial) de computaciones

simultaneamente en paralelo. Esta habilidad de las maquinas cuanticas hapermitido desarrollar algoritmos cuanticos (algoritmos que solo pueden serefectivamente implementados en maquinas cuanticas) que resuelven proble-mas aparentemente di…ciles en tiempo polinomial. El ejemplo mas famosoes el algoritmo cuantico de Shor [9], el cual permite encontrar la descom-

posicion prima de un entero n en tiempo O

jnj16

; (donde jnj denota el

tamaño del input n el cual es igual a log(n)). El algoritmo de Shor esentonces un algoritmo de tiempo polinomial que resuelve el problema de lafactorizacion de enteros. No existe una prueba de tal hecho, pero es unahipotesis ampliamente aceptada que el problema de la factorizacion enterano puede ser resuelto clasicamente en tiempo polinomial. Si este fuera elcaso, sucederian dos cosas muy interesantes:

1. La tesis fuerte de church seria falsa.

2. Los protocolos criptogra…cos del tipo RSA; serian seguros desde elpunto de vista clasico (esto es, no se podrian romper en tiempo poli-nomial usando algoritmos clasico).

Estudiar el modelo de maquinas cuanticas esta fuera del alcance de estelibro, y preferimos por tanto cerrar en este punto esta brevisima seccion.


1. Pruebe todas aquellas a…rmaciones que en este capitulo se presen-taron sin prueba y que usted considere no evidentes.

2. nose

3. nose

4. nose

5. nose

6. nose

7. no se



lxxii 5. Una introduccion a la complejidad computacional



This is page lxxiiiPrinter: Opaque this

6

Aplicaciones

En este el ultimo capitulo de libro estudiaremos algunas aplicaciones. Lasaplicaciones que estudiaremos pertencen a lo que suele llamarse el re-conocimiento de patrones. Estudiaremos, especi…camente, el problema delistar todos los palindromos que aparecen como subpalabras de una palabragrande. La palabra grande puede ser una secuencia genomica, las cualestipicamente son cadenas constituidas por millones e incluso millardos decaracteres. El que los inputs tipicos en las aplicaciones (por ejemplo enBioinformatica) sean palabras inmensas implica que, cuando intentemos

analizar estas palabras (para por ejemplo decidir si ellas son palindromos,o para listar todos sus subpalindromos) debemos usar algoritmos tan e…-cientes como sea posible, es por ello que en este capitulo estudiaremos elalgoritmo de Galil de tiempo real y algoritmos paralelos de tiempo sublin-eal.

6.1 Reconocimiento de patrones: Listado depalindromos aproximados

El algoritmo de Galil

Algoritmos paralelos



lxxiv 6. Aplicaciones



This is page lxxvPrinter: Opaque this

References

[1] A. Apostolico, D Breslauer, Z. Galil. Parallel Detection of all the Palin-dromes in a String. Theoretical Computer Science 141(1&2):163-173(1995)..(cesar-fabian)

[2] T. Biedl, J. Buss, E. Demaine, M. Demaine, M. Hajiaghayi, M. Vinar.Palindrome Recognition Using a Multidimensional Tape. TheoreticalComputer science 302(1-3): 475-480 (2003).

[3] R. Freivalds. Fast computation by probabilistic Turing machines.Theory of Algorithms and Programs, Latvian State University 2:201-205 (1975).

[4] Z. Galil. Palindrome Recognition in Real Time. Journal of Computersand Systems Sciences 16(2):140-157 (1978). (juan ricardo)

[5] F. Hennie. Crossing Sequences and O¤-line Turing Machines. FOCS1965:168-172.

[6] J. Hopcroft, J. Ullman. Introduction to Automata Theory, Languages,and Computation. Addison-Wesley 1979.

[7] R. Kolpakov, G. Kucherov. Searching for Gapped Palindromes. CPM

2008:18-30. (emilio,sergio)

[8] C. Papadimitriou. Computational Complexity. Addison Wesley,1994.



lxxvi References

[9] P. Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer . SIAM Journal on.Computing. 26(5): 1484-1509 (1997).

[10] M. Sipser. Introduction to the Theory of Computation. Course Tech-nology, 2005.

[11] A. Yao. A Lower Bound for Palindrome Recognition by Probabilis-tic Turing Machines. Technical report #77-647, Standford University1977.

teoria de la computacion via palindromos - carolina mejia

Documents