La máquina de Turing

En este momento presentaremos la Máquina de Turing, esta es una máquina diferente a las que habíamos visto en la forma como trabaja ya que la cadena que acepta está contenida en elemento de memoria. Hasta ahora no habíamos visto nada así, esta situación se puede apreciar en el hecho que el alfabeto de las cadenas terminales están contenidas en el alfabeto de la cinta. También se puede apreciar que es una generalización del ALF ya que el alfabeto de la cinta no especifica la existencia de los marcadores de inicio y fin de cinta. O

MT #

Una Máquina de Turing (MT) es una tupla \((Q,\Sigma,\Gamma,q_0,B,A, \delta )\) donde:
  • \(Q\) es un conjunto de estados finitos
  • \(\Sigma\) es un alfabeto de símbolos terminales
  • \(\Gamma\) es un alfabeto de la cinta tal que \(\Sigma \subset \Gamma \)
  • \(q_0\) es un estado que denominaremos inicial donde \(q_0 \in Q\)
  • \(B\) es un símbolo de espacio en blanco
  • \(A\) es un conjunto de estados que denominaremos finales donde \(A \subset Q\)
  • \(\delta\) es una función de transición que cumple con:
\[\delta:Q \times \Gamma \rightarrow Q \times \Gamma \times \{left,right\} \]

La cinta #

Una situación que genera confusión es la naturaleza de la cinta, ya que pareciera que necesitaríamos una cantidad infinita de esta y que toda máquina de Turing sería imposible de construir físicamente. Sin embargo, a la memoria la debemos considerar como un elemento del cual podemos obtener más si es necesario para la computación específica que se hace, no como un recurso indispensable del diseño. Recordemos que el AP también ya levantaba este dilema, ya que la pila también es un elemento de memoria potencialmente infinita.

Ejemplo de MT #

La siguiente tabla de transición especifica una Máquina de Turing

Q X Y a b 𝖁
⟶q_0 /Y→q_3,R /X→q_1,R
q_1 /Y→q_1,R /a→q_1,R /Y→q_2,L
q_2 /X→q_0,R /Y→q_2,L /a→q_2,L
q_3 /Y→q_3,R /𝖁→q_4,L
q_4

De forma gráfica la MT luce de esta forma:

MT para cadenas aⁿbⁿ con n>0

A continuación se puede apreciar como una MT analiza una cadena. En particular, hay que observar que se termina el análisis porque se alcanza el estado final.

Análisis para la cadena aaabbb

comments powered by Disqus