Máquinas de Turing

By :Rosviannis Barreiro 14-1138Listiany Agramonte 15-0737

¿Qué es una Máquina de Turing?

• La máquina de Turing puede considerarse como un autómata capaz de reconocer lenguajes formales. En ese sentido, es capaz de reconocer los lenguajes recursivamente enumerables, de acuerdo a la jerarquía de Chomsky. Su potencia es, por tanto, superior a otros tipos de autómatas, como el autómata finito, o el autómata con pila, o igual a otros modelos con la misma potencia computacional.

Tipos de Máquinas de Turing

• Máquina de Turing con cinta infinita a ambos lados

Esta modificación se denota al igual que una MT sencilla, lo que la hace diferente es que la cinta es infinita tanto por la derecha como por la izquierda, lo cual permite realizar transiciones iniciales como δ(q0, x) = (q1, y, L).

Tipos de Máquinas de Turing

• Máquina de Turing con cinta multipistaEs aquella que mediante la cual cada celda de la cinta de una máquina sencilla se divide en subceldas. Cada celda es así capaz de contener varios símbolos de la cinta. Por ejemplo, la cinta de la figura tiene cada celda subdividida en tres subceldas.

Se dice que esta cinta tiene múltiples pistas puesto que cada celda de esta máquina de Turing contiene múltiples caracteres, el contenido de las celdas de la cinta puede ser representado mediante n-tuplas ordenadas. Los movimientos que realice esta máquina dependerán de su estado actual y de la n-tupla que represente el contenido de la celda actual. Cabe mencionar que posee un solo cabezal al igual que una MT sencilla.

Tipos de Máquinas de Turing

• Máquina de Turing multicintaUna MT con más de una cinta consiste de un control finito con k cabezales lectores/escritores y k cintas. Cada cinta es infinita en ambos sentidos.

La MT define su movimiento dependiendo del símbolo que está leyendo cada uno de sus cabezales, da reglas de sustitución para cada uno de los símbolos y dirección de movimiento para cada uno de los cabezales. Inicialmente la MT empieza con la entrada en la primera cinta y el resto de las cintas en blanco.

Tipos de Máquinas de Turing

• Máquina de Turing multidimensional

Una MT multidimensional es aquella cuya cinta puede verse como extendiéndose infinitamente en más de una dirección, el ejemplo más básico sería el de una máquina bidimensional cuya cinta se extendería infinitamente hacia arriba, abajo, derecha e izquierda.

En la modificación bidimensional de MT que se muestra en la figura también se agregan dos nuevos movimientos del cabezal {U,D} (es decir arriba y abajo). De esta forma la definición de los movimientos que realiza el cabezal será {L,R,U,D}.

Aplicaciones de las Máquinas de Turing

• Teoría de la computación: La teoría de la computación es una rama de la matemática y la computación que centra su interés en las limitaciones y capacidades fundamentales de las computadoras. Específicamente esta teoría busca modelos matemáticos que formalizan el concepto de hacer un cómputo (cuenta o cálculo) y la clasificación de problemas de acuerdo a su grado de dificultad.

Máquinas Oráculo (O-Machines)

La máquina con oráculo, es una máquina de Turing equipada con un oráculo que es capaz de contestar preguntas sobre la pertenencia a un conjunto específico de números naturales.

Funcionamiento: La máquina también tiene tres estados especiales: el "estado llamada", el "estado-1" y el "estado-0" y un símbolo marcador especial: μ (mú). Para usar su oráculo, la máquina debe escribir primero el símbolo μ en dos recuadros de la cinta, y entonces se entrará en el "estado llamada". En este estado se manda una petición al oráculo y la máquina termina en el "estado-1" si el número escrito en los cuadrados de la cinta entre los símbolos "μ" son un elemento del conjunto oráculo y termina en el "estado-0" en otro caso.

Diseño del Turing doodle

Enlaces de Interes• Google-Doodle. URL: http://

www.google.com/doodles/alan-turings-100th-birthday

• Repositorio multimedia. URL: https://commons.wikimedia.org/wiki/Turing_Machine

• Máquina de Turing construida sobre hardware. URL: http://aturingmachine.com/

• Video de Máquina de Turing mecánica.• URL: https://www.youtube.com/watch?v=aBToqFJLrl4• Video Maquina de Turing de LEGO.• URL:

https://www.youtube.com/watch?v=FTSAiF9AHN4