Programas yMá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| directamen-te, 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 n2.

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:XY, n0, son funciones, y1,y2Y,

y1 y2 y {xn}n0 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}n0 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, confn(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 wL y otra que reconoce cuándo wL.

• 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 subpala-bras 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

;Trans,…

:Cinta1EstadoCinta2

0.24

;0a1a+,0b4a-,1a2a+,1b0a-,2a3a+,2b1a-,3a4a+,3b2a-,4a0a+,4b3a-

:aa2bab

0 1

24

3

aa+

aa+

aa+aa

+

aa+

ba-

ba-

ba-ba

-

ba-

Máquina de Turing universal

• Hay máquinas de Turing capaces de emular el funcionamiento de otras cualesquiera a partir de su codificación.

1BuscaTransición

AplicaTransición

2:Comprueba

0

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.