Maŝino de Turing
El Vikipedio
Maŝinoj de Turing estas ekstreme simplaj simbol-manipulantaj aparatoj kiuj — malgraŭ ilia simpleco — povas esti adaptitaj por simuli la logikon de ajna komputilo kiu eble povus esti foje konstruata. Ili estis priskribitaj en 1936 fare de Alan Turing. Maŝino de Turing kiu kapablas similuacii ajnan alian maŝinon de Turing estas nomata universala maŝino de Turing (aŭ simple universala maŝino).
Enhavo |
[redaktu] Historio
En 1936, respondinte 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.
[redaktu] Priskribo
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 por legi kaj skribi la literojn. Ĝi kapablas legi literon, skribi literon, moviĝi unu paŝon dekstren sur la bendo, 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.
[redaktu] 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 nome estas 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.
[redaktu] Lambdokalkulo
Teorio pri tio, ke ĉiu komputebla funkcio povas esti komputita 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.
[redaktu] Vidu ankaŭ jenon:
- Maŝino de Turing
- Probableca Maŝino de Turing

