Hijos de Eva

16/3/2005

Máquina de Turing

Filed under: — Quintanar @ 10:49 pm

La máquina de Turing es un modelo computacional creado por Alan Turing con el cual él afirmaba que se podía realizar cualquier cómputo.

La máquina de Turing, como modelo matemático, consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a:

* avanzar el cabezal lector/escritor para la derecha;
* avanzar el cabezal lector/escritor para la izquierda.

El cómputo es determinado a partir de una tabla de estados de la forma:

(estado,valor) (nuevo estado, nuevo valor, dirección)

Esta tabla toma como parámetros el estado actual de la máquina y el caracter leído de la cinta, dando la dirección para mover el cabezal, el nuevo estado de la máquina y el valor a ser escrito en la cinta. Con este aparato extremadamente sencillo es posible realizar cualquier cómputo que un computador digital sea capaz de realizar.

Mediante este modelo teórico y el análisis de complejidad de algoritmos, fue posible la categorización de problemas computacionales de acuerdo a su comportamiento, apareciendo así, el conjunto de problemas denominados P y NP, cuyas soluciones en tiempo polinómico son encontradas según el determinismo y no determinismo respectivamente de la máquina de Turing.

De hecho, se puede probar matemáticamente que para cualquier programa de computadora es posible crear una máquina de Turing equivalente. Esta prueba resulta de la Tesis de Church-Turing, formulada por Alan Turing y Alonzo Church, de forma independiente a mediados del siglo XX.

[De Wikipedia, la enciplopedia libre]

Tenemos 3 comentarios para “Máquina de Turing”

  1. ian llanos:

    Es cierto, la maquina de estados finitos de turin es la caña, yo la he estudiado para Teroia de la Computabilidad y puedo decir que su simplicidad solo es comparable a su determinación, algo tan simple puede resolver todo lo resoluble, aun solo sea capaz de resolver Primitivas. un articulo muy interesante y mas interesante aun es el tema de los algoritmos que no tienen solución, como el problema de la parada, es totalmente «imposible» (hasta que se demuestre lo contrario, ánimo compañeros) probar que un algoritmo no acaba nunca, a lo mas que se llega es a decir que el algoritmo no da una solución final en n pasos (sea n un numero finito). Pues eso, que me ha recordado las horas de TCO.

    Saludos cordiales.

  2. Quintanar:

    Aquí en Granada la asignatura se llama «Modelos de Computación», I y II (trimestral).

    Sobre el problema de la parada, no me dejó muy convencido la explicación (nos la dijeron por encima). Técnicamente no puede existir un programa que evalúe un programa y nos diga si termina, porque si se aplicara sobre sí mismo no acabaría nunca. Uhm… no, no lo veo claro.

  3. Quintanar:

    Ains, lo que es hablar sin tener ni idea. Meses después de mi anterior comentario, me retracto públicamente de semejantes afirmaciones («no me dejó muy convencido la explicación», Quintanar dixit).

    Tras Modelos de la Computación II, con un tema dedicado exclusivamente a las Máquinas de Turing, ahora sí puedo mostrarme partidario de la manifiesta irresolubilidad del problema de la parada.

Powered by WordPress