Que es maquina de Turing

Trabajo en word + Preguntas importantes

Descargar archivo desde aqui

1.     ¿Qué es Maquina de Turing?

Dispositivo que manipula símbolos sobre una tira de cinta de acuerdo a una tabla de reglas.

2.     ¿Quién dio a conocer las maquina de Turing y cuando sucedió?

Fue descrita por Alan Turing como una “máquina automática” en su ensayo de 1948.

3.     ¿En que consiste la Maquina de Turing?

Una ilimitada capacidad de memoria obtenida en la forma de una cinta infinita marcada con cuadrados, en cada uno de los cuales podría imprimirse un símbolo.

4.     La Maquina de Turing maneja un símbolo llamado ‘blanco’, ¿Cuáles son las posibles formas de representarlo en la tupla?

Un símbolo especial llamado blanco representado normalmente por b,  o 0.

5.     Describa la tupla de la la Maquina de Turing:

6.     ¿Cómo puede considerarse la maquina de Turing?

Un autómata capaz de reconocer lenguajes formales, es decir también, lenguajes recursivamente enumerables, de acuerdo a la jerarquía de Chomsky.

7.     ¿Qué le define la dirección del movimiento y el símbolo a escribir a la Maquina de Turing

La función de transición.

8.     ¿Cómo se representa la Maquina de Turing?

Mediante grafos particulares, también llamados diagramas de estados finitos.

9.     ¿Qué símbolos lee y escribe la Maquina de Turing?

Un bit 0 ó 1.

10.  ¿Cómo arranca la Maquina de Turing?

La máquina se inicializa en algún estado interno arbitrario.