Màquina de Turing
De Viquipèdia
La màquina de Turing és un model computacional introduït per Alan Turing en el treball "On computable numbers, with an application to the Entscheidungsproblem", publicat per la Societat Matemàtica de Londres, en el qual s'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 ens digui si és certa o no. Turing va construir un model formal de computador, la màquina de Turing, i va demostrar que existien problemes que una màquina no podia resoldre. La màquina de Turing és un model matemàtic abstracte que formalitza el concepte d'algoritme.
Taula de continguts |
[edita] Descripció
La màquina de Turing consta d'un capçal lector/escriptor i una cinta infinita en la que el capçal llegix el contingut, esborra el contingut anterior i escriu un nou valor. 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 realitzar.
Mitjançant aquest model teòric i l'anàlisi de complexitat d'algoritmes, va ser possible la categorització de problemes computacionals d'acord al seu comportament, apareixent així, 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 Tesis de Church-Turing, formulada per Alan Turing i Alenzo Church de forma independent a mitjans del segle XX.
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 estem 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 a la jerarquia de Chomsky. La seva potència és, per tant, superior a d'altres tipus d'autòmats, com l'autòmat finit, o l'autòmat amb pila, o igual a d'altres models amb la mateixa potència computacional.
[edita] Definició
Una màquina de Turing amb una sola cinta pot ser definida com una 6-tupla M = (Q,Γ,s,b,F,δ), on
- Q é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'aceptació
é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.
[edita] Màquines de Turing deterministes i no deterministes
L'entrada d'una Màquina de Turing ve determinada per l'estat actual i el símbol llegit, sent el canvi d'estat, l'escriptura d'un nou símbol i el moviment les accions ha prendre en funció d'una entrada. En el cas de que per a cada parell d'estat i símbol possible existeixi com a molt un possibilitat d'execució, direm que és una màquina de Turing determinista, mentre que en el cas que existeixin almenys un parell (estat, símbol) amb més d'una possible combinació d'actuacions direm que es tracta d'una màquina de Turing No Determinista.
La funció de transició δ en el cas no determinista queda definida com segueix: 
La capacitat de còmput d'ambdues màquines és equivalent; es pot demostrar que donada una màquina de Turing no determinista existeix una màquina de Turing determinista equivalent, en el sentit que reconeixen el mateix llenguatge, i viceversa. No obstant, la velocitat d'execució d'ambdós formalismes no és la mateixa, doncs una màquina determinista M reconeix una certa paraula de mida n en un temps O(t(n)), la màquina determinista equivalent reconeixerà la mateixa paraula en un temps O(2t(n)). És a dir, el no determinisme permetrà reduir la complexitat temporal de la solució dels problemes, permetent resoldre, per exemple, problemes de complexitat exponencial en un temps polinòmic.
[edita] Màquina Universal de Turing
Una màquina de Turing computa una determinada funció parcial de caràcter definit i unívoca, definida sobre les seqüències de possibles cadenes de símbols del seu alfabet. En aquest sentit es pot considerar com equivalent a un programa d'ordinador, o el que és el mateix, a un algorisme. No obstant, és possible realitzar una codificació de la taula que representa a una màquina de Turing com una seqüència de símbols en un determinat alfabet; per això, podem construir una màquina de Turing que accepti com entrada la taula que representa a una altra màquina de Turing i que simuli el seu comportament.
L'any 1947, Turing va indicar:
Es pot demostrar que és possible construir una màquina especial d'aquest tipus que pugui realitzar el treball de totes les demès. Es podria fer que treballés com a model d'altres màquines . Aquesta màquina especial es pot denominar màquina universal.
Aquesta fou possiblement, la idea germinal del concepte de Sistema Operatiu, un programa que pot executar altres programes i controlar-los, demostrant la seva existència i obrint camí per la seva construcció real.
Amb aquesta codificació de taules com a cadenes, s'obre la possibilitat de que una màquina de Turing es comporti com altres màquines de Turing. No obstant, moltes de les seves possibilitats són indecidibles, doncs no admeten una solució algorísmica. Per exemple, un interessant problema és determinar si una màquina de Turing qualsevol pararà en un temps finit sobre una determinada entrada; aquest problema és conegut com el problema de la parada, i que Turing va demostrar que era indecidible. En general, es pot demostrar que qualsevol qüestió no trivial sobre el comportament o la sortida d'una màquina de Turing és un problema indecidible.
