Màquina de Turing

Archiu:Maquina.png

Màquina de Turing

Plantilla:Teoria d'autómates Una màquina de Turing és un dispositiu que manipula símbols sobre una tira de cinta d'acort en una taula de regles. A pesar de la seua simplicitat, una màquina de Turing pot ser adaptada per a simular la llògica de qualsevol algoritme de computador i és particularment útil en l'explicació de les funcions d'una CPU dins d'un computador.

Originalment va ser definida pel matemàtic anglés Alan Turing com una «màquina automàtica» en 1936 en la revista Proceedings of the London Mathematical Society. La màquina de Turing no està dissenyada com una tecnologia de computació pràctica, sino com un dispositiu hipotètic que representa una màquina de computació. Les màquines de Turing ajuden als científics a entendre els llímits del càlcul mecànic.

Turing va donar una definició sucinta de l'experiment en el seu ensaig de 1948, «Màquines inteligents». Referint-se a la seua publicació de 1936, Turing va escriure que la màquina de Turing, ací cridada una màquina de computació llògica, consistia en:

... una illimitada capacitat de memòria obtinguda en la forma d'una cinta infinita marcada en quadrats, en cada u dels quals podria imprimir-se un símbol. En qualsevol moment hi ha un símbol en la màquina; cridat el símbol llegit. La màquina pot alterar el símbol llegit i el seu comportament està en part determinat per eixe símbol, pero els símbols en atres llocs de la cinta no afecten el comportament de la màquina. No obstant, la cinta es pot moure cap a avant i cap a arrere a través de la màquina, sent açò una de les operacions elementals de la màquina. Per lo tant qualsevol símbol en la cinta pot tindre finalment una oportunitat.

Turing (1948, p. 61.)

Una màquina de Turing que és capaç de simular qualsevol atra màquina de Turing és cridada una màquina universal de Turing (UTM, o simplement una màquina universal). Una definició més matemàticament orientada, en una similar naturalea «universal», va ser presentada per Alonzo Church, el treball de la qual sobre el càlcul lambda s'entrellaça en el de Turing en una teoria formal de la computació coneguda com la tesis de Church-Turing. La tesis senyala que les màquines de Turing capturen, de fet, la noció informal d'un método eficaç en la llògica i les matemàtiques i proporcionen una definició precisa d'un algoritme o «procediment mecànic».

L'importància de la màquina de Turing en l'història de la computació és doble: primer, la màquina de Turing va ser un dels primers (si no el primer) models teòrics per a les computadores, veent la llum en 1936. Segon, estudiant els seus propietats abstractes, la màquina de Turing ha servit de base per a molt desenroll teòric en les ciències de la computació i en la teoria de la complexitat. Una raó per a açò és que les màquines de Turing són simples, i per tant amenes a l'anàlisis. Dit açò, cal aclarir que les màquines de Turing no són un model pràctic per a la computació en màquines reals, les quals precisen models més ràpits com els basats en RAM.

Història

Archiu:Alan Turing cropped.jpg

Estàtua d'Alan Turing en un retrat de fondo.

Archiu:Turing Machine.png

Representació artística d'una màquina de Turing.

Alan Turing va introduir el concepte de màquina de Turing en el treball On computable numbers, with an application to the Entscheidungsproblem, publicat per la Societat Matemàtica de Londres en 1936, en el que s'estudiava la qüestió plantejada per David Hilbert sobre si les matemàtiques són decidibles, és dir, si hi ha un método definit que puga aplicar-se a qualsevol sentència matemàtica i que nos diga si eixa sentència és certa o no. Turing va idear un model formal de computador, la màquina de Turing, i va demostrar que existien problemes que una màquina no podia resoldre.

En este aparat extremadament senzill és possible realisar qualsevol còmput que un computador digital siga capaç de realisar.

Per mig d'este model teòric i l'anàlisis de la complexitat dels algoritmes, va ser possible la categorisació de problemes computacionals d'acort al seu comportament, apareixent aixina, el conjunt de problemes denominats P i NP, les solucions de la qual poden trobar-se en temps polinòmic per màquines de Turing determinista i no determinista, respectivament.

Precisament, la tesis de Church-Turing formulada per Alan Turing i Alonzo Church, de forma independent a mitan de el XX caracterisa la noció informal de computabilidad en la computació per mig d'una màquina de Turing.

L'idea subjacent és el concepte de que una màquina de Turing pot vore's com un autómata eixecutant un procediment efectiu definit formalment, a on l'espai de memòria de treball és illimitat, pero en un moment determinat solament una part finita és accessible.

Descripció informal

Archiu:Turing machine 2b.svg

Ací es mostra l'estat intern (q₁) dins del cabezal, i l'ilustració descriu la cinta com sent infinita i omplida prèviament en «0», el símbol servint com a blanc. L'estat complet del sistema (la seua configuració) consistix de l'estat intern, el contingut de les caselles sombreadas incloent el blanc llegit el cabezal («11B») i la posició del cabezal..

Archiu:TuringBeispielAnimatedG caps block 8 .gif

Animació de la màquina de Turing

La màquina de Turing modela matemàticament a una màquina que opera mecánicamente sobre una cinta. En esta cinta hi ha símbols que la màquina pot llegir i escriure, un al mateix temps, usant un cabezal llector/escritor de cinta. L'operació està completament determinada per un conjunt finito d'instruccions elementals com «en l'estat 42, si el símbol vist és 0, escriu un 1; Si el símbol vist és 1, canvia l'estat 17; en l'estat 17, si el símbol vist és 0, escriu un 1 i canvia l'estat 6; etc». En l'artícul original («Sobre números computables en una aplicació al Entscheidungsproblem»), Turing no imagina un mecanisme, sino una persona a la que ell crida la «computadora», qui eixecuta servilmente estes regles mecàniques determinista (o com Turing posa, «d'una manera desganada»).

Més precisament, una màquina de Turing consta de:

1. Una cinta que es dividix en celes, una al costat de l'atra. Cada cela conté un símbol d'algun alfabet finito. L'alfabet conté un símbol especial cridat blanc (ací escrit com a «B») i un o més símbols adicionals. La cinta se supon que és arbitrariamente extensible cap a l'esquerra i cap a la dreta, és dir, la màquina de Turing sempre és proveïda en tanta cinta com necessite per a la seua computació. Les celes que no s'hagen escrit prèviament s'assumixen que estan reblixes en el símbol blanc. En alguns models la cinta té un extrem esquerre marcat en un símbol especial; la cinta s'estén o és indefinidament extensible cap a la dreta.

1. Un cabezal que pot llegir i escriure símbols en la cinta i moure la cinta a l'esquerra i a la dreta una (i solament una) cela al mateix temps. En alguns models el cabezal es mou i la cinta és estacionaria.
2. Un registre d'estat que almagasena l'estat de la màquina de Turing, un dels estats finitos. Hi ha un estat inicial especial en el que el registre d'estat s'inicia. Turing escriu que estos estats reemplacen el «estat de la ment» en que ordinàriament estaria una persona realisant càlculs.
3. Una taula finita d'instruccions (cridada ocasionalment com a taula d'acció o funció de transició). Les instruccions són usualment 5-tuplas: q_ia_j→q_i1a_j1d_k, (a voltes 4-tuplas), que, donat el estat (q_i) en que la màquina es troba actualment i el símbol (a_j) que s'està llegint en la cinta (el símbol actualment baix del cabezal) li indica a la màquina fer lo següent en seqüència (per als models de 5-tupla):
   • Borra o escriu un símbol (reemplaçant a_j en a_j1), i llavors
   • Mou el cabezal (que és descrit per d_k i pot tindre els valors: «L» per a un pas a l'esquerra, o «R» per a un pas a la dreta, o «N» per a permanéixer en el mateix lloc) i després
   • Assumix el mateix o un nou estat com prescrit (veu l'estat q_i1).

En els models de 4-tupla, són especificades com a instruccions separades: borrar o escriure un símbol (a_j1) i moure el cabezal a l'esquerra o la dreta (d_k). Específicament, la taula indica a la màquina: (ia) borrar o escriure un símbol o (ib) moure el cabezal a l'esquerra o a la dreta, i després (ii) assumir el mateix o un nou estat, pero no les dos accions (ia) i (ib) en la mateixa instrucció. En alguns models, si no hi ha cap entrada en la taula per a l'actual combinació de símbol i estat, la màquina es detindrà; atres models requerixen que estiguen plenes totes les entrades.

Note que cada part de la màquina — el seu estat i coleccions de símbols — i les seues accions — imprimir, borrar, moviment de la cinta — és finito, discret i distinguible; és la cantitat potencialment illimitada de cinta lo que li dona una cantitat illimitada d'espai d'almagasenament.

Vore també

• Teoria d'autómates
• Sistema combinacional
• Autómata finito
• Autómata en pila
• Màquina abstracta
• Màquina de Turing universal
• Màquina de Turing alternante
• Problema de la parada
• Jerarquia de Chomsky
• Joc de la vida
• Càlcul lambda
• Cucs de Paterson

Bibliografia

• (1983) Alan Turing: The Enigma, Regne Unit: 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..
• Turing, A.M. (1936). “On Computable Numbers, with an Application to the Entscheidungsproblem”. Proceedings of the London Mathematical Society 42: 230–265. doi:10.1112/plms/s2-42.1.230.
• Turing, A.M. (1938). “On Computable Numbers, with an Application to the Entscheidungsproblem: A correction”. Proceedings of the London Mathematical Society 43 (6): 544–6. doi:10.1112/plms/s2-43.6.544.