Maquina de Turing - Investigacion

¿Qué es una máquina de Turing y cómo funciona?

La llamada “Máquina de Turing” es en realidad un modelo matemático consistente en un autómata que es capaz de “implementar cualquier problema matemático expresado a través de un algoritmo”. A pesar de esta definición tan complicada, en realidad la máquina de Turing destaca por su simplicidad pues manipula símbolos sobre una tira de cinta siguiendo una serie de reglas. A pesar de esta simplicidad, una máquina de Turing puede adaptarse para que simule la lógica de cualquier algoritmo de computador, de ahí su enorme potencial y valor.
 

Uno de los teoremas más importantes sobre las máquinas de Turing es que pueden simular el comportamiento de una computadora (almacenamiento y unidad de control).
Por ello, si un problema no puede ser resuelto por una de estas máquinas, entonces tampoco puede ser resuelto por una computadora

Teoremas sobre las máquinas de Turing
 

Recordemos que llamamos lenguaje Recursivamente Enumerable (RE) a los lenguajes que pueden ser aceptados por una Máquina de Turing.
 

Teorema 1 Todo lenguaje aceptado por una Máquina de Turing de varias cintas es Recursivamente Enumerable.

Teorema 2 Sea L = L(M) el lenguaje que acepta una máquina de Turing no determinista M, entonces existe una máquina de Turing deterministaN que acepta dicho lenguaje, es decir, L(M) =L (N).

Esta máquina de Turing está definida sobre el alfabeto 

${\displaystyle \Sigma =\{a,b,c\}}$, posee el conjunto de estados

${\displaystyle Q=\{q_{o},q_{1},q_{2},q_{3},q_{4},q_{5},q_{6}\}}$, con las transiciones que se pueden ver. Su estado inicial es ${\displaystyle q_{0}}$ y el estado final es ${\displaystyle q_{2}}$, el lenguaje de salida
${\displaystyle \Gamma =\{X,Y,Z,B\}}$ siendo ${\displaystyle B}$ el símbolo denominado "blanco". Esta máquina reconoce la expresión regular de la forma ${\displaystyle a^{n}b^{n}c^{n}}$ con

${\displaystyle n>=0}$.