Máquina de turing

´ MAQUINA DE TURING
Pedro Pablo Burrola Ch´vez a Teor´ de la computaci´n ıa o
9 de julio de 2009

Resumen La M´quina de Turing1 es un modelo abstracto de c´mputo creaa o do por Alan Mathison Turing, quien fue un matem´tico, inform´tico a a te´rico, cript´grafo y fil´sofo ingl´s. o o o e Se le considera uno de los padres de la Ciencia de la computaci´n, o siendo el precursor de la inform´ticamoderna. La m´quina fue creada a a dentro de un postulado que fue publicado en Londres, donde basicamente se trataba de explicar como existen sentencias matem´ticas a que son decidibles, esto quiere decir, que si hay una forma espec´ ıfica aplicable que para cualquier sentencia matem´tica, esa forma nos dice a si dicha sentencia es cierta o no. Con lo planteado por Turing se demostr´ que existenproblemas o que ni una m´quina puede resolver. El trabajo hecho por Turing fora maliza todo concepto de algoritmo. Actualmente la m´quina de Turing es el objeto central de estudio a de los te´ricos de la computaci´n. o o

Figura 1: Diagrama art´ ıstico de una m´quina de Turing. a

1

1.

Definici´n formal o

Una m´quina de Turing se define como: MT = (Q,Σ,Γ,s,B,δ,F ), donde: a Q = Conjuntofinito de estados. Σ = Alfabeto de la entrada. Γ = Alfabeto de la cinta. s = Estado inicial, s Q. B = S´ ımbolo blanco o nulo y es el unico s´ ımbolo que se puede repetir infinidad de veces dentro de la cinta de memoria, B Γ. δ = Es la funci´n de transici´n. Q × Γ → Q × Γ x {L,R} , donde L es un o o movimiento a la izquierda y R es un movimiento a la derecha. F = Conjunto de estados finales, F ⊆ Q.2.

Descripciones instant´neas a

La descripci´n instant´nea de una M T se define como una tripleta (α1 qα2 ) o a con α1 , α2 Σ∗ y q Q. La interpretaci´n que se da es: o i. El control de la M T est´ en el estado Q. a ii. El contenido de la cinta desde la primera posici´n es: α1 · α2 · BBBBB... o iii. La cabeza lector/escritor est´ posicionada sobre el primer s´ a ımbolo de α2 . Definici´n: dadauna descripci´n instant´nea I = (X1 ...Xi−1 qXi ...Xn ), poo o a demos distinguir dos tipos de transiciones: I I X1 ... Xi−1 YpXi+1 ...Xn X1 ... Xi−2 pXi−1 Y...Xn si δ(q,X1 ) = (p,Y,R) si δ(q,X1 ) = (p,Y,L) e i>1

Una m´quina de Turing es una representaci´n de un aut´mata que se a o o mueve atravez de una lista de datos. La m´quina consta basicamente de una a cabeza que funge como lector/escritory una cinta de memoria infinita, dividida en celdas donde se pueden almacenar s´ ımbolos de car´cter finito, que a son el alfabeto de la m´quina. Todas las celdas que se encuentren vac´ cona ıas tienen el caracter especial B que es s´ ımbolo blanco. La cabeza es capaz de leer un s´ ımbolo escrito en la cinta, o de borrar el existente e imprimir uno 2

nuevo en su lugar. Las unicas operacionesque se pueden realizar dentro del ´ funcionamiento de la m´quina de Turing es mover la cabeza lector/escritor a hacia la derecha y moverla hacia la izquierda. Todo este proceso se rige por una tabla de acci´n que es la que contiene o los pasos que har´ el aut´mata, las acciones dentro de esta tabla incluyen a o cuatro pasos: i. Leer un car´cter en la posici´n actual. a o ii. Escribir un nuevo s´ımbolo en la posici´n le´ o ıda. Depender´ del car´cter a a le´ y el estado en el que se encuentra. ıdo iii. Mover la cabeza de la m´quina hacia una celda de izquierda o derecha. a iv. Definir cual ser´ el nuevo estado, de acuerdo al car´cter le´ y al estado a a ıdo en el que se encuentra. La m´quina puede dar uso de la cinta de 3 maneras distintas: a i. Como almacenamiento de datos de entrada. ii.Como datos de salida. iii. Como almacenamiento de informaci´n del proceso. o Las aplicaciones que se le puede dar a una m´quina de Turing son: Acepa tadores de lenguajes, reconocedores de lenguajes y algoritmos. El funcionamiento esta regido tambi´n por una tabla de estados que deben e ser de la forma: (estado, valor) → (nuevo estado, nuevo valor, direcci´n) o Lo que en si representa es que a...