Máquina de Turing
Contenido de esta página:
Introducción.
Definición de Máquina de Turing (de una cinta).
Lenguaje de una Máquina de Turing.
Ejemplos de Máquinas de Turing.
Algunos Teoremas sobre las Máquinas de Turing y su lenguaje.
Páginas relacionadas:
Autómatas Finitos.
Ejemplos de Autómatas Finitos y Lenguajes Regulares.
Lema de Bombeo para Lenguajes Regulares.
Teoremas sobre los Autómatas Finitos, los lenguajes regulares, los
lenguajes de Autómatas y los leguajes de las gramáticas libres del
contexto.
Codificación de las máquinas de Turing.
Introducción
La máquina de Turing, presentada por Alan Turing en 1936 en On computable
numbers, with an application to the Entscheidungsproblems, es el modelo
matemático de un dispositivo que se comporta como un autómata finito y que
dispone de una cinta de longitud infinita en la que se pueden leer, escribir o
borrar símbolos. Existen otras versiones con varias cintas, deterministas o no,
etc., pero todas son equivalentes (respecto a los lenguajes que aceptan).
Uno de los teoremas más importantes sobre las máquinas de Turing es que
pueden simular el comportamiento de una computadora (almacenamiento y
unidad de control). Por ello, si un problema no puede ser resuelto por una de
estas máquinas, entonces tampoco puede ser resuelto por una computadora
(problema indecidible, NP).
La notación de las máquinas de Turing es sencilla y exacta, por lo que es más
cómodo trabajar con ellas a la hora de estudiar qué problemas
son decidibles (P) y cuáles indecidibles (NP).
Por el momento la relación de inclusión entre P y NP está por demostrar,
aunque sí sabemos que
P⊆NPP⊆NP
Además, diremos que los lenguajes aceptados por los Autómatas
Finitos (Deterministas o no, con o sin transiciones-ε, con o sin pila...) pueden
ser aceptados también por alguna máquina de Turing.
En esta página veremos la definición de la Máquina de Turing, algunos
ejemplos, su lenguaje y algunos teoremas que la relacionan con los Autómatas
Finitos.
Definición de la Máquina de Turing
Llamamos Máquina de Turing (ó MT) a
M=(Q,Σ,T,δ,q0,B,F)M=(Q,Σ,T,δ,q0,B,F)
donde
Q es el conjunto finito de estados que denotaremos por
q0,q1,q2,...q0,q1,q2,...
Σ es el alfabeto: el conjunto finito de símbolos de entrada.
Τ es el conjunto de símbolos de cinta. El alfabeto es un subconjunto de
Τ.
q0 es el estado inicial: el estado en el que se encuentra inicialmente la
MT.
B es un elemento de Σ: el símbolo en blanco. Se encuentra en todas las
casillas de la cinta que no tienen un símbolo de entrada.
F es el conjunto de estados finales.
δ es la función de transiciones.
La expresión
δ(q,X)=(p,Y,D)δ(q,X)=(p,Y,D)
indica que en el estado q, si la cabeza de la MT señala al símbolo de
cinta X, entonces la MT escribe el símbolo de cinta Y en la casilla actual
(cambia X por Y ) y mueve la cabeza una casilla hacia D (D puede ser
derecha, R; o izquierda, L) y pasa al estado p.
La cinta de la MT está formada por infinitas casillas.
Inicialmente, la palabra de entrada (una concatenación de símbolos del
alfabeto) se encuentra escrita en casillas consecutivas de la cinta y la cabeza
señala al primer símbolo de la palabra. Todas las otras casillas (hacia la
izquierda y la derecha) contienen el símbolo en blanco.
Lenguaje de una Máquina de Turing
El lenguaje de una Máquina de Turing
M=(Q,Σ,T,δ,q0,B,F)M=(Q,Σ,T,δ,q0,B,F)
es
L(M):={w∈Σ∗ : q0w⊢∗ αpβ,p∈F,α,β∈T∗}L(M):={w∈Σ∗ : q0w⊢∗ αpβ,p∈F,α,β∈T∗}
Es decir, las w de Σ* tales que la máquina de Turing alcanza un estado de
aceptación.
Lenguaje Recursivo
Sea L el lenguaje de una máquina de Turing M, es decir, L = L(M), y además,
si w es una palabra de L, entonces M se para (y alcanza un estado de
aceptación)
si w no es una palabra de L, entonces M se para (pero no alcanza un
estado de aceptación)
entonces se dice que L es un lenguaje recursivo.
Problema 1
Máquina de Turing que proporciona el complemento a 1 de un número binario.
Ver solución
Problema 2
Diseñar una máquina de Turing que calcula el número consecutivo de un
número dado en binario.
Ver solución
Problema 3
Diseñar una máquina de Turing que acepta el lenguaje
L={0n1n :n>0}L={0n1n :n>0}
Ver solución
Problema 4
Diseñar una Máquina de Turing que, dada una palabra w del alfabeto Σ={0, 1},
proporciona su reverso, wR .
Ver solución
Teoremas sobre las máquinas de Turing
Lenguaje Recursivamente Enumerable
Recordemos que llamamos lenguaje Recursivamente Enumerable (RE) a los
lenguajes que pueden ser aceptados por una Máquina de Turing.
Teorema 1
Todo lenguaje aceptado por una Máquina de Turing de varias cintas es
Recursivamente Enumerable.
Teorema 2
Sea L = L(M) el lenguaje que acepta una máquina de Turing no determinista M,
entonces existe una máquina de Turing deterministaN que acepta dicho
lenguaje, es decir, L(M) =L (N).
Lenguajes de máquinas de Turing y de Autómatas
Teorema 3
Sea L el lenguaje aceptado por una máquina de Turing, entonces existe algún
Autómata de dos pilas que acepta L.
Teorema 4
Todo lenguaje Recursivamente Enumerable es aceptado por alguna máquina de
tres contadores.
Teorema 5
Todo lenguaje Recursivamente Enumerable es aceptado por alguna máquina de
dos contadores.
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
