social

UNIVERSIDAD AUTÓNOMA DE NUEVO LEÓN

MAESTRÍA EN CIENCIAS DE LA ADMINISTRACIÓN
CON ESPECIALIDAD EN SISTEMAS

TRABAJO FINAL

MÁQUINAS DE TURING

ELABORADO POR :
EQUIPO 5
BRUNO LÓPEZ TAKEYAS
JAIME DAVID JOHNSTON B.
JAVIER CASTAÑEDA AMBRIZ
MA. GUADALUPE MENDOZA GARCÍA
MIGUEL GUERRERO CRESPO
SERGIO GARZA CARRANZA
FEBRERO DE 1996

1

CONTENIDO

Tema

Página

INTRODUCCIÓN3

REQUERIMIENTOS

6

OBJETIVO

7

DESCRIPCIÓN DEL PROGRAMA

8

LISTADO DEL PROGRAMA

10

CONCLUSIONES

22

BIBLIOGRAFÍA

23

2

INTRODUCCIÓN
La clase de autómatas que conocemos como máquinas de Turing
fué propuesta por Alan M. Turing en 1936. La idea básica de Turing fué
estudiar los procesos algorítmicos utilizando un modelo computacional
El propósito de lasmáquinas de Turing fué desarrollar un sistema
en el cual fuera posible modelar cualquier proceso que pudiera
considerarse como un cálculo.
Propiedades básicas
•
•
•

Tienen un mecanismo de control que en cualquier momento puede
estar en uno de entre un número finito de estados.
Realiza operaciones de movimiento, que consisten en mover el cabezal
de cinta una celda a la derecha ó una celda ala izquierda y pasar a un
nuevo estado.
Realiza operaciones de escritura, que consisten en reemplazar un
símbolo en la cinta con otro símbolo y entonces pasar a un nuevo
estado.
Representación de una máquina de Turing
Cinta

Cabezal de Lectura
y escritura
La cabeza se mueve en las
dos direcciones

Indicador de Estado
t
h

s4

s1

s3
s2

Mecanismo de Control

3Notación
Γ : Simbolos de cinta
S : Conjunto finito de estados
’
S : Conjunto finito de estados no finales
δ : Función de transición δ :(S’ x Γ)
donde LR ∉ Γ
∆ : Espacio en blanco

S x (Γ ∪ { LR})

Definición formal de Máquina de Turing
Una Máquina de Turing es una sextupla de la forma (S, Σ, Γ,δ, ) donde:
Γ,δ,i,h)
S es una colección finita de estados.
Σ es un conjunto finito de símbolosdistintos de espacio en blanco,
llamado alfabeto.
Γ es un conjunto finito de símbolos, incluidos los de Σ , que se conocen
como símbolos de la cinta de la máquina.
δ es la función de transición de la máquina.
i es un elemento de S llamado estado inicial.
h es un elemento de S llamado estado de parada.
Ejemplo de una máquina de Turing

S i,h
Σ {x,y}
Γ {x,y,∆}
δ(i,x)=(h,y)

x/y
i

iestado inicial
h estado de parada

La Tesis de Turing nos dice que el poder computacional de una máquina
de Turing es tan grande como el de cualquier sistema computacional
posible.

4

h

Sistema de codificación de máquinas de Turing

Dada una máquina M por representar, nuestro sistema de
codificación necesita que acomodemos los estados de M en una lista cuyo
primer elementocorresponda al estado inicial y el segundo elemento
corresponda al estado de parada. Con base en el orden de la lista,
podemos hablar del primer estado de M, del segundo estado de M y, en
general, del estado j de M. Establecemos que el estado j de M se
representará con una cadena de ceros de longitud j. Así, el estado inicial
estará representado por 0, el estado de parada por 00 y el siguiente estado(si existe) por 000.
Luego representamos los símbolos L y R como los símbolos en
Σ (los símbolos de cinta de M distintos de espacio en blanco) como
cadenas de ceros. Esto se hace acomodando en una lista los símbolos de
Σ y representando L con 0, R con 00, el primer símbolo de la lista con 000,
el segundo símbolo con 0000 y, en general, el símbolo j con una cadena de
ceros de longitud j+2.Si ahora establecemos que el símbolo del espacio en blanco se
representará por la cadena vacía, obtenemos un sistema en el cual
podemos representar los símbolos L y R, los estados de M y los símbolos
de la cinta de M por medio de cadenas de ceros. A su vez esto nos permite
representar cualquier transición de M como una cadena de ceros y unos.
A fin de cuentas se puede representar...