Maŝinoj de Turing estas ekstreme simplaj simbol-manipulantaj aparatoj, kiuj — malgraŭ sia simpleco — povas esti adaptitaj por simuli la logikon de ajna komputilo, kiu eble povus esti foje konstruata (kvankam eble tre malefike). Ili estis priskribitaj en 1936 fare de Alan Turing. Maŝino de Turing, kiu kapablas simuli ajnan alian maŝinon de Turing, estas nomata universala maŝino de Turing (aŭ simple universala maŝino).
Historio
En 1936, responde al la demando de Godelo pri tio, kio estas komputebla, Alan Turing verkis artikolon nomitan On Computable Numbers (Pri komputeblaj nombroj), en kiu li priskribis modelon de komputilo en formo plej simpla, abstrakta kaj esenca — tia modelo estas hodiaŭ konata kiel maŝino de Turing.
Priskribo
Maŝino de Turing konsistas el tri partoj:
- Rubando, dividita en ĉelojn, por registri la demandon kaj respondon de la maŝino en la formo de vico da skribsignoj el finia alfabeto (en unu ĉelon eblas skribi unu signon).
- Legilo/skribilo por legi kaj skribi la literojn. Ĝi kapablas legi literon, skribi literon, moviĝi laŭ la rubando je unu paŝo dekstren aŭ maldekstren.
- Decidilo kiu prenas literon el la legilo kaj, depende de la litero, ordonas al la legilo moviĝi aŭ skribi aŭ legi.
Signifo
La tuto ŝajnas esti simpla, sed Turing pruvis, ke tia maŝino povas komputi ion ajn, kio estas komputebla. Fakte, ĉiu ekzistanta komputilo estas esence tia maŝino. La diversaj modernaj teĥnologioj, uzataj nun, estas nome nur rimedoj por plirapidigi aŭ pligrandskaligi la komputadon, do diferenco de grado, sed ne de speco nek de esenco nek de ebleco. Laŭ materialistoj (ekzemple Daniel Dennett), eĉ la homa cerbo estas maŝino de Turing.
Lambdokalkulo
Teorio pri tio, ke ĉiu komputebla funkcio povas esti komputata de Maŝino de Turing nomiĝas la Tezo Church-Turing. Al ĝia ekesto kontribuis Alonzo Church, alia matematikisto de tiu tempo. De li priesplorita lambdokalkulo estas ekvivalento de la Maŝino de Turing kaj oni povas pruvi, ke ankaŭ ĝi povas komputi ĉiujn komputeblajn funkciojn.