Máquina de Turing

Unha máquina de Turing é un dispositivo abstracto que funciona como hipótese de computación. 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 hai 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. Alan Turing, «Máquinas intelixentes» (1948)

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.

Ademais, 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 sigan a arquitectura de Von Neumann, mais a súa importancia teórica 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 non baseado 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 niveis 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 á mesma 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 (coma 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 resolubles 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 ineficiente ou, nalgúns casos, 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 poida 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

Unha 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, non necesariamente por computadores, como explica o artigo orixinal "Sobre números computables cunha aplicación ao Entscheidungsproblem".

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 diferenza 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 explicitamente 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 baleira (ε) terá que ser excluída da linguaxe a tratar.

Definición formal

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

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

onde:

$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.

Descrición instantánea

Secuencia da forma $\alpha _{1}q_{i}\alpha _{2}$ na cal $\alpha _{1},\alpha _{2}\in \Gamma ^{*}$ e $q_{i}\in Q$ onde $q_{i}$ describe o estado actual da máquina. Por convención, a cabeza de lectura/escritura apunta ao primeiro símbolo que conforma $\alpha _{2}$ .

Por tanto, consta dos seguintes elementos:

Estado.
Contido da cinta.
Posición da cabeza de lectura/escritura.

Así, dícese que para $M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},B,F),\!$

con posibles transicións que movan o cabezal á esquerda como $\delta (q_{0},x_{k})=(q_{1},y,L)$

e transicións que fagan o propio á dereita $\delta (q_{0},x_{k})=(q_{1},y,R)$ .

Basándonos nunha descrición instantánea xenérica de $M$ : $x_{1}\ldots x_{k-1}q_{0}x_{k}\ldots x_{n},x_{i}\in \Gamma ,q_{0}\in Q$

podemos executar:

Desprazamentos á esquerda: $x_{1}\ldots x_{k-1}q_{0}x_{k}\ldots x_{n}\vdash x_{1}\ldots x_{k-2}q_{1}x_{k-1}yx_{k+1}\ldots x_{n}$
Desprazamentos á dereita: $x_{1}\ldots x_{k-1}q_{0}x_{k}\ldots x_{n}\vdash x_{1}\ldots x_{k-1}yq_{1}x_{k+1}\ldots x_{n}$

considerando o caso $\alpha _{1}q_{i}\alpha _{2}\vdash ^{*}\beta _{1}q_{j}y\beta _{2}$ que implicará parada cando a transición $\delta (q_{j},y)$ non estea definida.

Ademais, o caso $\alpha _{1}q_{0}\alpha _{2}\vdash ^{*}\infty$ implica non parar nunca.

Diagrama de estados

É posible representar máquinas de Turing mediante grafos con arestas dirixidas tamén chamados diagramas de estados. As principais convencións son as seguintes:

Estado inicial cunha única aresta incidente que non provén doutro vértice.
Estado final representado por unha dobre circunferencia.
Arestas etiquetadas coas transicións.

Exemplo

Unha aplicación sinxela dunha máquina de Turing estándar é a conversión dun número en alfabeto unario (é dicir, unicamente con 1's) a binario. Por simplicidade empregarase o alfabeto $\Sigma =\{0,1,=,x,B\}$ . O $x$ terá como obxectivo "marcar" as cifras en unario xa traducidas en formato binario. $B$ refírese ao espazo en branco.

Posible contido inicial de cinta: " $=1111111111$ " (equivalente ao número 10 en alfabeto decimal).
Respectivo contido final: " $1010=1111111111$ "

O conxunto de estados requiridos será

$Q=\{q_{0},q_{1},q_{2},q_{3},q_{4},q_{5}\}$

con $q_{0}$ estado inicial e $q_{5}$ estado final.

Así, a táboa de transicións (equivalente ás arestas da imaxe) será:

Estado	Símbolo leído	Símbolo escrito	Mov.	Estado sig.
$q_{0}\,\!$	1	0	$R\,\!$	$q_{0}\,\!$
$q_{0}\,\!$	=	=	$R\,\!$	$q_{1}\,\!$
$q_{1}\,\!$	x	x	$R\,\!$	$q_{1}\,\!$
$q_{1}\,\!$	B	B	$L\,\!$	$q_{4}\,\!$
$q_{1}\,\!$	1	x	$L\,\!$	$q_{2}\,\!$
$q_{2}\,\!$	x	x	$L\,\!$	$q_{2}\,\!$
$q_{2}\,\!$	=	=	$L\,\!$	$q_{3}\,\!$
$q_{3}\,\!$	1	1	$L\,\!$	$q_{3}\,\!$
$q_{3}\,\!$	0	1	$R\,\!$	$q_{0}\,\!$
$q_{3}\,\!$	0	1	$R\,\!$	$q_{0}$
$q_{4}\,\!$	x	1	$L\,\!$	$q_{4}\,\!$
$q_{4}\,\!$	=	=	$R\,\!$	$q_{5}\,\!$

Seguindo a computación da máquina de acordo á cadea de entrada " $=11$ " (resáltase a cabeza de lectura/escritura):

Paso	Estado	Cinta
1	$q_{0}\,\!$	=11
2	$q_{1}\,\!$	=11
3	$q_{2}\,\!$	=x1
4	$q_{3}\,\!$	=x1
5	$q_{0}\,\!$	1=x1
6	$q_{1}\,\!$	1=x1
7	$q_{1}\,\!$	1=x1
8	$q_{2}\,\!$	1=xx
9	$q_{2}\,\!$	1=xx
10	$q_{3}\,\!$	1=xx
11	$q_{3}\,\!$	1=xx
12	$q_{0}\,\!$	11=xx
13	$q_{0}\,\!$	10=xx
14	$q_{1}\,\!$	10=xx
15	$q_{1}\,\!$	10=xx
16	$q_{1}\,\!$	10=xx
17	$q_{4}\,\!$	10=xx
18	$q_{4}\,\!$	10=x1
19	$q_{4}\,\!$	10=11
20	$q_{5}\,\!$	10=11
Parada

Unha vez entrado no estado $q_{4}$ , a máquina substitúe cada $x$ por $1$ , dando por finalizada a tradución do número.

Modificacións

As versións modificadas da máquina de Turing estándar descritas a continuación non engaden ningún tipo de capacidade computacional, soamente simplifican algunhas aplicacións a nivel conceptual.

Máquina de Turing con opción de non movemento

$\delta :Q*\Gamma \rightarrow Q*\Gamma *\{R,L,E\}$

onde $E$ representa unha situación estática da cabeza de lectura/escritura.

A MT con opción de non movemento pódese simular cunha MT estándar, o que demostra que, en efecto, esta modificación non engade ningún tipo de complexidade computacional.

$\delta '(q_{j},a)=(q_{j},b,L\ ou\ R)$ sempre que na MT con opción de non movemento haxa $\delta (q_{j},a)=(q_{j},b,L\ ou\ R)$
$\delta '(q_{i},a)=(q_{jM},b,R)$ e $\delta '(q_{jM},c)=(q_{j},c,L)$ sempre que na MT con opción de non movemento haxa unha situación estática do tipo $\delta (q_{i},a)=(q_{j},b,E)$ .

Neste último caso haberá transicións para cada elemento $c\in \Gamma$ .

Máquina de Turing con cinta semi-infinita

Pista superior co contido da máquina de Turing estándar $M$ desde o cabezal ata a dereita.
Pista inferior co contido da máquina de Turing estándar $M$ desde o cabezal ata a esquerda en orde invertida.

A cinta semi-infinita con dous pistas (ambas limitadas nun extremo) ten como consecuencia que cada estado funcione con dous conxuntos, cada un referido a unha das pistas (inferior e superior). Para cambiar de pista serán necesarios marcadores especiais #.

Máquina de Turing con cinta de entrada

Cinta de só lectura
Unidade de control
Cinta estándar

Nesta modificación a entrada (input) está escrita nunha cinta que funciona como só de lectura (non se pode escribir). Unha unidade de control lee os símbolos da entrada así como o que se encontra baixo a cabeza de lectura/escritura na cinta estándar para executar as transicións.

Máquina de Turing multicinta

$\delta :Q*\Gamma ^{n}\rightarrow Q*\Gamma ^{n}*\{L,R\}^{n}$

Unha MT con $n$ cintas podería simularse con $2n$ pistas.

$n$ para representar o contido das $n$ cintas da máquina multicinta.
$n$ para representar os cabezales das $n$ cintas da máquina multicinta.

Máquina de Turing multidimensional

Ao aumentar o número de dimensións tamén o fan os extremos infinitos da cinta. O caso máis sinxelo é unha MT bidimensional:

$\delta :Q*\Gamma \rightarrow Q*\Gamma *\{R,L,U,D\}$

onde $U$ e $D$ sinalan "up" e "down".

Máquina de Turing non determinista

$\delta :Q*\Gamma \rightarrow 2^{Q*\Gamma *\{L,R\}}$

Unha MT non determinista pode estar en varios estados á vez, é dicir, considera cada estado de cada momento como unha hipótese ("é posible que esteamos en $q_{0}$ , mais quizais tamén en $q_{1}$ "). Vista desde a perspectiva dunha máquina estándar, a MT non determinista é replicable creando $2n$ pistas con $n$ sendo o número de MT a simular.

Véxase tamén

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.
Hopcroft, J. E, Motwani, R., e Ullman, J.D "Introducción a la Teoría de Autómatas, Lenguajes y Computación". Addison Wesley. 2002.
P. Linz. "An Introduction to Formal Languages and Automata". Jones and Bartlett Publishers, Inc. 2001.

Outros artigos

Autómata finito