Jon Callas from San Jose, USA CC BY 2.0 via Wikimedia Commons

En esta ocasión voy a presentar un breve recuento formal de lo qué es una máquina de turing. Esta máquina teórica es la única que logra reconocer los lenguajes recursivamente enumerables, en la jerarquía de Chomsky. Es por lo tanto la máquina más poderosa y la única que puede leer un lenguaje de programación. De aquí, que cada computadora logra simular una máquina de turing. Pero comencemos con el recuento.

Definición. 

Una Máquina de Turing(MT) según Hopcroft and Ullman[1] es una 7-tupla que se describe de la siguiente forma: 

M = Q,Σ,Γ,δ,q0,B,F⟩ 

Donde Q es el conjunto de estados de control; Σ es un conjunto finito de símbolos de entrada; Γ es el conjunto completo de símbolos en la cinta, Σ Γ; δ es la función de transición (los argumentos de δ(q,X) son un estado q y un símbolo de cinta X; y su valor es una 3-tupla (p, Y, D) donde p Q es el siguiente estado, Y es el símbolo en Γ escrito en la celda explorada y D es la dirección, ya sea L o R, izquierda o derecha respectivamente); q0 Q es el estado de inicio; B es el símbolo en blanco, B Γ,B ̸∈ Σ; y F que es un conjunto de estados finales o de aceptación, F Q

Una máquina con múltiples cintas se define por: 

M = Q,Σ,Γ,δ,[q1,B],[B,B],{[qn,B]}⟩

 El conjunto de estados Q es {q1,q2,...,qn}×{0,1,B}; El conjunto de símbolos Γ es {B, ∗} × {1, 2, c, B}; el conjunto de símbolos de entrada Σ, y la función de transición δ

¿Cuándo un conjunto o un lenguaje es reconocido por una máquina de turing?

Sea M una máquina de turing, L(M) es un conjunto de símbolos w Σ pero al llegar a un estad q y δ(q,X) es indefinida, puede no q F. Si todo estado q tiene una δ definida, también es reconocible. 

¿Cuándo es aceptado?

Sea M una máquina de turing. L(M) es el conjunto de símbolos w Σtal que q0w αpβ para algún estado p F y cualquier cadena α y β[1]. Se acepta el lenguaje cuando la máquina de turing se detiene en un estado q F y no hay mas movimientos posibles, δ(q, X) es indefinida. 

¿Cuándo es recursivo o decidible?

Los lenguajes con MT que paran eventualmente, sin importar si son aceptados o no son llamados recursivos. Las máquinas de turing que siempre paran, sin importar si son aceptados son buenos modelos para algoritmos. Si un algoritmo para resolver cierto problema existe, entonces se dice que el problema es decidible. 

Nota curiosa: Carta de Kurt Gödel a Jhon con Neumann

Cómo dato curioso, el problema de si P = NP o no ha marcado las máquinas de turing. Si bien el problema fue formulado posteriormente, un primer acercamiento a este fue hecho en una carta de Gödel a Neuman. Esta dice en lo general:

"Se puede construir una maquina de turing para cualquier fórmula F en predicado lógico de primer orden y para todo número natural n, que permite decidir si existe una demostración de F en una longitud de n, donde la longitud es igual al número de símbolos. Sea Ψ(F,n) el número de pasos que la máquina requiere para ello, y sea φ(n) = maxF Ψ (F, n). La pregunta es que tan rápido φ(n) crece para una máquina óptima. Se puede mostrar que φ(n)kn2Si realmente existe una máquina con φ(n) kn2 esto tendría fuertes consecuencias. Si n fuera tan largo que ya no se obtendría resultado, se podría asegurar que el problema no tiene resultado."

Sin embargo, Gödel piensa que esa tunción φ crecería de manera tan lenta que permanecería dentro de lo resolvible. Las máquinas de turing han marcado la ciencia de la computación y son su fundamento. Saber su planteamiento teórico es fundamental. Espero que este breve artículo sirva a su mejor comprensión. 

Referencias

[1] Hopcroft John E., Motwani Rajeev y Ullman, Jeffrey D. Introduction to Automata Theory, Languages, and Computation (3rd Edition). Addison-Wesley Longman Publishing Co., Inc., 2006.

 

 

 

Share This