Construye tu propia Máquina de Turing

10 Flares Twitter 0 Facebook 10 Google+ 0 Pin It Share 0 Email -- 10 Flares ×

¿Alguna vez soñaste con construir tu propia Máquina de Turing? Mike Davey también. Pero Mike, en lugar de limitarse a soñar con ello, pasó a la acción y la construyó. El resultado es un dispositivo que auna funcionalidad y belleza, a la vez convierte en un dispositivo real la Máquina teórica imaginada por Alan Turing en 1936. El constructor ha puesto disposición del publicó los planos de la máquina, haciendo posible que finalmente construyas la tuya ¿Te animas?

La Máquina de Turing es un modelo computacional introducido por Alan Turing en 1936. En su trabajo “On computable numbers, with an application to the Entscheidungsproblem”, publicado por la Sociedad Matemática de Londres, Turing abordaba la cuestión planteada por David Hilbert sobre si las matemáticas son “decidibles”, es decir, si hay un método definido que pueda aplicarse a cualquier sentencia matemática y que nos diga si esa sentencia es cierta o no. Para demostrar que  existían problemas que una máquina no podía resolver, Turing elaboró un modelo formal de ordenador -no contaba con los medios técnicos para construir un aparato real en esa época- al que se llamó Máquina de Turing.

Construye tu propia Máquina de Turing

La máquina imaginada por Turing era sumamente simple. Realizaba su trabajo utilizando como hardware un cabezal de lectoescritura y como soporte para el programa y los datos una cinta de papel infinitamente larga. El cabezal era capaz de leer el contenido de una posición de la cinta, borrarlo o escribir un nuevo valor. Concretamente, las operaciones que puede realizar una Máquina de Turing se limitan a avanzar el cabezal lector/escritor hacia la derecha o avanzar el cabezal lector/escritor hacia la izquierda. Una vez que está en la nueva posición, realiza el cómputo, que está determinado por una tabla de estados de la forma (estado, valor) → (nuevo estado, nuevo valor, dirección). Los parámetros de la tabla son el estado actual de la máquina y el caracter leído de la cinta, o que produce un nuevo estado de la máquina, proporciona la dirección a la que mover el cabezal y el nuevo valor a ser escrito en la cinta. A pesar de su sencillez extrema, esta máquina es capaz de realizar cualquier cómputo que un ordenador digital sea capaz de realizar, aunque obviamente, a una velocidad mucho menor. Por supuesto, en 1936 la Máquina de Turing era sólo un modelo matemático abstracto que formalizaba el concepto de algoritmo.

Construye tu propia Máquina de Turing

Mike Davey no ha hecho otra cosa que llevar a la práctica el concepto de Alan Turing. Obviamente, no es el primero en construir una máquina de este tipo, pero su creación se destaca sobre las demás por lo bien diseñada que está, y por poner al alcance de todos los interesados los planos, circuitos y programas necesarios para que quien lo desee pueda construirse su propia Maquina de Turing. El corazón del sistema es, cómo no, el cabezal de lectoescritura.  Davey utiliza un marcador convencional impulsado por servomecanismos y controlado por un microcontrolador Propeller, de  Parallax, para escribir ceros y unos sobre la cinta. Una pequeña cámara se encarga de “ver” el contenido de las “celdas” que contiene la cinta, y un rodillo motorizado se encarga de borrar aquellos datos que haga falta eliminar. La cinta utilizada es un largo carrete de película en blanco, que es arrastrado por dentro del cabezal mediante un sistema tractor impulsado por un motor paso a paso controlado también por el Propeller. Hay que aclarar que el microcontrolador no “sabe” cual es el contenido de la cinta: solamente cuenta con los datos que “ve” con la cámara, respetando a rajatabla la idea de Turing.

El estado inicial de la Máquina está dado por el contenido inicial de la cinta y la posición del cabezal. Esos datos se ingresan a la máquina mediante una tarjeta de memoria flash tipo “SD”, y el sistema se encarga de volcar los ceros y unos sobre la cinta. Cuando todo está listo, la Máquina comienza a trabajar.  Davey ha dotado a su aparato de una serie de visualizadores de 7 segmentos que permiten que el operador pueda ver en todo momento que es lo que está haciendo la máquina. También posee una pantalla LCD de 4 renglones en la que puede verse el estado actual, los próximos estados o el sistema de menues destinado a la carga o grabación de estados desde o en la tarjeta de memoria. Como dijimos al principio, ahora tienes todo lo necesario para construir una de estas máquinas en casa ¿Te animas a hacerlo?


  • anony

    maravillosa maquina!. hahahha me encantan las maquinas =D magnifica entrada

  • xXxOlivierxXx

    Me parece genial el invento… Pero la verdad, no le encuentro una funcion util xD

  • reje80

    No puedo entender para que fue diseñada

    • ecoronel

      reje80, cuando Alan diseñó el modelo teórico de su máquina lo hizo porque necesitaba demostrar que era imposible hacer un algoritmo que dado otro decidiera si el algoritmo paraba o no. Para particularidad que tiene la máquina de Turing es que se pueden tener dos algoritmos en el Modelo de RAM y parecer distintos pero cuando se traducen a la máquina de Turing se puede ver que el problema raíz es el mismo, es suele suceder con los problemas NP completos.

  • Falke

    Es la misma maquina que todos llamados "computadora" pero en su forma mas sencilla. Podemos ver como escribe, borra ceros y unos, no es eso lo que hace una PC actual?.

  • Kniffe

    Borra y escribe aleatoriamente 1 y 0 dependiendo de lo que ve?. no entiendo realmente cual es su utilidad, sumar, restar, o simplemente escribir?.

    • Kniffe

      ¡Me retracto!, no habia visto el video completo :P.., si esto fue pensado hace mas de 70 años atras impresionante.

  • Miky

    excelente articulo, es inspirador ver a la primera computadora y su simplicidad.

  • Lechuck

    Tecnicamente no es posible hacer una máquina de turing, ya que esta tiene una cinta infinita, lo que significa en español memoria infinita, y en el mundo no existe una cinta de papel de largo infinito. Más bien lo que construyó es un autómata finito, ya que el vocabulario es acotado(por definición de vocabulario) y con memoria finita, tiene estados acotados, pueden ser mucho, pero son finitos. Finalmente Alan Turing diseñó una máquina teórica, para demostrar que no todos los algoritmos son decidibles( halting problem). Es más, si se pudiera implementar esa máquina en realidad, sería mucho más poderosa que la computadora más moderna. Me explico, resolver un calculo es equivalente a identificar si una cadena pertenece a un lenguaje dado, las computadoras nuestras tienen una cantidad de señales finitas (estado del usb, bits en el disco, bits en ram, etc) Es decir, solo sería capáz de reconocer lenguajes regulares(es un autómata finito).
    Salu2

  • Anonimo

    Iba a explicar pero es como tratar de enseñarle a leer a un perro.

  • Anonimo

    Esta no es una maquina de Turing, sólo es un robot que escribe 0 y 1.

  • Anonimo

    Uuuuuy mm… no entiendo!!!!
    Uuuuiiii ¿Pa que sirve esta lesera?
    MMMM… cuetiones antiguas que no le sirven a nadie uuuuy
    Pa que hacen estas cossaaas mm
    Que utilidad tiene esta cosa? pff…. ninguna
    Es un PC!!!! Eureca soy un genio…
    Escribe 0s y 1s pero no entiendoooo…. Seguro son leseras.
    Bueno para todos los que ven esto y no lo entienden seguro tiene con suerte un CI de entre 70 y 90, es decir superan con suerte a los imbéciles.
    Para los que creen que es interesante pero no saben de que va el rollo ni para que sirve tal vez lleguen a ci 100.
    De ahí para arriba muchos no escriben acá pero usan su PC todos los días en sus trabajos sin saber siquiera que en alguna medida sus celulares, Palms, microondas, autos, equipos modulares, aviones, etc. etc. ocupan de alguna forma una maquina similar a esta (en el concepto po hueones, no va a haber un avión haciendo cálculos con este modelito) realizando millones de cálculos pa que el avión no se caiga o en un microondas pal programa que usas para calentarte la sopa, o en el auto cuando frenas ABS o doblas.
    Y claro, no nos podían faltar las cuentas del banco, tienes tu clave y el cajero automático te da el dinero pero seguro los que no captan nada de la maquina creen que hay un enano dentro del cajero contando los billetes para dárselos por la rendija. O llevan un enano dentro del capo del auto afirmando las ruedas… Bueno me dio risa, esta es una parodia ya que me dio paja explicar la Maquina de parada, a muchos debería explicárselo con peras y manzanas y de mas esta decir que no se acordarían de lo que les dije al principio con el fin de complementarlo con el resto de la explicación unos 20 min. después. Es decir son usuarios, y como dice el término sólo usan, no comprenden nada y en realidad no les hace falta, ya que si comprendieran, en esta sociedad habría más justicia, más respeto, más equidad.
    Eso sería, chao no mas.

  • Bill Gates

    No se para que inventan estas tonteras los inventores.
    Mejor me voy a pasear en mi yate.

  • Ano

    La carcuradora liiiinda, pero ¿cómo me lacho ar borsillo?