Copy Link
Add to Bookmark
Report
SET 033 0X09
-[ 0x09 ]--------------------------------------------------------------------
-[ Maquinas de Turing ]------------------------------------------------------
-[ by elotro ]-------------------------------------------------------SET-33--
.--_ _--.
| |__| |
| | A Q U I N A S D E T U R I N G
| |\__/| |
| | | | por elotro elotro.ar@gmail.com
|___| |___|
Es mecanizable el proceso de freir un huevo? O de estacionar un auto?
Tal vez el de hacer una suma con lapiz y papel?
O buscar errores en el codigo de un programa de computadora?
Por mas que progresen las computadoras, esta probado que existen
problemas que nunca lograran resolver...
Veremos que hay que tener mucho cuidado al hablar de cuando algo es
mecanizable, o sea que se puede solucionar por un procedimiento
mecanico efectivo. Para entender que significa esto se idearon unos
dispositivos inmaginarios o abstractos que toman el rol de las
computadoras modernas.
Antes que nada, conozcamos al genio detras del telon : Alan Turing
Alan Mathison Turing fue un destacado matematico y logico britanico.
Trabajo en la Universidad de Princeton y formo parte del Foreing Office
Britanico. Fue director adjunto del Manchester Automatic Digital Machine
y estudio las capacidades de las maquinas pensantes y desarrollo metodos
matematicos y fisicos para el estudio de la morfogenesis.
1. Comenzar por lo simple @
@%@%@%@%@%@%@%@%@%@%@%@%@
Que es una maquina de Turing? Se han ideado varios tipos de maquinas de
Turing (MT), pero se ha probado que todos los tipos pueden resolver los
distintos problemas, con lo cual basta que describa solo un tipo para que
fijen la idea.
La idea de una MT es definir una computadora minima, que pueda hacer todo
lo posible. Basicamente, tener una maquina de Turing significa tener:
a) Un vocabulario (conjunto finito de simbolos), de por lo menos 2 simbolos
diferentes; dentro de este vocabulario tenemos un simbolo especial llamado
'blanco' y que represente la ausencia de otro posible simbolo.
b) Una cinta con infinitos casilleros, tantos como numeros naturales existen
y numerados del 1 en adelante, junto con una cabeza lectora escritora.
c) Un conjunto finito de estados, la maquina estara en cada uno de ellos en
cada instante
d) Un conjunto finito de instrucciones, o programa
e) Una configuracion inicial de la cinta, es decir, hay finitos casilleros
con simbolos no blancos en la cinta y ademas una posicion inicial de la
cabeza lectora-escritora.
La cabeza lectora-escritora apunta a un unico casillero de la cinta en cada
instante; lee y escribe los posibles caracteres del vocabulario de la maquina
y puede avanzar o retroceder una posicion cada vez que se le pida.
Es el programa (d) el que determina las acciones de la maquina.
2. De vuelta al principio @
@%@%@%@%@%@%@%@%@%@%@%@%@
Entonces: Que es un programa?. Un conjunto de instrucciones.
Esta concepcion de programa implica que estas instrucciones no tienen que
estar ordenadas, vale decir, no forman una secuencia.
Cada instruccion dice algo asi como: Si el simbolo al que apunta la cabeza
es X, y el estado actual es E, entonces escribir en ese lugar el simbolo Y,
mover la cabeza una posicion (izquierda o derecha), o no moverla, y pasar
al estado F.
Todos estos datos conforman la instruccion.
3. Vida, pasion y muerte de una MT @
@%@%@%@%@%@%@%@%@%@%@%@%@%@%@%@%@
Una MT 'vive' haciendo una serie de operaciones sobre una cinta infinita
en ambos entidos, y pasando eventualmente de un estado a otro entre la
ejecucion de estas operaciones. Parara cuando no encuentre la operacion
necesaria, o bien, cuando se le diga que pare. [que pare, no que se le pareXD]
Componente a componente
"""""""""""""""""""""""
Una MT es basicamente un conjunto finito de instrucciones, cada una de ellas
de la siguiente forma:
Si el estado actual es E, y el simbolo de la cabeza lectora es S, entonces
haz lo siguiente:
- Imprimir en el lugar leido el simbolo T (que puede ser igual a S, o bien
otro simbolo diferente)
- Moverse hacia el lado X (X puede ser izquierda o derecha, o nada, es decir
que no se mueve)
- Pasar al estado U (puede ser cualquier estado, inclusive E)
Por ejemplo, esta es una posible instruccion de una MT:
Si el estado actual es 0, y el simbolo de la cabeza lectora es A, entonces:
- Imprime en el lugar leido el simbolo B
- Muevete a la derecha
- Pasa al estado 1
Haciendolo facil
""""""""""""""""
Para poder escribir las instrucciones de una forma comoda con pocos
simbolos, se pueden escribir de esta manera:
0,a,b,D,1
Significa que si el estado es 0 y se lee a, escriba b, ir a la derecha y
pasar al estado 1.
4. El limite de lo computable @
@%@%@%@%@%@%@%@%@%@%@%@%@%@%
Alan Turing ideo su maquina mucho tiempo antes de que existieran las
primeras computadoras. En su epoca se trabajaba en forma teorica y se estaba
consciente de la mayoria de los problemas de computabilidad [que palabrota]
que se conocen hoy en dia.
Todo esto se sigue estudiando a nivel teorico, independientemente del
progreso que se produzca con la aparicion de nuevas concepciones practicas.
[lease como los procesadores que intel saca al mercado y que los de latino
america no podemos comprar por falta de $]
En realidad, el 99% de lo que se conoce como progreso en algun sentido,
corresponde a mejoras y superacion de la calidad y la eficiencia, e incluso
oferta de mejores facilidades, pero para realizar lo ya realizable
anteriormente. Pero las computadoras siguen resolviendo los mismos problemas
que a principio de siglo, solo que mas rapida y eficientemente.
[ o sea que si corriendo Linux en un 386 sacaba 2+2 y me daba 4, corriendo
Windows en un Pentium 4 generalmente se cascara el sistema, pero podria dar
4 tambien y en una forma visual y mas bonita [y cara]]
5. Nada nuevo bajo el sol @
@%@%@%@%@%@%@%@%@%@%@%@%
Todo lo que hacen las computadoras modernas, es decir computar o calcular
[ no creas que si tienes una SET en tu disco, dentro de el hay papeles con
todos los articulos ] , tambien lo puede hacer una MT apropiada, siempre que
se disponga del tiempo suficiente y del tamanio de cinta que se necesite.
No quiero decir que sea conveniente calcular una raiz cuadrada en una MT
[ porque cuando termine ya habra salido SET 680 :)], pero es posible calcular
potencias, logaritmos, ordenar, clasificar, buscar en listas. Todas las
operaciones que tu, programador, estas acostumbrado a hacer.
[no me digas que nunca has tocado un Qbasic, un gcc o un Logo por lo
menos, porque no te voy a creer ]
Lo que muestra que esto es una evidencia a favor de que las maquinas de
Turing representan las funciones computables, o sea que pueden calcular las
cosas que deberians ser calculadas por medios mecanicos.
Pero, Que es un procedimiento mecanico? Hasta hoy, no se esta en un acuerdo
absoluto, pero se cree que se esta en el camino de la respuesta al estudiar
estos procedimientos.
6. Falta de decision @
@%@%@%@%@%@%@%@%@%@%
Se podria decir: 'Bueno, pero que problemas no son computables?' Los hay
muchos, como el siguiente.
Se sabe que en matematica no siempre es facil encontrar soluciones a
las sumas algebraicas. Normalmente en la escuela se ensenia a encontrar
soluciones de ecuaciones lineales, cuadraticas y otros tipos. Un matematico
en su carresa aprende a resolver numerosos tipos de ecuaciones. Pero los
metodos para resolver polinomios (son ecuaciones de grado arbitrario, como
por ejemplo: Que valores de x satisfacen x^5 + 3 - x^3 - x^2 - 6x + 1 = 0)
no son en general uniformes, en los que se deben hacer algunos pasos al tanteo
junto con otros mas complejos; y en los que no se garantiza la posibilidad
de encontrar la solucion entera.
Es decir que no hay un algoritmo que resuelva el caso general. Claro que
puede haber uno si la ecuacion es sencilla como la anterior.
[me parece qe no es tan sencilla porque aun estoy tratando de resolverla]
La ecuacion puede ser resuelta usando un metodo de fueza bruta, probando
todos los numeros reales hasta que se encuentre la solucion. Pero lo que
estoy exponiendo aqui es que no existe un algoritmo que pueda resolver una
ecuacion si en principio esta puede ser cualquiera.
Si los algoritmos no son otra cosa que MT, esto es asi y ya debes saber que
el gato no tiene 5 patas. Y como las computadoras no son otra cosa que MTs
aunque mas rapidas y sofisticadas, entonces ninguna computadora puede
resolver un problema de este tipo, hasta tanto no cambie la nocion de
algoritmo y computable.
7. Datos insuficientes @
@%@%@%@%@%@%@%@%@%@%@%
Existe lo que se denomina tesis de Church. Alonso Church fue un logico
matematico de principios de siglo que se destaco, junto con otros, por sus
investigaciones en la teoria de la computabilidad, es decir, que cosas son
computables y cuales no lo son. En esta tesis se propone lo que se entiende
formalmente como algoritmo.
Sabemos que un algoritmo es todo lo que de alguna manera efectiva da un
metodo para computar algo. Esta computacion puede hacerce de varias maneras
posibles, pero basta con que pueda seguirse mecanicamente sin necesidad de
esfuerzo adicional para que se llame metodo efectivo. Esto que resulta tan
sencillo de expresar no es tan facil a la hora de precisar matematicamente
los conceptos.
Como puedes ir observando, al plantear un problema surgen naturalmente
dudas cerca de la posibilidad de resolverlo. Por esta razon, Church propuso
su tesis en la cual da formalmente distintas nociones de cuando algun
procedimiento, merece ser llamado algoritmo. Ademas, prueba que todas esas
nociones son equivalentes, en el sentido de que aceptando cualquiera de ellas
como lo que se define a algoritmos posibles, se obtienen exactamente
algoritmos identicos.
Ni uno mas, ni uno menos. Esto sirve como evidencia de que la nocion de
algoritmo como algo efectivamente computable es la que se afirma en esa tesis.
8. Volver al futuro @
@%@%@%@%@%@%@%@%@%@
La tesis de Church no puede ser demostrada. Esto no es debido a carecer
de elementos matematicos o conocimiento suficiente. Se debe a que puede haber
varias nociones distintas de cuando algo constituye un algoritmo, unas sin
desmerecer las otras, pero no se puede saber con certeza si estas nociones
dan o daran alguna vez procedimientos mecanizables. Es decir, si alguna
computadora los puede llevar a cabo.
Lo que se hace en lugar de demostrar esta tesis, es dar mas evidencia a
su favor. (Tambien pueden haber evidencias en contra, pero no es muy probable.
Cada vez que alguien descubre o inventa un mecanismo abstracto de computo
que parezca representativo de lo que puede se un algoritmo de la manera mas
general posible, se trata de probar que resulta equivalente o puede conseguir
los mismo computos que aquellos realizados por Maquinas de Turing, por
ejemplo.
Ademas, todas las variantes que se pueden presentar al esquema de maquinas
de Turing, conducen al mismo concepto de algoritmo. Vale decir, si agregamos
2, 3, ... cintas, cabezas, mas simbolos, mas movimiento similares, etc.. no
tendremos otra nocion de algoritmo. Podremos simplemente resolver los mismos
problemas de antes, solo que de manera mas eficiente. [lo que pasa con linux
y windows]
Con las computadoras de hoy en dia pasa exactamente esto. Todas en alguna
manera son versiones sofisticadas de maquinas de Turing (paradojicamente, y
en la practica, tienen memoria limitada, a diferencia de las MT.) No pueden
resolver un problema que una MT no pueda.
Pero, Podra algun dia cambiar la nocion de algoritmo? Posiblemente, si
las computadoras progresan lo suficiente como para permitir esto. Deberian
no aumentar precisamente en velocidad, aunque esto sea tambien importante;
sino tambien en poseer algun tipo de operacion primitiva que permita otros
tipos de operaciones no conocidas o exploradas hasta el presente.
Quizas sea en la representacion de los datos. Quizas sea en la secuencia
de los computos. Quizas nunca nadie lo sepa.
8. Variantes al esquema de MT @
%@%@%@%@%@%@%@%@%@%@%@%@%@%@%
Estas son las principales variantes a los esquemas de MT que suelen
aparecer en la literatura de computacion teorica. Todas pueden usarse y
combinarse, dando como consecuencia distintos estilos de MT, y por tanto,
modelos diferentes de computadoras. Pero puede demostrarse formalmente que
todos esos modelos son matematicamente equivalentes. Esto es, no hay ninguna
funcion matematica que sea computable usando un posible modelo de maquina y
que no lo sea por otro modelo.
Por ejemplo, si una funcion puede computarse usando 2 cintas, entonces
tambien podra ser resuelta usando una sola cinta [ mira mas abajo ]. Si una
funcion no puede computarse sin una instruccion especial de parada (entre
otras), entonces tampoco podra computarse si se agrega esta instruccion de
parada, no inporta en que instruccion se coloque.
Respecto de lo ilimitado de la cinta : puede ser ilimitada a izquierda o
derecha, o en un solo sentido.
Numero de cintas : puede haber 1, 2 o mas cintas (incluso de distintos
tipos), con la condicion de que una de ellas sea infinita.
Alfabeto: Debe ser un conjunto finito de simbolos, de uno o mas simbolos.
Si hay uno solo, debe existir el 'blanco' o ausencia de simbolo. En caso
contrario, todos los casilleros de la cinta tendran el mismo contenido
y no habra computo alguno.
Conjunto de estados: Debe ser finito.
Conjunto de instrucciones : Debe tambien ser finito.
Instruccion de parada : Puede haber o no haber. Si no la hay, entonces se
supone que cada vez que no hay una instruccion que contemple el estado de
la maquina y el simbolo actual, esta debe parar.
Tipos de acciones : Las accines pueden ser del tipo escritura de un
simbolo y movimiento hacia un lado, o bien contar separadamente con dos
tipos de instrucciones, de escritura de un simbolo y otra de movimiento
hacia un lado.
8. El huevo o la gallina @
%@%@%@%@%@%@%@%@%@%@%@%
Otro problema clasico probablemente indeducible [que palabrotas :) ] es
es de la parada de un MT. Que significa esto?
Es considerar la construccion de un algoritmo que reciba como entrada
una MT incluyendo los datos de la cinta y la posicion inicial de la cabeza
y tal que el decida si esa maquina parara o ciclara indefinidamente.
No es posible construir ese algoritmo con ningun lenguaje conocido, ni
jamas podra hacerse, hasta tanto no cambie la nocion de algoritmo, tal como
plantee antes.
Esto es equivalente a decir que no existe una MT que pueda recibir como
entrada a otra MT arbitraria y decir SI o NO segun esta ultima pare o no
pare.
Por supuesto, existen variantes a estos problemas, y tantos otros, que
tambien son indecidibles.
[ un ejemplo de problema indecidible es cual de todos los windows es
el que peor funciona. Me contaron que el XP el que va ganando.. ]
8. Mira a donde fuimos a parar @
%@%@%@%@%@%@%@%@%@%@%@%@%@%@%
Se duda bastante que alguna vez exista una computadora con operaciones
escencialmente tan diferentes que permita resolver problemas que hasta hoy
se consideran no computables. [si leiste bien veras que no es imposible, sino
que es demasiado complejo para la tecnologia de hoy en dia]
A veces se especula con su existencia puramente teorica. Por ejemplo,
supongamos que podemos resolver el problema de la parada de una MT con una
simple consulta a un cierto algoritmo. Esto se conoce como el uso de oraculos.
Entonces, tiene sentido estudiar que otros posibles problemas hasta ahora
indecidibles podran ser decididos de esta manera.
No voy a tocar este tema ahora [porque me esta dando suenio], pero sabremos
que aun asi habra otros problemas indecidibles. O sea, que ni agregando ciertos
oraculos se podran resolver todos los problemas. [ como el problema de que
estoy soltero ]
8. Y entonces que ? @
%@%@%@%@%@%@%@%@%@%
Luego de la decepcion que representa enterarse de algo asi como que no
todo es algoritmizable [ alguien aviseme si esa palabra existe], se abren
nuevas puertas a la computacion teorica. A saber, interesa cada vez que
alguien propone un problema bien planteado, el hecho de que sea solucionable
computacionalmente [ esta palabra tambien ] o no.
Luego, si se descubre que es computable, entonces no solo queda pendiente
encontrar algoritmos que lo resuelva, sino que hay que encontrar algoritmos
que lo resuelvan de la manera mas eficiente posible. De esto se ocupa el area
conocida como Complejidad Computacional.
Si en cambio, se descubre que no es computable, entonces aun quedan cosas
por hacer. Los teoricos trabajan a veces viendo la forma de pasar a resolver
por lo menos el problema de forma parcial.
Por ejemplo, asumir ciertas hipotesis, restringiendo el problema original
y tratar de esa manera de encontrar algoritmos que resuelvan esos casos.
Tambien interesa ver un poco por donde se hallan los limites de lo
computable a lo no compuable.
8. Moraleja @
%@%@%@%@%@%
La moraleja de este texto no es solo que descubras otros metodos de
computacion, sino tambien que aprendas lo siguiente:
Ni el Pentium, ni tarjetas perforadas, ni Maquinas de Turing hacen la
felicidad. Pero hay maneras y maneras de vivir feliz...y computar.
9. Ojo ! Todavia no termina @
%@%@%@%@%@%@%@%@%@%@%@%@%@%
Se que estas aburrido leyendo esto, pero robo otros minutos de tu
tiempo para que veas este simulador de MT hecho en Quick Basic. [ perdon
por que sea en este lenguaje, pero hace poco que comence a aprender C
y C++, y no tenia mucha confianza como para pasarlo de lenguaje ]
<++> turing.bas
' Simulador de Maquinas de Turing
' Derechos reservados a Ariel Arbiser (c) 1994
' Extraido de la revista Byte Argentina, edicion febrero de 1994
' Si el autor original tiene algun problema con la reproduccion de este codigo
' en algun medio fisico o electronico, por favor comunicarse a los mails
' indicados arriba.
' Recomendado compilar con Quick Basic. Su compilacion en Fbasic u otro
' similar puede necesitar alguna modificacion de sintaxis en las declaraciones
' de subrutinas y matrices
' Comentarios son precedidos por comillas sencillas -> '
' COMIENZO DEL PROGRAMA
' declaraciones de subrutinas
DECLARE SUB Parar (m$)
DECLARE SUB Tecla ()
DECLARE SUB MuestraCinta (cinta$(), posic%)
DEFINT A-Z
' numero maximo de instrucciones y tamanio de la cinta
CONST true = 1, false = 0
CONST maxni = 50, maxcinta = 200
' declaracion de matrices
DIM insest(maxni), inscar$(maxni), insnuevo$(maxni), insmov$(maxni),
inspasa(maxni) 'esto va en la linea de arriba pero lo puse aca porque se
'pasa de las 78 columnas
DIM cinta$(maxcinta)
' inicializa la pantalla
SCREEN 0: WIDTH 80: CLS
' lee linea de comando
i = INSTR(COMMAND$, " ")
IF i = 0 THEN
LINE INPUT "Archivo de programa : "; f$
ELSE
f$ = MID$(COMMAND$, i)
END IF
f$ = LTRIM$(f$)
' abre archivos con datos de la maquina
OPEN f$ FOR INPUT AS 1
' lee cinta
INPUT #1, tamcinta
FOR c = 1 TO tamcinta
INPUT #1, cinta$(c)
NEXT
' pone a cero el numero de instrucciones
ni = 0
' lee "programa"
' numero instrucciones
INPUT #1, ni
' instruciones
FOR r = 1 TO ni
INPUT #1, insest(r), inscar$(r), insnuevo$(r), insmov$(r), inspasa(r)
NEXT
' ejecuta
' setea el numero de instrucciones a cero
niejec = 0
' setea la posicion de la cabeza a 1
posic = 1
' inicializa estado de la cinta
estado = 0
LOCATE 3: COLOR 11: PRINT STRING$(80, "=")
' ciclo principal
DO
' se paso ?
IF posic > maxcinta OR posic < 0 THEN Parar "Error: posicion fuera de la cinta"
' exhibe cinta
MuestraCinta cinta$(), posic
' ejecuta instruccion
car$ = cinta$(posic)
' busca simbolo en instrucciones
i = 0
enc = false
DO WHILE i < ni AND enc = false
i = i + 1
IF inscar$(i) = car$ AND insert(i) = estado THEN enc = true
LOOP
VIEW PRINT 4 TO 25
LOCATE 23
COLOR 13
PRINT "Estado: "; estado, "caracter: "; car$
' si no se encontro simbolo
IF enc = false THEN Parar "Maquina paro por ausencia de instruccion"
' si no
COLOR 12: PRINT "Ejecutando instruccion #"; i; "escribe "; insnuevo$(1); ,
" accion: "; insmov$(i); ", pasa al estado "; inspasa(i)
' ^ ^ ^ ^ ^ ^
' | | | | | |
'eso va en la linea de arriba porque se pasa de 80 columnas
' actualiza estado
estado = inspasa(i)
' actualiza cinta
cinta$(posic) = insnuevo$(i)
' actualiza cabeza
SELECT CASE LCASE$(insmov$(i))
CASE "i": posic = posic - 1
CASE "d": posic = posic + 1
CASE "s": Parar "Instruccion de parada"
CASE ELSE
END SELECT
' incrementa el numero de ejecuciones
niejec = niejec + 1
COLOR 10: PRINT "Nro instrucciones ejecutadas : "; niejec
PRINT
' espera por una tecla
Tecla
' cicla indefinidamente o hasta detenerse
LOOP
SUB MuestraCinta (cinta$(), posic)
CONST anchocinta = 20
STATIC posicini
COLOR 12
VIEW PRINT 1 TO 3
LOCATE 1, 1: PRINT SPACE$(160)
LOCATE 1, 1
' Cinta visible
IF posic < posicini OR posic > posicini + anchocinta - 2 THEN posicni = posic
LOCATE 1: PRINT " ";
FOR i = posicini TO posicini + anchocinta
PRINT "|";
IF i > 0 AND i <= maxcinta THEN
COLOR 11: PRINT cinta$(i)
ELSE
COLOR 7: PRINT ".";
END IF
COLOR 12: PRINT " ";
NEXT
PRINT "|";
' dibujar cabeza
LOCATE 2, 1
t = 4 * (posic - posicini) + 4
' dibujarla
COLOR 11: PRINT SPACE$(t); "^"; " ";
END SUB
SUB Parar (m$)
COLOR 15: PRINT m$
Tecla
SYSTEM
END SUB
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
SUB Tecla
LOCATE 23, 21
PRINT "Pulse una tecla"
a$ = INPUT$(1)
LOCATE 23, 21: PRINT SPACE$(15)
END SUB
<-->
Este es el modo en que opera el programa: Abre un archivo de texto ascii
cuyo nombre lo ingresa el usuario, e interpreta cada una de las lineas de la
manera siguiente.
La primera linea debe decir cuantos casilleros de la cinta se definen
inicialmente segun su contenido. A continuacion se dan los caracteres escritos
uno por uno, en orden, desde aquel en que la cabeza de la maquina comienza
a leer. La siguiente linea dice el numero de instrucciones que posee la
maquina.
Por ultimo, vienen las lineas de las instrucciones que posee la maquina.
( fijate en Vida, Pasion y muerte de una MT para ver su formato), tantas
como se indico en la linea anterior. El formato del archivo, es este:
[n: numero de caracteres iniciales en la cinta]
[caracter 1]
[caracter 2]
......
......
[caracter n]
[m: numero de instrucciones de la maquina]
[instruccion 1]
[instruccion 2]
......
......
[instruccion m]
El programa luego simula el funcionamiento de la maquina. Se detiene
cuando no se encuentra contemplando entre las instruciones alguna combinacion
de estado, simbolo leido, o bien cuando se ejecuta la instruccion parar.
Las acciones son :
i: mover a izquierda
d: mover a derecha
s: parar
cualquier otro simbolo : no moverse
Al correr el programa, se pregunta automaticamente el nombre del archivo
que constituye el "programa" de la maquina. Supongamos que sea MT.TXT
Si se invoca desde DOS al programa ejecutable (despues que lo compilaste
con Quick Basic), y asumiendo que se lo llamo TURING.EXE, entonces se puede
pedir directamente el nombre del archivo segun la sintaxis :
TURING MT.TXT
Si no dispones de Quick Basic o no lo puedes conseguir en internet, (debe
andar por algun lado..), visita www.qbasic.com, alli hay una seccion de
compiladores Basic. Recomiendo el Fbasic, aunque tal vez tengas que cambiar
algunas lineas del codigo.
10. Ojo ! Todavia no termina (parte dos) @
%@%@%@%@%@%@%@%@%@%@%@%@%@%@%@%@%@%@%@%
Incluyo unos ejemplos de MT para que crees el archivo [no creeras que
voy a hacer todo por ti], y luego los pruebes con el simulador.
Todos los ejemplos estan bajo derechos reservados de Ariel Arbiser.
Gato x liebre
"""""""""""""
Esta MT transforma una sucesion de letras "a" (aaaaa..), en una sucesion
de letras "a" y letras "b" alternadas (abab..). Esta escrito segun la
codificacion de "Vida, pasion y muerte de una MT"
0,a,b,D,1
0,b,a,D,1
1,a,a,D,0
1,b,b,D,0
Desde luego, se considera a 0 como el estado inicial de la maquina, en
este y todos los demas casos. Esta MT parara cuando encuentre un simbolo
que no sea ni A ni B, puesto que no hay ninguna instruccion que contemple ese
caso.
Este problema de cambiar las letras que ocupan una posicion impar de la
cinta, demanda 4 instrucciones. Puede haber problemas que demanden un numero
menor o mayor de instrucciones.
Bloque mayoritario
""""""""""""""""""
Otro ejemplo puede ser este. Se desea buscar en la cinta la primera
ocurrencia de un bloque de letras a (aaaa..) y cambiarlo a todo un bloque de
letras b (bbbb..). Para resolverlo se pueden usar las siguientes instrucciones
de MT. Se asume que los unicos simbolos que pueden aparecer en la cinta son
a, b y c.
0,a,b,D,1
0,b,b,D,0
0,c,c,D,0
1,b,b,D,1
1,a,a,-,2
1,c,c,-,2
Esta maquina parara cuando encuentre un simbolo diferente de a,b; o bien
cuando haya convertido al primer bloqe de letras a (aaaa..) en letras b
(bbbb..).
Facil como 1+1 [ cuanto sera 1+1 en windows xp ? :) ]
""""""""""""""
Por ultimo, esta es una MT para incrementar en uno a un numero binario,
esto es, en simbolos que representan a un numero en la cinta escrito en base
2. Los simbolos seran "a" representando al 0 y "b" representando al 1. Se
puede usar cualquier otra representacion similar.
Aclaro que el numero se escribe de izquierda a derecha como lo escribes
normalmente. Finalmente, hay un simbolo especial, "x", que denota el blanco
o delimitador. Hay simbolos "x" a ambos lados del numero, de modo que la
MT sabra cuando empieza y termina el numero.
0,x,x,D,0 1)
0,a,a,D,0 2)
0,b,b,D,0 3)
0,x,x,I,1 4)
1,a,b,-,2 5)
1,b,a,I,1 6)
1,x,a,-,2 7)
La idea del funcionamiento de esta MT es el siguiente:
Primero (1) la maquina saltea todos los "x" que pueda, moviendo la cabeza
hacia la derecha, para encontrar el primer digito (el mas significativo) del
numero.
Luego (2 y 3), la maquina busca el ultimo digito del numero (el menos
significativo), para comenzar alli la operacion de incrementar el numero.
Con la instruccion 4, se coloca en el ultimo digito. Al llegar al estado
1 (5 y 6), la maquina comienza la operacion, de derecha a izquierda.
La instruccion 6 corresponde a la idea intuitiva del acarreo [me llevo 1]
que se va ejecutando hasta tanto este no ocurra mas. Se llega a la
instruccion 7 si se produce un acarreo tal que el numero de digitos del
resultado sera mayor que el numero original (sucede todas las cifras del
numeros son unos), reemplazando de esta manera la "x" izquiera con un 1
adicional.
Al llegar al estado 2, la maquina termina pues no hay ninguna instruccion
que opere en ese estado.
11. Me voy a dormir @
@%@%@%@%@%@%@%@%@
Termino este largo [tal vez aburrido] articulo sobre las maquinas de
Turing. Nos volveremos a ver ...
[parece sacado de una peli de terror :)]
Criticas, sugerencias, opiniones, dinero o lo que quieras enviar :
elotro.ar@gmail.com
*EOF*
