-------------------------- LA TESIS DE TURING ----------------------
cualquier proceso computacional".
en la actualidad, pero nadie ha podido producir un modelo computacional ampliamente aceptado que supere el poder del modelo de Turing.
------- DEFINICION Y PROPIEDADES DE LAS MAQUINAS DE TURING. ------
matas finitos en que constan de un mecanismo de control y flujo de entrada que
to de estados. Uno de estos estados se denomina estado inicial y representa el e a su estado de parada.
rear los datos de la cinta y modificar las celdas que desee sin alterar las dem
Al utilizar la cinta para fines de almacenamiento auxiliar, es conveniente queen estar codificados los datos de entrada iniciales, y un conjunto, posiblement
da, escribiendo en ella un espacio en blanco. Por esto, con frecuencia se consi
e movimiento comprende mover la cabeza una celda a la derecha o a la izquierda
La cinta puede considerarse o infinita o arbitrariamente extensible en ambas d
DEFINICION FORMAL DE LA MAQUINA DE TURING:
Un elemento de S llamado estado inicial.
S= {q0,q1,..qn} , = {s0, s1,...,sm} .
".
over la cabeza una celda a la izquierda (Left) y pasar al estado q".
over la cabeza una celda a la derecha (Right) y pasar al estado q".
damente hasta llegar al estado de parada ( esto quiere decir que en ciertas con, ya que su programa interno puede quedar atrapado en un ciclo sin fin). En otr
blanco, con la cabeza sobre la celda que contiene la z.
ring.
Ejemplo:
inicial=q1
((q2,1) , (R,q2))
((q2,b) , (1,q3))
((q3,1) , (R,q3))
((q3,b) , (1,q1)) }
Funcionamiento:
en el estado q2.
-Si lo que se lee es 'b', se procede a escribir en esa celda de la cinta un '1'or lo que enseguida realiza un movimiento a la derecha y continua en q3.
---------------------- EVALUACION DE CADENAS. --------------------
Las MT se pueden utilizar para evaluar cadenas y determinar su pertenencia a u
con L(M).
ir que simplemente se detengan o insistir en que respondan con un mensaje de acse detenga, a menos que se especifique lo contrario.
------- LENGUAJES ACEPTADOS POR MAQUINAS DE TURING. -------
gulares e independientes del contexto.
de las reglas de reescritura pueden consistir en cualquier cadena finita de terminales y no terminales, siempre y cuando exista por lo menos un no terminal en el lado izquierdo.
es estructurados por frases. Estos son los lenguajes que pueden definirse "gramaticalmente", en el sentido de que sus estructuras de cadenas se pueden analizan la clase de los lenguajes estructurados por frases.
----------- LIMITACIONES DE LA MAQUINA DE TURING: ----------
r decir, uno de los ejemplos que se muestran mas adelante, add2, faltase el sig
posible de pasos que pueden ocurrir.
Este es el problema de la parada (halting problem):
entrada.
a este problema.
-------- EL SIMULADOR DE LA MAQUINA DE TURING. -----------
y un creciente desarrollo de programas que presentan lo que se considera comportamiento inteligente. Muchos de estos programas inteligentes o que aparentan sepoco tiempo.
EL ALGORITMO DEL SIMULADOR:
indefinido, el programa mt termina.
y actualizar el estado ej. (R q2). Es decir, en ese momento se tuvo una
4.- Regresar al paso 1.
----------------- CONCLUSIONES : ---------------
a sencillez las hace inadecuadas para la mayor parte de las necesidades calculatorias. Idealmente, las operaciones que se pueden realizar con una maquina de Turing se deben realizar con las modernas computadoras de la actualidad; no obstante, hay que tomar en cuenta muchas consideraciones tales como las limitacionea cabo.
imula una cinta de entrada infinita en ambos extremos, la cual se puede desplaza cinta en la cual se encuentra en ese momento la cabeza lectora/escritora de l
imientos: no requiere gran cantidad de memoria y necesita poco espacio en disco
---------------- OTROS TRABAJOS FUTUROS: ------------------
-------------- EL MANUAL DE USUARIO: --------------
LOS REQUERIMIENTOS DEL SISTEMA:
-Computadora ibm pc xt o' at (o compatible), con MSDOS y 640K
de memoria ram.
-Un disquete o disco duro con aproximadamente 110 KB de espacio
disponible para los siguientes archivos.
* mulisp.com
* windows.lsp
* turing.lsp
* turing.hlp
* dup.mt
* suma.mt
* add2.mt
* resta.mt
COMO USAR EL SIMULADOR DE LA MAQUINA DE TURING:
*Arrancar desde DOS:
c:\mulisp turing
En este momento se encuentra en el entorno de mulisp (prompt $) y si lo desea puede trabajar en el, en forma normal.
<ESC>
<SPACE> y <TAB> mueve hacia la derecha y <RETROCESO> hacia la izquierda.
-Parametros,
-Step,
-Correr,
-Ejemplos,
-Load,
-Opciones,
-Quit.
Elegir alguna de las siguientes sub-opciones:
-Edo_inicial,
-Pos_cinta,
-Cinta (entrada),
-Reinicializar.
ejecutar el programa mt.
Ej.- Q4 <enter>.
Los valores aceptados van desde 0 hasta (length entrada) - 1.
Por ejemplo si la entrada es '(b 1 1 b) es desde 0 a 3.
Ej.- 0 <enter>.
programa mt.
Ej.- (b 1 0 1 1 b) <enter>.
D2.MT.
Ej.- 2<enter>.
Ejecutar el programa mt.
A) Presionar <ESC> y confirmar.
B) Cada vez que el step llega a cero y el programa no ha terminado se
"continuar (Y/N)? "
si la respuesta es Y (si), volvemos a ejecutar el programa a partir
del momento donde se quedo.
C) Cuando el estado buscado es indefinido.
Ejemplos a elegir:
b, 1, y/o 0.
-Suma (s0,s1,s2):Sumar dos valores (formados por 1 y/o 0) separados
-Resta (s0,s1) :Realiza la resta positiva de dos valores formados
Cargar un programa mt. Elegir alguno de los archivos que se presentan y teclear Ej.- eleva.mt<enter>.
Elegir alguna de las sub-opciones:
-Color
-Dos
Mediante la tecla <TAB> nos podemos posicionar sobre lo que deseamos cambiar:
Frame: Cuadro interior y letras de titulo.
Working: Estado del programa mt y su corrida.
Prompt: Color del prompt de opciones.
Status: Mensaje del programa en la parte inferior de la pantalla.
Bckgrnd: Fondo en pantalla (se aconseja negro=0).
Border: Marco de pantalla.
, presionar <ESC>.
.
Para regresar a turing.lsp teclear:
exit<enter>.
Abandonar turing.lsp.