Ensayos

Solo disponible en BuenasTareas
  • Páginas : 5 (1213 palabras )
  • Descarga(s) : 0
  • Publicado : 24 de enero de 2011
Leer documento completo
Vista previa del texto
INSTITUTO TECNOLOGICO DE LA PAZ
Nombre del maestro:

Isaac Villa Medina
Nombre del Alumno:

Misael Cosío Domínguez.
Nombre de la Materia:

Teoría de la Computación
Contenido:

Investigación Sobre Maquinas de Turing (MT)

La Paz Baja California Sur, Martes 30 noviembre del 2010

¿Qué es una máquina de Turing (MT)

U

na máquina de Turing (MT) es un modelo computacionaldesarrollado por Alan Turing.

el cual lo estaba implementando para una investigación en el cual se involucraban las matemáticas. La cuestión era “si las matemáticas eran decidibles”; en otras palabras, si existe algún método definido que pueda aplicarse a cualquier sentencia matemática y que nos diga si esa sentencia es válida o errónea. Lo único que se pudo demostrar fue que existían problemas quelas máquinas de Turing no podían resolver. Por eso, se dice que una máquina de Turing es un modelo matemático abstracto que formaliza el concepto de algoritmo. Se Describe una máquina de Turing (MT) como un modelo matemático que consiste en un autómata eficiente con la capacidad de resolver cualquier tipo de problema matemático Expresado en forma de algoritmo. Tesis de Church: Algoritmo= Maquina deTuring. También, una máquina de Turing puede ser vista como una especie de máquina de estados (autómata). En cualquier momento la MT esta en cualquiera de un numero finito de estados, la cual ejecutara cierta instrucción en cierto estado.

Definición Formal de Una MT
Una Maquina de Turing (MT) es una tupla formada por varios objetos (Q, Σ, Γ, δ, q0, B, F) Q: Un Conjunto Finito de Estados. Σ: Sele define como alfabeto de Entrada (conjunto finito de símbolos o caracteres a procesar). Γ: Es el alfabeto de la cinta, que contiene todos los símbolos que la maquina puede leer o escribir en la cinta. Tal que, Σ € Γ (el alfabeto de entrada es un subconjunto del alfabeto de la cinta). δ: Q×Γ € Q×Γ×{I,N,D} : se le conoce como función de transición. q0 € Q: Estado Inicial. F € Q: Estados finales oestados de Aceptación. B: símbolo del Espacio en blanco

Funcionamiento MT
La cinta de la MT es infinita hacia la derecha (o del estado inicial hacia adelante).  Utilizan el Símbolo Supuesto: Si δ(q, ) , está definido por δ(q, )=(qn , , X) donde X € {D, N} } para representar la posición 0 de la cinta.

Si a € Γ \ {

} y δ(q, a) está definido: δ(qn , a) = (q’, b, X) donde b € Γ \ {

Σes el alfabeto de entrada y Γ el alfabeto de la cinta.   Una palabra W € Σ* de entrada de largo n es colocada en las posiciones 1,...., n de la cinta. Las posiciones siguientes (n + 1 , n+ 2 …….) contienen el símbolo B.

Al comenzar a funcionar la MT, la maquina se encuentra en el Estado q0 y su cabeza lectora se encuentra en la posición 1 de la cinta.

En cada instante la maquina seencuentra en un estado q y su cabeza lectora se encuentra en una posición p.  La máquina escribe el símbolo B en la posición p de la cinta.  Cambia de estado q a qn.  Mueve la cabeza lectora a la posición p -1 si X = I y a la posición p + 1 si X= D. si X= N, entonces la cabeza lectora permanece en la posición p.

Descripción de su funcionamiento
Una Maquina de Turing (MT) puede considerarse como undispositivo capaz de adoptar un estado entre varios posibles y que dispone de un cabezal que puede leer y escribir símbolos en una cinta. En cada momento, en función del estado en que se encuentra y del símbolo que lea de la cinta, realiza las 3 acciones básicas:

1. Escribe un nuevo símbolo en la cinta 2. Desplaza el cabezal en una única posición a lo largo de la cinta, siempre y cuando notopes con 0 podrás recorrer hacia la izquierda; derecha cuando sea mayor 0, o dejarlo en la misma posición. 3. Cambias de estado actual a estado siguiente.

NOTA: Cuando la MT no tiene definida ninguna acción para alguna configuración o estado en que se encuentra este se detiene.

Tipos de Maquinas de Turing.
Máquinas de Turing Deterministas y no Deterministas.

 Maquina de Turing...
tracking img