Maquinas De Turing

MAQUINAS DE TURING Y
MAQUINAS DE REGISTROS
ILIMITADA
Argenis Aldair Aroche Villarruel
Gustavo Mariscal Rangel
Carlos F. Huerta Agustin

MAQUINA DE TURING
Fueron propuestas por primera vezpor Alan
Turing, en un intento para dar una definición
matemática precisa de algoritmo o
procedimiento mecánico.

Una Máquina de Turing es una séptupla M =
{Г,∑,●,Q,q0,f,F}, donde:
- Г es elalfabeto de símbolos de cinta.
- ∑ es el alfabeto de símbolos de entrada.
- ● es el símbolo blanco que no pertenece a ∑.
- Q es un conjunto finito de estados.
- q0 es el estado inicial.
- F es elconjunto de estados finales.
- f es una función de transición parcial.

Por lo anterior una Máquina de Turing es un dispositivo
capaz de adoptar un estado
determinado (de Q ) y está conectado auna
cabeza lectura/escritura que puede leer y
escribir símbolos en una cinta infinita.

En cada movimiento:
1.
La máquina lee el símbolo de la cinta en la posición
donde se encuentra la cabezade lectura/escritura.
2.
En función del símbolo leído y del edo. Actual:
a.
Pasa a un nuevo estado.
b.
Imprime símbolo en la cinta en la posición donde leyó
el símbolo actual.
c.
Mueve lacabeza de lectura/escritura una posición a
la izquierda (L) o a la derecha (R).

Inicialmente la cinta contiene un número finito
de símbolos de ∑, precedidos y seguidos por un
número infinito deblancos. La cinta se comporta
como un dispositivo de entrada y salida.

EJEMPLO:
Realizar MT que cumpla: {wwr / w ϵ (0+1)*}

URM




El modelo URM(máquina de registros ilimitada)
deShepherdson y Sturgis
Como su “conjunto de instrucciones” esta mas
cercano a los lenguajes de alto nivel que el de la
TM la URM es mas fácil de programar. Así
algunos autores que prefieren incluir lateoría de
la recursividad a través de algún formalismomáquina han favorecido a la URM antes que la
TM.

URM








Todas las entradas, salidas y valores internos de
cualquier...