Maŝino de Turing
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 simulacii ajnan alian maŝinon de Turing, estas nomata universala maŝino de Turing (aŭ simple universala maŝino).
Enhavo |
Historio [redakti]
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 [redakti]
Maŝino de Turing konsistas el tri partoj:
- Bendo por registri la demandon kaj respondon de la maŝino en la formo de literoj aŭ numeroj.
- Legilo/skribilo por legi kaj skribi la literojn. Ĝi kapablas legi literon, skribi literon, moviĝi laŭ la bendo unu paŝon dekstren, aŭ moviĝi unu paŝon maldekstren.
- Decidilo kiu prenas literon el la legilo kaj, depende de la litero, ordonas al la legilo moviĝi aŭ skribi aŭ legi.
Signifo [redakti]
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 [redakti]
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.
