Teoria de la computación
Páginas: 11 (2734 palabras)
Publicado: 28 de noviembre de 2009
MAQUINAS DE TURING
4.1 DEFINICION FORMAL DE UNA MAQUINA DE TURING
La clase de autómatas que ahora se conocen como maquinas de Turing fue propuesta por Alan M. Turing en 1936, la idea básica de Turing fue estudiar los procesos algorítmicos utilizando un modelo computacional.
Las maquinas de Turing se asemejan a los autómatas finitos en que constan de un mecanismo de control y un flujo deentrada (cinta); la diferencia es que las maquinas de Turing pueden mover sus cabezas de lectura hacia delante y hacia atrás y pueden leer o escribir en la cinta.
PROPIEDADES BASICAS DE LAS MAQUINAS DE TURING
Esta maquina contiene un mecanismo de control que en cualquier momento puede encontrarse en uno de entre un numero finito de estados. Uno de estos estados es un estado inicial en elcual se comienzan los cálculos y otro es el estado de parada cuando se llega a estado se terminan los cálculos, este difieres de los estados de aceptación de los autómatas finitos y de pila en que pueden continuar sus cálculos después de llegar aun estado de aceptación, una maquina de Turing debe detenerse en el momento que llega al estado de parada (por lo anterior la maquina debe tener por lomenos dos estados).
La diferencia mas importante es que una maquina de Turing esta equipada con una cabeza que puede leer y escribir símbolos en la cinta de la maquina y no esta limitada a las operaciones de inserción y extracción, sino que puede rastrear los datos de la cinta y modificar las celdas que desee sin alterar las demás.
En la siguiente figura 1.1 se representa una maquina deTuring, allí en mecanismo de control de la maquina esta representado por un rectángulo con una especie de carátula de reloj que indica el estado actual de la maquina. Encima de este se encuentra la cinta de la maquina; la cabeza de la maquina esta indicada con un apuntador.
La definición formal de una maquina de Turing estará dada de la siguiente forma:
Una maquina de Turing es una séxtupla dela forma (S, ∑, Ґ, δ, ι, h), donde:
S es una colección finita de estados.
∑ es un conjunto finito de símbolos distintos de espacio en blanco, llamado alfabeto de la maquina.
Ґ es un conjunto finito de símbolos, incluidos los de ∑, que se conocen como símbolos de la cinta de la maquina.
δ es la función de transición de la maquina.
ι es unelemento de S llamado estado inicial
h es un elemento de S llamado estado de parada.
Es conveniente contar con una notación que represente la configuración de la cinta de la maquina de Turín, incluyendo el contenido de sus celdas y la posición de la cabeza. En estos casos se presenta el contenido de las celdas de la cinta, subrayando la posición de la cabeza. De esta forma ΔxyzΔΔ…representara una cinta que contiene un espacio en blanco, seguido por los símbolos x,y y z, seguidos a su vez de espacios es blanco, con la cabeza sobre la celda que contiene la z.
LOS ORIGENES DE LAS MAQUINAS DE TURING
El propósito para el cual se desarrollaron las maquinas de Turín fue el de contener todo el poder de los procesos computacionales. Es decir, la intención de Turing fuedesarrollar un sistema en el cual fuera posible modelas cualquier proceso que pudiera considerarse como un calculo.
Turing pensó en un cálculo realizado por un ser humano con lápiz y papel. Bajo este contexto razono que en un momento dado las personas solo podrían concentrarse en un porción restringida del papel y que a su vez la colección de marcas en este trozo de papel se podía considerar comoun solo símbolo.
Por esto considero dividir un papel en secciones, cada una de las cuales constituía la cantidad de papel requerida para registrar un solo símbolo. Turing llego a la conclusión de que cualquier proceso computacional solo podía implicar un número finito de símbolos.
Una maquina de Turing nunca se ve restringida por la carencia de espacio de almacenamiento, algo que...
4.1 DEFINICION FORMAL DE UNA MAQUINA DE TURING
La clase de autómatas que ahora se conocen como maquinas de Turing fue propuesta por Alan M. Turing en 1936, la idea básica de Turing fue estudiar los procesos algorítmicos utilizando un modelo computacional.
Las maquinas de Turing se asemejan a los autómatas finitos en que constan de un mecanismo de control y un flujo deentrada (cinta); la diferencia es que las maquinas de Turing pueden mover sus cabezas de lectura hacia delante y hacia atrás y pueden leer o escribir en la cinta.
PROPIEDADES BASICAS DE LAS MAQUINAS DE TURING
Esta maquina contiene un mecanismo de control que en cualquier momento puede encontrarse en uno de entre un numero finito de estados. Uno de estos estados es un estado inicial en elcual se comienzan los cálculos y otro es el estado de parada cuando se llega a estado se terminan los cálculos, este difieres de los estados de aceptación de los autómatas finitos y de pila en que pueden continuar sus cálculos después de llegar aun estado de aceptación, una maquina de Turing debe detenerse en el momento que llega al estado de parada (por lo anterior la maquina debe tener por lomenos dos estados).
La diferencia mas importante es que una maquina de Turing esta equipada con una cabeza que puede leer y escribir símbolos en la cinta de la maquina y no esta limitada a las operaciones de inserción y extracción, sino que puede rastrear los datos de la cinta y modificar las celdas que desee sin alterar las demás.
En la siguiente figura 1.1 se representa una maquina deTuring, allí en mecanismo de control de la maquina esta representado por un rectángulo con una especie de carátula de reloj que indica el estado actual de la maquina. Encima de este se encuentra la cinta de la maquina; la cabeza de la maquina esta indicada con un apuntador.
La definición formal de una maquina de Turing estará dada de la siguiente forma:
Una maquina de Turing es una séxtupla dela forma (S, ∑, Ґ, δ, ι, h), donde:
S es una colección finita de estados.
∑ es un conjunto finito de símbolos distintos de espacio en blanco, llamado alfabeto de la maquina.
Ґ es un conjunto finito de símbolos, incluidos los de ∑, que se conocen como símbolos de la cinta de la maquina.
δ es la función de transición de la maquina.
ι es unelemento de S llamado estado inicial
h es un elemento de S llamado estado de parada.
Es conveniente contar con una notación que represente la configuración de la cinta de la maquina de Turín, incluyendo el contenido de sus celdas y la posición de la cabeza. En estos casos se presenta el contenido de las celdas de la cinta, subrayando la posición de la cabeza. De esta forma ΔxyzΔΔ…representara una cinta que contiene un espacio en blanco, seguido por los símbolos x,y y z, seguidos a su vez de espacios es blanco, con la cabeza sobre la celda que contiene la z.
LOS ORIGENES DE LAS MAQUINAS DE TURING
El propósito para el cual se desarrollaron las maquinas de Turín fue el de contener todo el poder de los procesos computacionales. Es decir, la intención de Turing fuedesarrollar un sistema en el cual fuera posible modelas cualquier proceso que pudiera considerarse como un calculo.
Turing pensó en un cálculo realizado por un ser humano con lápiz y papel. Bajo este contexto razono que en un momento dado las personas solo podrían concentrarse en un porción restringida del papel y que a su vez la colección de marcas en este trozo de papel se podía considerar comoun solo símbolo.
Por esto considero dividir un papel en secciones, cada una de las cuales constituía la cantidad de papel requerida para registrar un solo símbolo. Turing llego a la conclusión de que cualquier proceso computacional solo podía implicar un número finito de símbolos.
Una maquina de Turing nunca se ve restringida por la carencia de espacio de almacenamiento, algo que...
Leer documento completo
Regístrate para leer el documento completo.