-[ 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*