Maquinas de turing

...

Lenguaje recursivamente enumerable: este es un lenguaje formal, acepta y se detiene con cualquier cadena de lenguaje, pero se puede para y rechazar o incluso iterar indefinidamente, con una cadena que ni pertenece al lenguaje.

Lenguajes Libres de contexto: Son gramáticas conocidas también como gramáticas de tipo 2 o gramáticas independientes del contexto, son las que generan los lenguajes libres o independientes del contexto. Los lenguajes libres del contexto son aquellos que pueden ser reconocidos por un autómata de pila determinístico o no determinístico.

---------------------------------------------------------------

Tipos de máquinas de Turing

-

Máquina de Turing Multicinta

En este modelo nos dice que la máquina de Turing se basa en las cintas que tiene un numero k infinitos de ambos sentidos y de igual manera tiene un numero k de cabezales, y nos dice que solo tiene una entrada de información en la primera cinta. Las transiciones se basan en tres pasos los cuales son:

-En el primer paso hace referencia a la Transición de estado de la cinta

-El segundo paso nos dice que hay que escribir un símbolo en cada una de las celdas sobre las que están colocados los cabezales de L/E.

- y como último paso el movimiento de casa cabezal es independiente e izquierdo, derecho o ninguno.

Así es como funciona este tipo de máquina.

-

Máquina de Turing No Determinista

Esta es una máquina que ahora las cintas son limitadas a la izquierda y que son caracterizadas porque se basan en el estado y en un símbolo que puede haber diferentes transiciones. El número de transiciones nos dice que es finito y se basa en el estado o en el símbolo

-

Máquina de Turing Multidimensional

En estas máquinas, el modelo de una cinta ahora es un ARRAY de K dimensiones de celdas, recordemos que la K representa una cantidad, en esta ocasión la K se refiere al tamaño del ARRAY y existen dos direcciones posibles. EL estado y el símbolo va a determinar en qué de las 2k direcciones existentes va a ver una transición y tiene un movimiento unidimensional, ose solo una dirección. Como referencia tenemos que se considera que la entrada esta sobre un eje y que la posición inicial del cabezal está ajustada a la izquierda.

-

Máquina de Turing con Múltiples Cabezales

Como su nombre los dice, esta máquina tiene un numero k de cabezales de E/L, es semejante al de la Multicinta solo que ahora con cabezales. Nos dice que la formada de operar de los cabezales es independientes, y su movimiento es como el de la Multicinta izquierda, derecha o ninguna.

-

Máquina de Turing Offline

Ahora este es un caso particular de las Máquinas Multicinta, tienen una cinta especial de sólo lectura en la que el cabezal, que sólo puede moverse hacia la derecha, no puede moverse de la zona delimitada por una par de símbolos especiales.

-

Máquina de Turing con movimiento "stay" o "esperar"

Nos dice que la función de transición de la Maquina de Turing sencilla está definida por δ :Q x Γ → Q x Γ x {L, R}, una representación modificada puede ser δ: Q x Γ → Q x Γ x {L, R, S} . La variable S significa "permanecer" o "esperar", esto quiere decir que no debe mover el cabezal de lectura o escritura. Y por lo tanto δ(q, σ ) va hacer igual a (p, σ’, S), donde el estado q va a pasar al estado p, se escribe σ’ en la celda actual y la cabeza se queda sobre la celda actual. A continuación podemos ver un ejemplo para entenderlo un poco mejor.[pic 5]

---------------------------------------------------------------

-

Máquina de Turing con cinta infinita a ambos lados

Esta máquina es una modificación de la MT sencilla, y la función de esta es que las cintas por la izquierda y por la derecha son infinitas y esto hace que se puedan realizar transiciones iniciales como δ(q0, x) = (q1, y, L).

[pic 6]

-

Máquina de Turing con cinta multipista

Es aquella que mediante cada celda de la cinta de una máquina sencilla se divide en subceldas. Cada subcelda es capaz de contener símbolos de la cinta. La cinta tiene cada celda subdividida en tres subceldas. Esto nos quiere decir 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 está 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.

---------------------------------------------------------------

-

Máquinas de Turing multidimensionales

Este tipo de máquinas una MT multidimensional es aquella cuya cinta puede verse como extendiéndose infinitamente en más de una dirección, uno de los ejemplos puede ser el de una máquina bidimensional cuya cinta se extendería infinitamente hacia arriba, abajo, derecha e izquierda. Veamos el ejemplo en la imagen

[pic 7]

En esta modificación de la MT también se agrega dos nuevos movimientos del cabezal {U,D} esto quiere decir arriba y abajo. De esta forma la definición de los movimientos que realiza el cabezal será {L,R,U,D}.

---------------------------------------------------------------

-

Máquina de Turing Cuántica

Nos dice que Deutsch presentó el diseño de la primera Máquina Cuántica basada