algoritmo

http://www.dcc.uchile.cl/~gnavarro/apunte.pdf

Máquinas de Turing

La computabilidad se puede estudiar usando diversos formalismos, todos ellos equivalentes:

(i) se parecen a los autómatasde distinto tipo que venimos viendo de antes,
(ii) son el modelo canónico para estudiar NP-completitud, que es el ´ultimo capítulo del curso.

Solamente en el formalismo, y cómo utilizarlo yextenderlo para distintos propósitos, y en el siguiente lo utilizaremos para obtener los resultados de computabilidad. Recomendamos al lector el uso de un simulador de MTs (que usa la notación modulardescrita en la Sección 4.3) que permite dibujarlas y hacerlas funcionar. Se llama Java Turing Visual (JTV) y está disponible en http://www.dcc.uchile.cl/jtv.11

4.1 La Máquina de Turing (MT)

LaMáquina de Turing es un mecanismo de computación notoriamente primitivo, y sin embargo (como se verá más adelante) permite llevar a cabo cualquier cómputo que podamos hacer en nuestro PC. Informalmente, unaMT opera con un cabezal dispuesto sobre una cinta que tiene comienzo pero no tiene fin, extendiéndose hacia la derecha tanto como se quiera.

Cada celda de la cinta almacena un carácter, y cuandose examina un carácter de la cinta nunca visto, se supone que ´este contiene un blanco (#). Como los autómatas, la MT está en un estado, de un conjunto finito de posibilidades. En cada paso, la MT leeel carácter que tiene bajo el cabezal y, según ese carácter y el estado en que está, pasa a un nuevo estado y lleva a cabo una acción sobre la cinta: cambiar el carácter que leyó por uno nuevo (en lamisma celda donde tiene el cabezal), o mover el cabezal hacia la izquierda o hacia la derecha.

Como puede escribir la cinta, la MT no tendrá estados finales o no finales, pues puede dejar escritala respuesta (sí o no) al detenerse. Existe simplemente un estado especial, denominado h, al llegar al cual la computación de la MT se detiene. La computación también se interrumpe (sin llegar al...