Capítulo 5 – MÁquinas de turing



Descargar 2,22 Mb.
Página6/31
Fecha de conversión08.06.2017
Tamaño2,22 Mb.
1   2   3   4   5   6   7   8   9   ...   31
6.-Máquinas de Turing Modificadas

En los programas de Post-Turing y en las máquinas de Turing ya sean de cuadruplas o quintuplas, hemos supuesto que la memoria estaba constituida por una única cinta ilimitada en ambas direcciones. Sin embargo se podrían suponer otros dispositivos de memoria. Por ejemplo, en la formulación original de Turing se consideraba que la cinta era infinita en una única dirección, estando acotada por la derecha:
























……….

Esto limita la memoria, pero también se puede pensar en ampliarla, por ejemplo, usando varias cintas que pueden ser ilimitadas en ambas direcciones o solo en una. Pero, de acuerdo con la tesis de Church-Turing todas estas formulaciones deben de ser equivalentes. En esta sección intentaremos demostrarlo.

Vamos a comenzar considerando las máquinas de Turing con cinta ilimitada en una sola dirección. Para concretar vamos a suponer que cuando la máquina esté posicionada en la casilla mas a la izquierda y haya que moverse a la izquierda, entonces la máquina para. Se podían haber hecho otras suposiciones en estas condiciones, pero llegaríamos a modelo equivalentes.

Es evidente que todo lo que se pueda hacer en estas máquinas se puede hacer en una máquina de Turing de las que hemos visto en este capitulo de cinta ilimitada en ambas direcciones. El problema es de si este tipo de cintas limita la capacidad de cálculo. La realiadad es que no es asi. De hecho, Turing dio su modelo original con este tipo de cintas.



Vamos a indicar la idea de la demostración. Esta se basa en representar el contenido de una cinta infinita bidireccional mediante una cinta unidireccional con dos pistas, dos filas de símbolos. A su vez, se puede considerar que esta cinta tiene solo una pista, en la que en cada casilla hay una pareja de símbolos. Es decir los símbolos que se escriben en la cinta unidireccional van a ser parejas de símbolos de la bidiroccional. Por ejemplo, si tenemos la cinta,


. . . .

B

c

a

B

a

a

b

B

B

………

entonces eligiendo una casilla cualquiera de corte (por ejemplo la cuarta de la figura), esta cinta se puede representar como


a

a

b

B

B

....

B

a

c

B




....

Y esta se puede considerar como una cinta normal en la que se encuentran los símbolos (a, B) , (a ,a), (b,c),.... De forma más precisa, sea M una máquina de Turing con alfabeto {s1,…, s2 }y estados q1 , . . . ,qk . Supongamos que M calcula la función unaria g en A0*, donde A0 A. Cuando en esta máquina estamos calculando g(x) la configuración inicial de la cinta bidireccional será

B x


q1



A continuación construiremos una máquina de Turing que calcule g con una cinta unidireccional. El alfabeto de será
1   2   3   4   5   6   7   8   9   ...   31


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

    Página principal