miniatura|Fotografia d'Alan Turing (1930) La màquina de Turing és un model computacional introduït per Alan Turing en l'obra On computable numbers, with an application to the Entscheidungsproblem, publicat per la Societat Matemàtica de Londres. Hi estudiava la qüestió plantejada per David Hilbert sobre si les matemàtiques són decidibles, és a dir, si hi ha un mètode definit que pugui aplicar-se a qualsevol sentència matemàtica i que resolgui si és certa o no. Turing va construir un model formal de computador, la màquina de Turing, un dispositiu que manipula símbols sobre una tira de cinta d'acord amb una taula de regles i va demostrar que existien problemes que una màquina no podia resoldre.
Malgrat la seva simplicitat, la màquina de Turing pot ser adaptada per simular la lògica de qualsevol algorisme de computador i és particularment útil en l'explicació de les funcions d'una unitat central de processament (CPU) dins d'un ordenador.
Originalment va ser definida com una «màquina automàtica» el 1936, a la revista Proceedings of the London Mathematical Society.La idea ja la va tenir el 1935 després d'una qüestió de M.H.A. Newman a les seves classes. Turing va enviar l'article el 31 de maig de 1936 a la redacció de la revista Proceedings de la London Mathematical Society (cf Hodges 1983:112), però va trigar fins a 1937 per a publicar-lo. La màquina de Turing no està dissenyada com una tecnologia de computació pràctica, sinó com un dispositiu hipotètic que representa una màquina de computació, i van ajudar els científics a entendre els límits del càlcul mecànic.
Turing va donar una definició succinta de l'experiment en el seu assaig de 1948, «Intelligent Machinery» (‘Maquinari intel·ligent’). Referint-se a la seva publicació de 1936, Turing va escriure que la màquina de Turing, aquí anomenada una màquina de computació lògica, consistia en:
Una màquina de Turing que sigui capaç de simular qualsevol altra màquina de Turing és anomenada com una màquina universal de Turing (UTM, o simplement una màquina universal). Una definició més matemàticament orientada, amb una semblant naturalesa «universal», va ser presentada per Alonzo Church, el treball sobre el càlcul lambda s'entrellaça amb el de Turing en una teoria formal de la computació coneguda com la tesi de Church-Turing. La tesi assenyala que les màquines de Turing capturen, de fet, la noció informal d'un mètode eficaç en la lògica i les matemàtiques i proporcionen una definició precisa d'un algoritme o 'procediment mecànic'.
Quan se'n estudia les propietats abstractes, la màquina de Turing produeix moltes perspectives en les ciències de la computació i en la teoria de la complexitat.
Història Alan Turing va introduir el concepte de màquina de Turing a l'article On computable numbers, with an application to the Entscheidungsproblem, publicat per la Societat Matemàtica de Londres el 1936, en el qual estudiava la qüestió plantejada per David Hilbert sobre si les matemàtiques són decidibles.
Mitjançant aquest model teòric i l'anàlisi de la complexitat dels algoritmes, va ser possible de categoritzar problemes computacionals d'acord amb el seu comportament, apareixent així, el conjunt de problemes denominats P i NP, les solucions poden trobar-se en temps polinòmic per màquines de Turing deterministes i no deterministes, respectivament.
Precisament, la tesi de Church-Turing formulada per Alan Turing i Alonzo Church, de forma independent a mitjan caracteritza la noció informal de computabilitat amb la computació mitjançant una màquina de Turing.
La idea subjacent és el concepte que una màquina de Turing pot veure com un autòmat executant un procediment efectiu definit formalment, on l'espai de memòria de treball és il·limitat, però en un moment determinat només una part finita accessible.
Descripció miniatura|Diagrama artístic d'una màquina de Turing. La màquina de Turing modela matemàticament una màquina que opera mecànicament sobre una cinta. En aquesta cinta hi ha símbols que la màquina pot llegir i escriure, un alhora, per això fa servir un capçal lector / escriptor de cinta. L'operació està completament determinada per un conjunt finit 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 a 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'article original «On computable numbers…» (‘Sobre nombres computables’), Turing no s'imagina un mecanisme, sinó una persona que anomena l'«ordinador», és-a-dor, una persona qui fa orde, qui executa servilment aquestes regles mecàniques deterministes (o com Turing posa, «d'una manera desganada»).
Més precisament, una màquina de Turing consta de: Una cinta que es divideix en cel·les, una al costat de l'altra. Cada cel·la conté un símbol d'algun alfabet finit. L'alfabet conté un símbol especial anomenat blanc (aquí escrit com 'B') i un o més símbols addicionals. La cinta és arbitràriament extensible cap a l'esquerra i cap a la dreta, és a dir, la màquina de Turing sempre és subministrada amb tanta cinta com necessiti per a la computació. Les cel·les que no s'hagin escrit prèviament s'assumeixen que estan farcides amb el símbol blanc. En alguns models la cinta té un extrem esquerre marcat amb un símbol especial; la cinta s'estén o és indefinidament extensible a la dreta. Un capçal que pot llegir i escriure símbols en la cinta i moure la cinta a l'esquerra i a la dreta una (i només una) cel·la alhora. En alguns models el capçal es mou i la cinta és estacionària. Un registre d'estat que emmagatzema l'estat de la màquina de Turing, un dels estats finits. Hi ha un estat inicial especial amb el qual el registre d'estat s'inicia. Turing escriu que aquests estats reemplacen l'«estat de la ment» en què ordinàriament seria una persona que fa els càlculs. Una taula finita d'instruccions (anomenada ocasionalment com a taula d'acció o funció de transició). Les instruccions són usualment 5-tuples: qiaj → qi1aj1dk, (de vegades 4-tuples), que, donat l'estat (qi) en què la màquina es troba actualment i el símbol (aj) que s'està llegint a la cinta (el símbol actualment sota del capçal) li indica a la màquina fer el següent en seqüència (per als models de 5-tupla): Esborra o escriu un símbol Mou el capçal Asumeix el mateix o un nou estat como preescrit. En els models de 4-tupla, són especificades com instruccions separades: esborrar o escriure un símbol (AJ1) i moure el capçal a l'esquerra o la dreta (dk). Específicament, la taula indica a la màquina: (ia) esborrar o escriure un símbol o (ib) moure el capçal a l'esquerra o a la dreta, i després (ii) assumir el mateix o un nou estat, però no les dues accions (ia) i (ib) en la mateixa instrucció. En alguns models, si no hi ha entrades a la taula per a l'actual combinació de símbol i estat, la màquina s'aturarà; altres models requereixen que estiguin plenes totes les entrades. Noti que cada part de la màquina - el seu estat i col·leccions de símbols - i les seves accions - imprimir, esborrar, moviment de la cinta - és finit, discret i distingible; és la quantitat potencialment il·limitada de cinta el que li dona una quantitat il·limitada d'espai d'emmagatzematge. Les operacions que es poden realitzar en aquesta màquina es limiten a:
avançar el capçal lector/escriptor cap a la dreta; avançar el capçal lector/escriptor cap a l'esquerra;
El còmput és determinat a partir d'una taula d'estats de la forma:
(estat, valor) (\nou estat, \nou valor, direcció)
Aquesta taula pren com a paràmetre l'estat actual de la màquina i el caràcter llegit de la cinta, donant la direcció per a moure el capçal, el nou estat de la màquina i el valor a ser escrit en la cinta. Amb aquest aparell extremadament senzill és possible realitzar qualsevol còmput que un computador digital sigui capaç de fer.
Mitjançant aquest model teòric i l'anàlisi de complexitat d'algorismes, va ser possible categoritzar problemes computacionals d'acord amb el seu comportament. Així apareixen el conjunt de problemes denominats P i NP, les solucions dels quals en temps polinòmic són trobades segons el determinisme i no determinisme respectivament de la màquina de Turing.
De fet, es pot provar matemàticament que per a qualsevol programa de computador és possible crear una màquina de Turing equivalent. Aquesta prova resulta de la Tesi de Church-Turing, formulada per Alan Turing i Alonzo Church de forma independent a mitjans del .
La idea subjacent en el concepte de màquina de Turing és una persona executant un procediment efectiu definit formalment, on l'espai de memòria de treball és il·limitat, però en un moment determinat només una part finita és accessible. La memòria es divideix en espais de treball denominades cel·les, on es pot llegir i escriure símbols. Inicialment totes les cel·les contenen un símbol especial denominat «blanc». Les instruccions que determinen el funcionament de la màquina tenen la forma, «si som en l'estat x, llegint la posició y, on hi ha escrit el símbol z, llavors aquest símbol ha de ser reemplaçat per aquest altre símbol, i passar a llegir la cel·la següent, bé a l'esquerra bé a la dreta».
La màquina de Turing pot considerar-se com un autòmat capaç de reconèixer llenguatges formals. En aquest sentit, és capaç de reconèixer els llenguatges recursivament enumerables, d'acord amb la jerarquia de Chomsky. Per tant, té una potència superior a altres autòmats, com l'autòmat finit, o l'autòmat amb pila, o igual a altres models amb la mateixa potència computacional.
Definició Una màquina de Turing Teoría de Autómatas, RAI 2012 Universidad Carlos III és un model computacional que realitza una lectura / escriptura de manera automàtica sobre una entrada anomenada cinta, generant una sortida en aquesta mateixa.
Aquest model està format per un alfabet d'entrada i un de sortida, un símbol especial anomenat blanc, un conjunt d'estats finits i un conjunt de transicions entre aquests estats. El seu funcionament es basa en una funció de transició, que rep un estat inicial i una cadena de caràcters (la cinta, la qual pot ser infinita) pertanyents a l'alfabet d'entrada. La màquina va llegint una cel·la de la cinta a cada pas, esborrant el símbol en què es troba posicionat seu capçal i escrivint un nou símbol que pertany a l'alfabet de sortida, per després desplaçar el capçal a l'esquerra o a la dreta (només una cel·la alhora). Això es repeteix segons s'indiqui en la funció de transició, per finalment aturar-se en un estat final o d'acceptació, representant així la sortida.
Una màquina de Turing amb una sola cinta pot ser definida com una 7-tupla: miniatura|Màquina de Turing on s'aprecia el capçal i la cinta que es llegeix. , on:
és un conjunt finit d'estats és un conjunt finits de símbols de cinta, l'alfabet de cinta és l'estat inicial és un símbol denominat blanc, i és l'únic símbol que es pot repetir un nombre infinit de cops és el conjunt d'estats finals d'acceptació és una funció parcial denominada funció de transició, on L és un moviment a l'esquerra i R és el moviment a la dreta.
Existeix a la literatura un abundant nombre de definicions alternatives, però totes elles tenen el mateix poder computacional, per exemple es pot afegir el símbol S com símbol de "no moviment" en un pas de còmput.
Funcionament La màquina de Turing consta d'un capçal lector / escriptor i una cinta infinita en la qual el capçal llegeix el contingut, esborra el contingut anterior i escriu un nou valor. Les operacions que es poden realitzar en aquesta màquina es limiten a:
Moure el capçal lector / escriptor cap a la dreta. Moure el capçal lector / escriptor cap a l'esquerra. miniatura El còmput es determina a partir d'una taula d'estats de la forma:
(estat, valor) (nou estat, nou valor, direcció)