Màquina de Turing



Alan M. Turing

Procediment «mecànic» idealitzat, això és, procediment que seguiria una màquina ideal, descompost en les seves parts elementals i inventat pel matemàtic anglès Alan Turing (1912-1954) com a resposta a l'anomenat problema de decisió, proposat en 1900 per David Hilbert, al Congrés nacional de matemàtics a París. Aquest problema plantejava si era possible trobar un procediment algorítmic, o un procediment mecànic, que resolgués, en principi, tots els problemes de matemàtiques. Turing va dissenyar (1937) aquesta màquina ideal com un dispositiu constituït per un autòmat i una cinta (potencialment) infinita, dividida en caselles amb símbols o en blanc, i un dispositiu capaç de llegir el contingut de cada casella, esborrar o imprimir símbols, i de desplaçar-se cap a endavant o enrere (o esquerra i dreta), de manera que, efectuats tots els càlculs, la màquina es parés i donés el resultat final. El resultat al fet que va arribar, més o menys al mateix temps que Alonzo Church, que havia treballat en el mateix problema d'Hilbert de forma independent, és que: 1) una màquina de Turing és un algorisme; 2) si una màquina de Turing resol un problema és que aquest és computable; 3) no existeix un algorisme general per a tot problema matemàtic o, el que és el mateix, no per a tot problema la màquina de Turing es per, o no tot problema és computable. Si a aquestes conclusions s'hi afegeix que la ment humana pot considerar-se una màquina de Turing, tenim la denominada tesi de Church-Turing.

Es denomina «màquina universal de Turing» a la màquina de Turing capaç de solucionar tot problema computable. Els computadors digitals actuals es consideren màquines d'aquest tipus.