Modelo de turing

Cuestionario
1.- ¿Quién planteo como un modelo matemático la máquina de Turing y en qué año?
R= fue planteada por Allen M. Turing en 1936.

2.- ¿En que se basa el funcionamiento del modelo deTuring?
R=se basa en una función de transición, que recibe un estado inicial y una cadena de caracteres (la cinta, la cual puede ser infinita) pertenecientes al alfabeto de entrada.

3.- ¿Defina demanera formal la máquina de Turing?
R=La máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe unnuevo valor.

4.- ¿Mencione los pasos para construir una máquina de Turing?
R= 1.-Elimine las características de inicio de los estados iníciales de las maquinas, excepto la de aquel donde iniciara lamaquina compuesta. 2.-Elimine las características de detención de los estados de parada de todas la maquinas e introduzca un nuevo estado de parada que no se encuentre en ninguno de los diagramas quese combinan. 3.-Para cada uno de los antiguos estados de parada p y cada x en y.

5.- ¿Qué lenguajes acepta la máquina de Turing?
R= Los lenguajes formales que son aceptados por una máquina deTuring son exactamente aquellos que pueden ser generados por una gramática formal. El cálculo Lambda es una forma de definir funciones.

6.- ¿Qué tipo alfabeto utiliza la máquina de Turing?
R= alfabetode entrada y uno de salida, un símbolo especial llamado blanco (Normalmente b, Δ o 0).

7.- ¿Cómo funciona una máquina de Turing Multipista?
R= Es aquella mediante la cual cada celda de la cinta sedivide en subceldas. Cada subcelda es capaz de contener símbolos de la cinta. La cinta tiene cada celda subdividida en tres subceldas. Se dice que esta cinta tiene múltiples pistas.

8.- ¿Se leconsidera un autómata a la máquina de Turing? ¿Por qué?
R= si, por que es capaz de reconocer lenguajes formales.

9.- ¿Cuáles son los tipos de máquinas de Turing?
R= con movimiento stay o...