Maŝino de Turing
El Vikipedio
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 |
[redaktu] 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.
[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 la bendon unu paŝon dekstren, aŭ movi ĝin unu paŝon maldekstren.
- Decidilo kiu prenas literon el la legilo kaj, depende de la litero, ordonas al la legilo movi la bendon 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 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.
 |
 |
 |
[redaktu] Vidu ankaŭ jenon:
- Probableca Maŝino de Turing
