• Author / Uploaded
• Skrpio Kuyoc

Citation preview

INTRODUCCION

Una máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo a una tabla de reglas. La máquina de Turing fue descrita por Alan Turíng como una «máquina automática» en 1936 en la revista Proceedings of the London Mathematical Society, La máquina de Turing no está diseñada como una tecnología de computación práctica, sino como un dispositivo hipotético que representa una máquina de computación. Las máquinas de Turing ayudan a los científicos a entender los límites del cálculo mecánico. En este trabajo se mostrara una comparativa sobre los diferentes tipos de Máquinas De Turing, se mencionara sus características, algunas ventajas y desventajas y sus aplicación respectivamente. La máquina de Turíng es diseñada para la facilitación del trabajo de representación de los procesos que realiza una computadora. Es muy utilizada por ingenieros y expertos de la computación para el modelado y simulación de eventos que podría realizar en un futuro.

Máquina de Turing con cinta infinita a ambos lados

Tipos de Maquinas de Turing

Máquina de Turing con cinta infinita a ambos lados Máquina de Turing con cinta multipista

Es aquella que mediante la cual cada celda de la cinta de una máquina sencilla se divide en subceldas. Cada celda es así capaz de contener varios símbolos de la cinta.

Una MT con más de una cinta consiste de un control finito con k cabezales lectores/escritores y k cintas. Cada cinta es infinita en ambos sentidos.

Máquina de Turing multicinta Máquina de Turing multidimensional

Máquina de Turing determinista y no determinista

Una MT multidimensional es aquella cuya cinta puede verse como extendiéndose infinitamente en más de una dirección, el ejemplo más básico sería el de una máquina bidimensional cuya cinta se extendería infinitamente hacia arriba, abajo, derecha e izquierda.

La entrada de una máquina de Turing viene determinada por el estado actual y el símbolo leído, un par (estado, símbolo), siendo el cambio de estado, la escritura de un nuevo símbolo y el movimiento del cabezal, las acciones a tomar en función de una entrada

Ventajas, desventajas y aplicaciones de las máquinas de Turíng. Tipo de Maquina de Turíng Multicinta

Ventaja 



No Determinista



Desventaja Cada sub celda es capaz de contener símbolos de la cinta Cada sub celda es capaz de contener símbolos de la cinta puede haber un número finito de movimientos a elegir



Múltiples cabezales

Offline



permite que la cinta tenga muchas dimensiones .



 

Los cabezales funcionan de forma independien te se admiten movimientos L, R o Z. Permite la resolución de problemas cuánticos.



Solo maneja una sola cinta





no puede moverse de la zona delimitada Solo puede moverse a la derecha





 



Multidimensional

No tiene más potencia que la máquina de Turíng original

Aplicación



No se gana ninguna potencia adicional a causa del no determinis mo. No es una capacidad real.

Resolución de problemas matemáticos, como son la suma, resta, multiplicación, división, etc. Funcionamiento de computadoras para la resolución de problemas. Resolución de problemas finitos.

BIBLIOGRAFÍA







 

Feynman, Richard (1996). Conferencias sobre computación. Graficromo. ISBN 84-8432444-3. http://books.google.cl/books?id=nMhfwj9WGz4C&printsec=frontcover&dq=conferenc ias+sobre+computacion&hl=es&ei=Ul85TOfaKtCQuAe17bWXBA&sa=X&oi=book_result &ct=book-thumbnail&resnum=1&ved=0CC8Q6wEwAA#v=onepage&q&f=false. Consultado el 11 de julio de 2010. Viso, Elisa (2008). Introducción a la teoría de la computación. ISBN 978-970-32-5415-6. http://books.google.cl/books?id=NXQE8NJw9d4C&pg=PA254&dq=maquina+de+turing &hl=es&ei=J2A5TPXsD4SRuAfshLSkBA&sa=X&oi=book_result&ct=result&resnum=4&v ed=0CDsQ6AEwAw#v=onepage&q=maquina%20de%20turing&f=false. Consultado el 11 de julio de 2010. De Castro, Rodrigo (2004). Teoría de la computación : lenguajes, autómatas, gramáticas. http://books.google.cl/books?id=EAbc79tlWD4C&pg=PA201&dq=codificacion+de+una +maquina+de+turing&hl=es&ei=QF8-TIeCCoWKlwf19T4BQ&sa=X&oi=book_result&ct=result&resnum=1&ved=0CCgQ6AEwAA#v=onepage& q&f=false. Consultado el 15 de julio de 2010. «on computable numbers,with an application to the entscheidungsproblem» (en español). Consultado el 15 de julio de 2010. «Variantes de una Máquina de Turing» (en español). Consultado el 11 de julio de 2010.