Download Programas y Máquinas de Turing

Programas y
Máquinas de Turing
Roberto Moriyón
Algoritmos: Orígenes de la palabra
• Al-Khwārizmī, astrónomo y matemático
persa, escribió en 825 un tratado en árabe
sobre el Cálculo con Cifras Indúes, que se
tradujo al latín en el siglo XII como
Algoritmos con números indios.
• La raíz es la misma que la de la palabra
Álgebra.
Algoritmos: Definición y tipos
• Conjunto de instrucciones (en un
lenguaje entendido por “la computadora”,
una máquina o persona) que especifica
las operaciones para procesar una
información de entrada arbitraria, y
producir una información de salida
deseada.
– Información: Datos (números, cadenas de
caracteres)
– Tipos de algoritmos: Procedimientos para
realizar tareas, recetas de cálculo, …
Diversidad de tipos de datos
• Los tipos de datos que se utilizan en los
distintos mecanismos computacionales son
equivalentes: cadenas de caracteres,
números en diferentes representaciones, ...
(excepción: el Lambda-Cálculo)
• La equivalencia anterior no es válida si nos
interesa la eficiencia algorítmica.
• Otros tipos de datos no se pueden (o no se
saben) tratar computacionalmente: estado
instantáneo de un ser vivo, …
Tipos de datos
• Los programas son datos y definen
funciones
• Normalmente usaremos cadenas de
caracteres
• A menudo nos restringiremos a cálculos
sobre cadenas que son programas
• Así pues, a menudo los datos serán
programas y definirán funciones
• P(P1, …, Pn): aplicación de la función de P
Algoritmos: Orígenes del concepto
• Algoritmos concretos: se conocen desde
antes de nuestra era
– Método de Euclides para calcular el máximo
común divisor de dos números
– Método de Eratóstenes para obtener la lista
de los números primos
• El concepto de algoritmo data del primer
tercio del siglo XX.
Mecanismos computacionales
•
•
•
•
•
•
•
Lenguajes de programación
Máquinas de Turing (Turing) y variantes
Gramáticas (Chomsky)
Funciones recursivas (Gödel, Herbrandt)
Lambda-cálculo (Church)
Sistemas canónicos de reescritura (Post)
Computación cuántica, …
Mecanismos computacionales, II
• Algunos de los mecanismos anteriores
(lenguajes de programación, máquinas de
Turing indeterministas, funciones recursivas,
lambda cálculo) se utilizan para definir
funciones.
• Otros (máquinas de Turing indeterministas,
gramáticas, reglas de reescritura) se utilizan
para reconocer la pertenencia a conjuntos de
datos (normalmente cadenas de caracteres).
Mecanismos computacionales:
Funciones
• Casi todos los mecanismos anteriores permiten
definir funciones.
• Pueden ser funciones sobre cadenas de
caracteres, sobre números o sobre funciones
• A veces al calcular el valor de la imagen de un
dato (cadena, número o función) mediante una
función no se obtiene ningún valor porque el
cálculo nunca termina
• Las funciones definidas a partir de mecanismos
computacionales son funciones parciales sobre
un dominio universal (*, , )
Mecanismos computacionales:
Funciones, II
• Distintos programas pueden definir la misma
función.
• Por ejemplo, hay infinitos programas que nunca
paran, y todos ellos definen la función de
dominio vacío.
• No todas las funciones en el sentido matemático
se pueden definir a partir de un mecanismo
computacional. Lo veremos más adelante.
Mecanismos computacionales:
Funciones, III
• Ejemplo: Dada una máquina de Turing M
con alfabeto , definimos la función
an, si M para sobre w
f(w) =
 en caso contrario
donde n es el número de pasos que da la
máquina antes de pararse a partir de w.
• A priori no está claro cómo definir f
mediante un mecanismo computacional.
Mecanismos computacionales:
Funciones, IV
• El ejemplo anterior tiene trampa: todo
depende de cuál sea la máquina M.
• Por ejemplo, si M calcula a|w| directamente, f se calcula mediante la misma M.
• Si M se mete siempre en un bucle infinito,
f se puede calcular mediante la máquina
que borra el contenido de la cinta.
• Hay alguna máquina M para la que f no se
puede calcular mediante otra máquina?
Mecanismos computacionales:
Funciones, V
• Otro ejemplo: Hasta 1995 no se sabía
cómo calcular la función f(n), que calcula
el “primer” valor no trivial de x, y y z tal
que xn+yn=zn a menos que no exista, en
cuyo caso le hace corresponder x(n)=0,
y(n)=0, z(n)=0. Tras la demostración del
teorema de Fermat por Wiles, se sabe que
f(2)=(3,4,5) y f(n)=(0,0,0) si n2.
Mecanismos computacionales:
Funciones, VI
• Un mecanismo computacional es más
potente que otro cuando permite
calcular más funciones.
• Teorema: Las máquinas de Turing, los
lenguajes de programación, las
funciones recursivas y el cálculo lambda
tienen la misma potencia computacional.
Tesis de Church
• No hay ningún mecanismo computacional
más potente que los anteriores.
• No es una afirmación demostrable, pues
no hay una definición rigurosa y absoluta
de mecanismo computacional.
Lenguajes de programación
•
•
•
•
Qué os puedo decir que no sepáis ya?
Pueden entrar en bucles interminables.
Es imprevisible cuándo lo hacen.
Incluso es imposible distinguir cuándo
están dentro de un bucle interminable y
cuándo están ejecutando un algoritmo
complejo.
• En teoría permiten definir todas las
funciones calculables (o recursivas).
Lenguajes de programación, II
• Lenguajes minimales:
– Variables
– Tipos de datos básicos (números, cadenas)
– Operaciones y condiciones básicas
(incremento, anteposición, igualdad, …)
– Instrucciones (asignación, condicional)
– Etiquetas y redireccionamiento.
• Posibilidad adicional: Definición de
funciones y recursividad.
Cuestiones
• La definición no recursiva de funciones
añade potencia a un lenguaje de
programación?
• La recursividad añade potencia a un
lenguaje de programación con funciones?
• La eliminación de etiquetas y
redireccionamiento resta potencia a un
lenguaje de programación con
recursividad?
Lenguajes de programación:
Autoaplicación
• En un lenguaje de programación que admite
cadenas de caracteres, los programas pueden
ser datos sobre los que se corren otros
programas.
• Ejemplos:
– Programa que calcula la cantidad de variables que
aparecen en otro programa.
– Programa que calcula el tiempo(P,D) que tardará
otro programa al ejecutarse sobre unos datos dados.
– Programa que calcula el resultado(P,D) de ejecutar
otro programa sobre unos datos dados.
• Observación: Los ejemplos anteriores definen
funciones matemáticas (parciales). Hay
programas que las implementan.
Cuestiones
• Cómo se puede implementar un programa
que calcula la cantidad de variables que
aparecen en otro programa?
Cuestiones
• Cómo se puede implementar un programa
que calcula el tiempo que tarda el
programa
int y = 0;
while (x>0) {
x -= 2;
y++; }
return y;
al ejecutarse sobre unos datos?
Cuestiones
• Cómo se puede implementar un programa
como el anterior de manera sistemática,
que sirva también para otros programas?
Cuestiones
• Cómo se puede implementar un programa
que emula el funcionamiento de otro
programa cualquiera a partir de unos
datos arbitrarios?
Cuestiones
• Cómo se puede implementar un programa
que determina si otro programa arbitrario
no termina nunca de ejecutarse a partir de
unos datos arbitrarios?
Cuestiones
• Criticar el siguiente procedimiento para
construir una función que no sea
calculable:
– Construimos un programa P que ordena los
programas, {Pn}, por ejemplo por orden
lexicográfico (no alfabético!!!).
– Construimos otro programa w que ordena un
conjunto infinito de cadenas de caracteres,
{wn}, por ejemplo por orden lexicográfico.
– Definimos f(wn)=“0”+resultado(Pn, wn).
Observación
• En el caso particular en que el conjunto de
cadenas que elegimos es el de todos los
programas, es decir que wn sea el n-ésimo
programa por orden lexicográfico, el
mismo orden en ambos casos, la
construcción anterior es
f(Q)=“0”+resultado(Q, Q).
Cuestiones
• Criticar el siguiente procedimiento para
construir una función que no sea
calculable:
– Construimos un programa P que ordena los
programas, {Pn}, por ejemplo por orden
lexicográfico (no alfabético!!!).
– Construimos otro programa w que ordena un
conjunto infinito de cadenas de caracteres,
{wn}, por ejemplo por orden lexicográfico.
–…
Cuestiones
• …
• Definimos
• f(wn)=“0” si Pn no se para en tiempo finito a partir de
wn.
• f(wn)=“0”+resultado(Pn, wn) en caso contrario.
Cuestiones
• Lo anterior permite implementar un
programa que define una función no
calculable? Por qué no?
Observación
• En el caso particular en que el conjunto de
cadenas que elegimos es el de todos los
programas, con el mismo orden en ambos
casos, la construcción anterior es
– f(P)=“0” si P no se para en tiempo finito a
partir de P.
– f(P)=“0”+resultado(P, P) en caso contrario.
• Por lo anterior, la condición “P no se para
sobre P” no es calculable.
Diagonalización
• Los argumentos anteriores son ejemplos
concretos de un tipo de demostración
genérico que se utiliza en ámbitos
distintos. Hay más ejemplos.
Diagonalización, II
• Si fn:XY, n0, son funciones, y1,y2Y,
y1 y2 y {xn}n0 son elementos distintos dos
a dos de X, entonces la función

y1 si x=xn y fn(x)=y2
f(x)=


y2 en caso contrario
es diferente de todas las fn.
Demostración: Por definición, fn(xn)f(xn).
Diagonalización, III
• Si {xn}n0 son números reales entre 0 y 1, hay
otros que no están en la sucesión.
La idea es la misma del ejemplo anterior, con
fn(x)=[2nx]%2 (n-ésima cifra binaria de x):
x0 = 0,x00x01x02x03…
x1 = 0,x10x11x12x13…
x2 = 0,x20x21x22x23…
x3 = 0,x30x31x32x33…
y = 0,y00y11y22y33…
(ykk = 1 – xkk)
Máquinas de Turing
• Mecanismo basado en una máquina de estados
con acceso a una cinta infinita de lectura y
escritura que permite definir algoritmos
generales sobre cadenas de caracteres.
• Estados iniciales y finales, función de transición.
• Se pueden utilizar para reconocer palabras con
un criterio de aceptación o para generarlas a
partir de otras.
Ejercicios
• [T1] Programar una máquina de Turing
que elimina los ceros de un número
binario, dejando solamente los unos sin
espacios entre medio.
• [T2] Programar una máquina de Turing
que acepte palabras de la forma (ab)n.
• [T3] Programar una máquina de Turing
que reconoce las palabras que tienen
tantas aes como bes.
EJERCICIO
• [PILA] Dar un autómata a pila que
reconozca al lenguaje {anbcn | n>0} y una
máquina de Turing que emule al autómata
a pila.
Utilización de MdT
• Un lenguaje L es computable si hay una MdT
que reconoce cuándo wL y otra que reconoce
cuándo wL.
• Una función f es computable si hay una MdT
que reconoce cuándo f(x)=y y otra que reconoce
cuándo f(x)y (es decir, si el lenguaje
L={v + “:” + f(v) | v  }
es computable).
Variaciones de MdT
• Indeterministas (para reconocimiento de
lenguajes).
• Con submáquinas (no recursivas o recursivas).
• Con varias cintas.
• Con cinta limitada por un lado.
• Con un alfabeto de dos símbolos.
• Con infinitas cintas (superficie cuadriculada)
Todas ellas son computacionalmente
equivalentes a las MdT normales.
Ejercicios
• [T4] Programar una máquina de Turing
con submáquinas que acepte palabras
que o bien pertenecen al lenguaje del
ejercicio T2 o están formadas únicamente
por aes.
• [T5] Programar una máquina de Turing
con submáquinas que acepte palabras
tales que al separarlas en varias subpalabras separadas por ces, cada palabra
resultante pertenezca al lenguaje anterior.
Máquinas de Turing con
submáquinas
• La ejecución de una transición con una
submáquina en una máquina de Turing es
como sigue:
– Si la submáquina es determinista, se ejecuta a
partir del contenido de la cinta. Si la submáquina
tiene éxito, se da por terminada la transición de
la máquina inicial.
– Si la submáquina es indeterminista, la máquina
inicial puede pasar indeterministamente a
contener en la cinta cada uno de los contenidos
de la cinta en la submáquina en estados de
aceptación, pasando al estado siguiente.
Máquinas de Turing con
submáquinas, II
• Lo anterior se puede describir mediante pasos atómicos
como sigue:
– En cada momento de la ejecución hay una pila de máquinas en
funcionamiento, cada una apuntando a una casilla de la cinta.
– En cada paso si es posible se ejecuta una transición de la
máquina que está sobre la pila. Si la transición tiene asociada
una submáquina, se pone en marcha con la misma cinta y se
introduce sobre la pila. Si no se puede aplicar ninguna
transición, en caso de que la última máquina esté en un estado
final (de aceptación) se extrae de la pila.
– La máquina tiene éxito si la pila se queda vacía.
• La forma de ejecución anterior se puede aplicar también
en el caso de MdT con submáquinas y recursividad.
EJERCICIO
[SUBMÁQUINA]
• Dar una máquina de Turing con
submáquinas y otra máquina de Turing sin
submáquinas que emule a la primera.
• Se puede aplicar el mismo procedimiento
a cualquier máquina de Turing con
submáquinas? Debería estar claro cómo
generalizar la construcción a cualquier
otra MdT con submáquinas.
EJERCICIO
[VARIAS CINTAS]
• Describir el funcionamiento de una MdT
con varias cintas.
• Dar un ejemplo de una MdT que utilice
dos cintas y otra MdT normal que emule a
la primera. Debería estar claro cómo
generalizar la construcción a cualquier
otra MdT con varias cintas.
EJERCICIOS
• [CINTA LIMITADA] Dar un ejemplo de una
MdT con cinta limitada por la izquierda y
otra MdT normal que la emule. Debería
estar claro cómo generalizar la
construcción a cualquier otra MdT con
cinta limitada por la izquierda.
• [SÍMBOLOS] Dar un ejemplo de una MdT
con 3 símbolos y otra con 2 símbolos que
la emule. Debería estar claro cómo
generalizar la construcción a cualquier
otra MdT con más de 3 símbolos.
Codificación de MdT
• Las máquinas de Turing se pueden
codificar codificando cada transición y
concatenando los resultados con
separadores.
• De esta forma se define un lenguaje de
programación en el que hay tres variables:
El estado de la máquina y las dos partes
en que se divide la cinta.
Ejemplo de codificación de MdT y
de sus estados instantáneos
EstIni.EstFin
aa
0
ba
aa+
;Trans,…
+
1
-
ba-
ba4
aa
aa+
2
ba-
ba-
+
3
aa
+
:Cinta1EstadoCinta2
0.24
;0a1a+,0b4a-,1a2a+,1b0a,2a3a+,2b1a-,3a4a+,3b2a,4a0a+,4b3a:aa2bab
Máquina de Turing universal
• Hay máquinas de Turing capaces de
emular el funcionamiento de otras
cualesquiera a partir de su codificación.
1
AplicaTransición
BuscaTransición
:Comprueba
0
2
Cuestión
• Comparar lo anterior con la emulación de
programas.
EJERCICIO
• [BUSCA TRANSICIÓN] Escribir la
submáquina BuscaTransición de la MTU
• [APLICA TRANSICIÓN] Escribir la
submáquina AplicaTransición de la MTU
• [COMPRUEBA] Escribir la submáquina
Comprueba de la MTU
EJERCICIOS
• [EMULA DETERMINISTA] Dar una MdT
indeterminista y otra MdT determinista que
emula su funcionamiento.
• [MTU DETERMINISTA] Dar una MdT
determinista que emule el funcionamiento
de una MdT arbitraria, determinista o no
Problema de la parada
• Dada una MdT M y una palabra w, ¿llega
M a un estado de parada a partir de w?
• Solución del problema: Sería
– MdT que, al ejecutarse sobre una codificación
de M + w, se para si y sólo si M no lo hace a
partir de w.
• No tiene solución.
Demostración: Análoga al caso de
programas.
EJERCICIO
• [PARA PARA 1] Suponiendo que el
problema de la parada tuviera solución,
escribir una MdT, PP, que utilice a la
anterior como submáquina que, al
ejecutarse sobre la codificación de otra
MdT M + una palabra w, se pare en el
estado 0 si M lo hace sobre w, y en ese
caso deje sobre la cinta el valor calculado
por M, y se pare en el estado 1 si M no lo
hace sobre w.