Capítulo 5 – MÁquinas de turing



Descargar 2,22 Mb.
Página31/31
Fecha de conversión08.06.2017
Tamaño2,22 Mb.
1   ...   23   24   25   26   27   28   29   30   31
LA MAQUINA UNIVERSAL DE TURING
Es posible concebir una M T capaz de ejecutar cualquier algoritmo; es decir capaz de realizar los cálculos que realizaría cualquier otra MT, o sea, capaz de simular (tener el mismo comportamiento) cualquier MT particular.
Esta máquina Universal no debe ser diseñada para realizar un cálculo específico, sino para procesar cualquier información (realizar cualquier cálculo específico -MT particular- sobre cualquier configuración inicial de entrada correcta para esa MT particular). La MUT ha de tomar como información de entrada la MT particular más la C.I. . El algoritmo universal ha de ser un intérprete de esa información de entrada. La cinta de entrada ha de tener una C.I. tal como: ... bb quíntupla b quíntupla b... C I (MT) b b ...

El trabajo de interpretación del esquema universal ha de consistir en:

1º) sk = s0 (Inicialización: Suponer que la MT particular empieza estando en s0).

2º) Acceder al carácter de la Configuración apuntado por la Cabeza L/E de la MT (ai).

3º) Encontrar en la cinta una quíntupla que empiece por ai sk (ai sk aj m s1).

4º) Reemplazar ai por aj en la casilla donde se accedió a ai.

5º) Realizar el desplazamiento m desde la casilla donde estaba ai. O sea, marcar la nueva casilla a la que apunta la cabeza L/E de la MT particular.

6º) sk = s1 (actualizar el estado de la MT particular).

7º) Volver a 2).


Observaciones sobre el esquema universal:

- La M U T parará cuando el cálculo esté terminado, o sea, cuando la quíntupla a aplicar sea del tipo ai sk ai sk N sk. Así pues, en el ciclo que es el algoritmo universal, hay que incluir dentro de la fase 3ª una exploración de la quíntupla, una vez encontrada, para decidir si hay que parar o continuar.

-Es complicado explicitar detalladamente las instrucciones que componen cada fase del Algoritmo Universal, debido al carácter unidimensional de la cinta y a la exploración casilla a casilla.



- Es obligada una codificación de la información. El nº de alfabetos y de caracteres distintos de todas las posibles M T particulares que puedan pensarse es arbitrariamente grande y, sin embargo, la M U T sólo puede disponer de un alfabeto finito determinado. Esto obliga a definir procedimientos para codificar la información de cualquier alfabeto finito al alfabeto que definamos para la M U T. Por el mismo motivo ha de haber una normalización en la notación de los estados (el estado inicial de cualquier M T debe ser designado con el mismo símbolo, y así para los sucesivos).

Una metodología para la aplicación de este concepto de normalización de la información es la numeración de Gödel, que se ve en Funciones Recursivas.

Otra, más práctica, es la siguiente:
Codificación de MT’S:

La codificación debe permitir a la MUT un reconocimiento preciso de cada componente sintáctico registrado en la cinta.

Para las letras del alfabeto:

c (b) = b (código del carácter blanco)



c (ai) = 1i+1; ai (indeterminadamente grande); i 0,1,2,…

Para los estados:

c (h) = 1; h = estado de parada.

c( si) = 1i+1; Si Q S (indeterminadamente grande).

Para los desplazamientos del cursor, m N, I, D:

c (N) = 1; c ( I) = 1 1; c (D) = 1 1 1.

El código de una quíntupla ‘p a q d m’ está representado por una palabra 0, 1*, definida así: c(p) b c(a) b c (q) b c(d) b c(m) b.

Una MT que tiene n quíntuplas (el orden no importa): u1, u2, ……, un tiene un código:

c(qj) b c(u1) b c(u2) b ………….. b c(un) b, siendo qj: estado inicial de T.



Codificación de palabras

Sean las letras del alfabeto Zi A y Z una palabra Z = Z1 Z2………Zn

Z tiene un código c(Z) = b b c ( Z1) b c (Z2) b……… b c (Zn) b
Sobre el trabajo de la MUT (continuación)

La entrada a la MUT está dada por una MT y una palabra Z. La entrada codificada es: c(T) c(Z).

Obsérvese que entre el final del código de la última quíntupla y el comienzo del código de Z hay tres blancos.

Es fácil construir la MT que transforma T en c(T) y Z * en c(Z).

Para simular el trabajo de T con una entrada Z, la entrada a la MUT es c(T) c(Z). El trabajo ha de ser:

a) Cuando la función parcial que calcula T está definida para Z, T se detiene y da s como resultado. En este caso la MUT debe parar y dar c(s) como resultado.

z T s

c(T) c(Z) MUT c(T) c(s)

b) Cuando la función que calcula T no está definida para Z, T no se detiene y la MUT tampoco debe parar. En este caso la MUT se mete en un ciclo infinito.


Tesis de Turing

<>.

Esta tesis se apoya en la mismas observaciones que la definición de algoritmo y en el hecho de que la M U T simula cualquier M T particular.



Otros esquemas de máquinas de Turing modificadas:

Máquina de Turing con Cinta Infinita en Ambos Sentidos.


Máquina de Turing Multicinta


Máquina de Turing con múltiples cabezales



Apuntes ampliados por: José María de Córdoba Zea 2ºA Ingeniería Informática


CAPITULO 5- Máquinas de Turing
1   ...   23   24   25   26   27   28   29   30   31


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal