Máquina de Turing

Unha máquina de Turing é un dispositivo abstracto que funciona como hipótese de computación máis que unha tecnoloxía con aplicacións prácticas. Conceptualmente, manipula símbolos sobre unha tira de cinta de acordo a unha táboa de regras de transición. A pesar da súa simplicidade aparente, unha máquina de Turing pode ser adaptada para simular a lóxica de calquera algoritmo de computador. É particularmente útil na explicación das funcións dunha CPU dentro dun computador.

Foi definida en orixe polo matemático inglés Alan Turing como unha «máquina automática» en 1936 na revista Proceedings of the London Mathematical Society. Dícese, polo tanto, que as máquinas de Turing serven de apoio aos profesionais das ciencias da computación en canto que permiten diferenciar problemas resolubles por un computador dos que non o son (ver Tese de Church-Turing).

Turing definiu o concepto no seu ensaio de 1948, «Máquinas intelixentes». Referíndose á súa publicación de 1936, Turing escribiu que a máquina de Turing, aquí chamada unha "máquina de computación lóxica", consistía en:

... unha memoria de capacidade ilimitada en forma dunha cinta infinita marcada a cadros. En cada un dos mesmos pode imprimirse un símbolo. Sempre hay un símbolo na máquina: o símbolo leído. A máquina pode modificar o símbolo leído e o comportamento posterior está determinado polo mesmo, pero os símbolos doutros lugares da cinta non afectan ao comportamento da máquina. Non obstante, a cinta pode moverse cara adiante e cara atrás a través da máquina, sendo isto unha das operaciones elementais da máquina. Polo tanto, calquera símbolo da cinta pode ter finalmente unha oportunidade.^[1]

Turing (1948, p. 61.)

Existen diferentes variacións da máquina de Turing clásica. Entre as mesmas, encóntranse:

Máquina de Turing con opción de non movemento
Máquina de Turing con cinta semi-infinita
Máquina de Turing con cinta de entrada

Ademáis, outras máquinas requiren un almacenamento máis complexo como:

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

sen obviar a máquina de Turing non determinista (que é posible simular cunha máquina de Turing determinista).

Cabe resaltar que todas estas máquinas funcionan como modelos conceptuais: non hai razón práctica para computar problemas en sistemas que non sexan computadores, pero a riqueza que aportan as máquinas de Turing a nivel teórico xustifica que o seu estudo sexa fundamental nas ciencias da computación.

Destaca especialmente a máquina universal de Turing (UTM), capaz de simular as demais máquinas de Turing. Alonzo Church contribuíu a unha definición matemática das máquinas de Turing a través do cálculo lambda, especialmente á súa capacidade de definir un algoritmo de forma precisa basándose nos campos da lóxica e as matemáticas. Este sistema formal foi introducido por Alonzo Church e Stephen Kleene nos anos 30, e considérase unha linguaxe de programación minimalista e pioneira: unha aproximación equivalente á máquina de Turing desde un punto de vista funcional e non basado en hardware.

As propiedades abstractas da máquina de Turing asentaron a maior parte dos desenvolvementos teóricos das ciencias da computación, así como a teoría da complexidade computacional que distingue os problemas computacionais en distintos niveles de complexidade.

Historia

Alan Turing introduciu o concepto de máquina de Turing en On computable numbers, with an application to the Entscheidungsproblem, publicado pola Sociedade Matemática de Londres en 1936. O Entscheidungsproblem ("problema de decisión", en galego) foi un reto de lóxica simbólica no que se estudaba a existencia dun algoritmo que decidise se unha fórmula en cálculo de primeira orde era un teorema. Tanto Church como Turing chegaron á misma solución (a non existencia de dito algoritmo), aunque mediante métodos distintos. Church afrontouno mediante o cálculo lambda e os traballos previos de Kleene; mentres que Turing ideou un modelo formal de computador, a máquina de Turing, e demostrou que existían problemas que unha máquina non podía resolver (ver o célebre problema da parada para máquinas de Turing).

O modelo teórico da máquina de Turing e os fundamentos teóricos de clases de complexidade permitiron distinguir entre as clases de problemas P e NP. Os primeiros (P) son o conxunto de problemas con solución por unha máquina de Turing en tempo polinómico, mentres que os segundos (NP) son problemas cunha solución que pode atoparse mediante unha máquina de Turing non determinista en tempo polinómico. Os problemas da clase P considéranse tratables, e o resto intratables (Tese de Cook-Karp); é dicir, computables a costa de tal cantidade de recursos (tempo e memoria) que a implementación resulta imposible.

Entre os argumentos máis potentes a favor da hipótese formulada por Church e Turing encóntranse os seguintes:

Non hai problemas resolubles algorítmicamente para os cales non se poda escribir un programa para unha máquina de Turing.
Calquera problema resoluble nun computador é tamén resoluble cunha máquina de Turing.
Os modelos alternativos de computación non probaron ser máis potentes que o modelo da Tese de Church-Turing.

Definición informal

Una máquina de Turing pode considerarse un autómata apoiado nun dispositivo de almacenamento infinito (cinta) así como un cabezal de lectura/escritura. Nesta cinta hai símbolos que terán que pertencer ao alfabeto da cinta (ou ao de entrada) para poder ser lidos/escritos. Toda a labor da máquina de Turing pode ser realizada por persoas e non necesariamente por computadores, como explica o artículo orixinal Sobre números computables cunha aplicación ao Entscheidungsproblem. Así, conceptualmente non sería necesario ter un computador para levar a cabo as funcións do mecanismo da máquina de Turing servilmente.

Nunha máquina de Turing a entrada está escrita ao comezo, e a saída vaise gravando na cinta durante as sucesivas operacións. O procesamento da mesma finaliza cando alcanza un estado de parada. Asúmese que nun estado final non hai transicións definidas, polo que a máquina deterase ao chegar a un estado final. Polo tanto, non é necesario ler todo o contido da cinta para acabar o procesamento, a diferencia doutro tipo de autómatas da Xerarquía de Chomsky (autómatas de estados finitos e autómatas con pila).

Polo tanto, poderíamos resumir informalmente as características dunha máquina de Turing estándar da seguinte forma:

Cinta infinita (ambas direccións).
Función de transición determinista (cada configuración estado-símbolo ten un movemento definido como máximo).
Entradas e salidas codificadas explícitamente na cinta.

Para tales propósitos, é común empregar os espazos en branco a ambos lados das cadeas escritas na cinta como delimitadores da cadea de entrada. De adoptar esta aproximación, a cadea vacía (ε) terá que ser excluída da linguaxe a tratar.

Definición formal

Unha máquina de Turing estándar (basada nunha soa cinta) pode definirse como unha 7-tupla

M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},B,F),\!

onde:^[2]

$Q\!$ : conxunto finito de estados.
$\Sigma \!$ : alfabeto de entrada (funciona como subconxunto do alfabeto de cinta prescindindo do espazo en branco).
$\Gamma \!$ : alfabeto de cinta sabendo que $\Sigma \subseteq \Gamma -\{B\}$ .
$\delta$ : función de transición.
$q_{0}\in Q$ : estado inicial.
$B\in \Gamma \!$ : espazo en branco ( $B\notin \Sigma$ ).
$F\subseteq Q$ : conxunto de estados finais.

Véxase tamén

Referencias

↑ See the definition of "innings" on Wiktionary
↑ Pérez, Iván (2005). "Lenguaje y Compiladores" (en español): 137. |data-acceso= require |url= (Axuda)

Bibliografía

Hodges, Andrew (1983). Alan Turing: The Enigma. Reino Unido: Burnett Books/Hutchinson. ISBN 0-671-49207-1.
Minsky, Marvin (1967). "Unsolvability of the Halting Problem". Computation: Finite and Infinite Machines. NJ: Prentice–Hall, Inc.
"On Computable Numbers, with an Application to the Entscheidungsproblem". 2 42. 1936: 230–265. doi:10.1112/plms/s2-42.1.230.
"On Computable Numbers, with an Application to the Entscheidungsproblem: A correction". 2 43 (6). 1938: 544–6. doi:10.1112/plms/s2-43.6.544.

ligazón=Wikidata|alt=Wd|20x20px|Wikidata Datos: Q163310
ligazón=Wikimedia_Commons|20x20px|Commonscat Multimedia: Turing machines / Q163310

[1] See the definition of "innings" on Wiktionary

[Lenguaje_y_compiladores-2] Pérez, Iván (2005). "Lenguaje y Compiladores" (en español): 137. |data-acceso= require |url= (Axuda)

[1]

[2]