Monografias.com > Uncategorized
Descargar Imprimir Comentar Ver trabajos relacionados

Máquinas de Turing (página 2)




Enviado por Pablo Turmero



Partes: 1, 2, 3

Monografias.com

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?

Monografias.com

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.

Monografias.com

Cuestiones
Cómo se puede implementar un programa que calcula la cantidad de variables que aparecen en otro programa?

Monografias.com

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?

Monografias.com

Cuestiones
Cómo se puede implementar un programa como el anterior de manera sistemática, que sirva también para otros programas?

Monografias.com

Cuestiones
Cómo se puede implementar un programa que emula el funcionamiento de otro programa cualquiera a partir de unos datos arbitrarios?

Monografias.com

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?

Monografias.com

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).

Monografias.com

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).

Monografias.com

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.

Monografias.com

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.

Monografias.com

Cuestiones
Lo anterior permite implementar un programa que define una función no calculable? Por qué no?

Monografias.com

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.

Monografias.com

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.

Monografias.com

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).

Monografias.com

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)

Monografias.com

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.

Monografias.com

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.

Monografias.com

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.

Monografias.com

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).

Monografias.com

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.

Monografias.com

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.

Monografias.com

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.

Monografias.com

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.

Partes: 1, 2, 3
 Página anterior Volver al principio del trabajoPágina siguiente 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Categorias
Newsletter