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 #
- \(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:
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:
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.