Act 11 automatas unad

Tercera Unidad |Capítulos |Temas | |
|LENGUAJES ESTRUCTURADOS POR FRASES|Máquinas de Turing. |Conceptos generales, Otras definiciones.Funcionamiento de la MT. |
| |Máquina de Turing y Computación. |Tesis de Church/Turing. Máquina de Turing Universal.Funciones |
| ||computables.Decidibilidad. |
| |Funciones recursivas. |Introducción ,Funciones recursivas primitivas.Funciones |
| | |recursivas parciales |

MAQUINA DE TURING[1]
La máquina de Turing es unmodelo computacional introducido por Alan Turing en el trabajo “ On computable numbers, with an application to the Entscheidungsproblem ”, publicado por la Sociedad Matemática de Londres, en el cual se estudiaba la cuestión planteada por David Hilbert sobre si las matemáticas son decidibles, es decir, si hay un método definido que pueda aplicarse a cualquier sentencia matemática y que nos diga siesa sentencia es cierta o no. Turing construyó un modelo formal de computador, la máquina de Turing, y demostró que existían problemas que una máquina no podía resolver. La máquina de Turing es un modelo matemático abstracto que formaliza el concepto de algoritmo .
Una máquina de Turing es un “dispositivo” como lo eran los autómatas finitos o los autómatas a pila, con más capacidades que éstos.Dispone también de un número finito de estados, uno de ellos inicial, y algunos de ellos finales. Dispone también de una cinta, que es una sucesión “doblemente infinita” de “celdas”, en cada una de las cuales hay un símbolo. La cinta está inicialmente “en blanco” salvo en una porción finita, en la que está almacenada la entrada. La máquina de Turing puede leer y escribir símbolos en la cinta, ymoverse a lo largo de ella en ambos sentidos. Para ello dispone de una cabeza de lectura-escritura. Su operación viene determinada por su función de transición.
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 un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a:• avanzar el cabezal lector/escritor para la derecha.
• avanzar el cabezal lector/escritor para la izquierda.
El cómputo es determinado a partir de una tabla de estados de la forma:
(estado, valor) [pic](\nuevo estado, \nuevo valor, dirección)
Esta tabla toma como parámetros el estado actual de la máquina y el carácter leído de la cinta, dando la dirección para mover el cabezal, elnuevo estado de la máquina y el valor a ser escrito en la cinta.
Con este aparato extremadamente sencillo es posible realizar cualquier cómputo que un computador digital sea capaz de realizar.

[pic]

[1] http://www.wikipedia.es/enciclopedia/M%C3%A1quina_de_Turing

Act 11: Reconocimiento Unidad No. 3

|Según Alan Turing, cualquier tipo de problema puede ser resuelto por una Máquina|
|Su respuesta : |
|Falso |
|Es correcto|

Cuál de las siguientes proposiciones es FALSA con respecto a las Máquinas de Turing
Su respuesta :
El desplazamiento de la Máquina en la cinta es siempre hacia la derecha
Correcto, no es cierto ya que se desplaza en ambos sentidos
Principio del formulario
[pic][pic]
Final del formulario

Act 11: Reconocimiento Unidad No. 3

|Una Máquina...