Máquina de Turing

miniatura|361x361px|Esquema de 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 cunha 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 en 1936 como unha «máquina automática» na revista *Proceedings of the London Mathematical Society*. Dise, xa que logo, 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 daqueles que non o son (ver Tese de Church-Turing).

Turing definiu o concepto no seu ensaio «Máquinas intelixentes», de 1948. Referíndose á súa publicación de 1936, 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 obtida baixo a forma dunha cinta infinita marcada con cadros, en cada un dos cales se pode imprimir un símbolo. Sempre hai un símbolo na máquina: o símbolo lido. A máquina pode modificar o símbolo lido e o comportamento posterior desta está determinado por ese mesmo símbolo, pero os símbolos doutros lugares da cinta non afectan o comportamento da máquina. Non obstante, a cinta pode moverse cara a adiante e cara a atrás a través da máquina, na que é unha das operacións elementais dela. Polo tanto, calquera símbolo na cinta pode ter finalmente unha oportunidade.

Alan Turing, «Máquinas intelixentes» (1948)Existen diferentes variacións da máquina de Turing clásica. Entre elas atópanse:

* **Máquina de Turing con opción de non-movemento**
* **Máquina de Turing con cinta semiinfinita**
* **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 baseá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 
[esquerda|miniatura|Estatua de [Alan Turing cun retrato de fondo]]
miniatura|300x300px|Representación artística dunha máquina de Turing (suponse cinta infinita)
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 dese algoritmo), aínda que 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 á custa 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 algoritmicamente para os que 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 
miniatura|300x300px|A cinta funciona como unha colección unidimensional de celas. Cada cela contén un único símbolo. A cinta esténdese infinitamente en ambas as direccións. A cabeza de escritura/lectura mostra o estado interno da máquina (neste caso q1). A cabeza pode moverse á esquerda ou á dereita, cun desprazamento cela-a-cela. Na máquina de Turing clásica, neste desprazamento só é posible ler e escribir un único símbolo.
miniatura|Animación de máquina de Turing
Unha máquina de Turing pode considerarse un autómata apoiado nun dispositivo de almacenamento infinito (**cinta**) así como unha **cabeza de lectura/escritura**. Nesta cinta hai símbolos que terán que pertencer ao alfabeto da cinta (ou ao de entrada) para poderen ser lidos/escritos. Todo o labor da máquina de Turing pode ser realizado 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 desta 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, ao contrario 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 as direccións).
* **Función de transición determinista** (cada configuración estado-símbolo ten un movemento definido como máximo).
* **Entradas e saídas codificadas explicitamente** **na cinta**.

Para tales propósitos, é común empregar os espazos en branco a ambos os 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 que se vai 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í, dise que para M=(Q, \Sigma, \Gamma, \delta, q_0, B, F),\!

con posibles transicións que movan a cabeza de lectura/escritura á 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).
miniatura|Visualización dunha máquina de Turing: cinta e cabeza visibles (asúmese que é infinita en ambos extremos).|282x282px

Baseá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} y x_{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} y q_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 
[miniatura|Máquina de Turing definida sobre o [alfabeto \Sigma=\{a,b,c\}. Posúe o conxunto de estadosQ=\{q_0,q_1,q_2,q_3,q_4,q_5,q_6\}. Estado inicial q_0 e estado final q_3.|326x326px]]
É 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.

miniatura|Aplicación sinxela dunha máquina de Turing para converter secuencias de 1's no seu análogo en formato binario.|393x393px
Así, a **táboa de transicións** (equivalente ás arestas da imaxe) será: 

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

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 semiinfinita 
* **Pista superior** co contido da máquina de Turing estándar M desde a cabeza de lectura/escritura ata a dereita.
* **Pista inferior** co contido da máquina de Turing estándar M desde a cabeza de lectura/escritura ata a esquerda en orde invertida.

A cinta semiinfinita con dúas 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 le 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 as cabezas 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 que se vai simular. 

## Véxase tamén 
### Bibliografía 
* 
* 
* 
* 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