Máquina de Turing
Este artigo ou sección precisa dunha revisión ortográfica e/ou de gramática (recurso útil: corrector ortográfico en liña de galego). Podes axudarte do revisor ortográfico, activándoo en: Preferencias → Trebellos → Navegación → Ortografía: Activar o revisor ortográfico. Colabora connosco neste artigo e noutros en condicións semellantes para que a Galipedia mellore e medre. |
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 lido. A máquina pode modificar o símbolo lido 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 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
editarAlan 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
editarUnha 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 saídas 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
editarUnha máquina de Turing estándar (baseada nunha soa cinta) pode definirse como unha 7-tupla
onde:
- : conxunto finito de estados.
- : alfabeto de entrada (funciona como subconxunto do alfabeto de cinta prescindindo do espazo en branco).
- : alfabeto de cinta sabendo que .
- : función de transición.
- : estado inicial.
- : espazo en branco ( ).
- : conxunto de estados finais.
Descrición instantánea
editarSecuencia da forma na cal e onde describe o estado actual da máquina. Por convención, a cabeza de lectura/escritura apunta ao primeiro símbolo que conforma .
Por tanto, consta dos seguintes elementos:
- Estado.
- Contido da cinta.
- Posición da cabeza de lectura/escritura.
Así, dise que para
con posibles transicións que movan o cabezal á esquerda como
e transicións que fagan o propio á dereita .
Basándonos nunha descrición instantánea xenérica de :
podemos executar:
- Desprazamentos á esquerda:
- Desprazamentos á dereita:
considerando o caso que implicará parada cando a transición non estea definida.
Ademais, o caso implica non parar nunca.
Diagrama de estados
editarÉ 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
editarUnha 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 . O terá como obxectivo "marcar" as cifras en unario xa traducidas en formato binario. refírese ao espazo en branco.
- Posible contido inicial de cinta: " " (equivalente ao número 10 en alfabeto decimal).
- Respectivo contido final: " "
O conxunto de estados requiridos será
con estado inicial e 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. |
---|---|---|---|---|
1 | 0 | |||
= | = | |||
x | x | |||
B | B | |||
1 | x | |||
x | x | |||
= | = | |||
1 | 1 | |||
0 | 1 | |||
0 | 1 | |||
x | 1 | |||
= | = |
Seguindo a computación da máquina de acordo á cadea de entrada " " (resáltase a cabeza de lectura/escritura):
Paso | Estado | Cinta |
---|---|---|
1 | =11 | |
2 | =11 | |
3 | =x1 | |
4 | =x1 | |
5 | 1=x1 | |
6 | 1=x1 | |
7 | 1=x1 | |
8 | 1=xx | |
9 | 1=xx | |
10 | 1=xx | |
11 | 1=xx | |
12 | 11=xx | |
13 | 10=xx | |
14 | 10=xx | |
15 | 10=xx | |
16 | 10=xx | |
17 | 10=xx | |
18 | 10=x1 | |
19 | 10=11 | |
20 | 10=11 | |
Parada |
Unha vez entrado no estado , a máquina substitúe cada por , dando por finalizada a tradución do número.
Modificacións
editarAs 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
editar
onde 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.
- sempre que na MT con opción de non movemento haxa
- e sempre que na MT con opción de non movemento haxa unha situación estática do tipo .
Neste último caso haberá transicións para cada elemento .
Máquina de Turing con cinta semi-infinita
editar- Pista superior co contido da máquina de Turing estándar desde o cabezal ata a dereita.
- Pista inferior co contido da máquina de Turing estándar 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
editar- 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
editar
Unha MT con cintas podería simularse con pistas.
- para representar o contido das cintas da máquina multicinta.
- para representar os cabezais das cintas da máquina multicinta.
Máquina de Turing multidimensional
editarAo aumentar o número de dimensións tamén o fan os extremos infinitos da cinta. O caso máis sinxelo é unha MT bidimensional:
onde e sinalan "up" e "down".
Máquina de Turing non determinista
editar
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 , mais quizais tamén en "). Vista desde a perspectiva dunha máquina estándar, a MT non determinista é replicable creando pistas con sendo o número de MT a simular.
Véxase tamén
editarWikimedia Commons ten máis contidos multimedia na categoría: Máquina de Turing |
Bibliografía
editar- 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.