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 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.
| Página siguiente |