Turingen makina

Turing-en makina edo Turing makina makina abstraktu bat definitzen duen konputaziozko modelo matematikoa da^[1], erregela - taula baten arabera zinta tira baten gainean sinboloak manipulatzen dituena^[2]. Sinplea bada ere, Turing makina edozein konputazio-algoritmo simulatzeko^[3] egokitua izan daiteke.

Turing makina ordenagailu batek egindako datu-manipulazio guztia kontrolatzen duen prozesamendu unitate zentral (PUZ) baten adibide orokor bat da, makina kanonikoarekin datuak biltzeko memoria sekuentziala erabiliz. Zehazkiago, alfabeto baten kate baliodunen azpimultzo arbitrarioren bat zerrendatzeko gai den makina — automata — bat da. Kateak modu mugikorrean zerrendatu daitekeen multzo baten zati dira. Turing-en makinak luzera infinituko zinta bat du, non irakurtzeko eta idazteko eragiketak egin ditzakeen.

1. ↑ Minsky 1967:107 "1936 urteko artikuluan, bere izena daramaten makina abstraktuak definitu zituen. Turing makina bat egoera finituko makina bat da, ingurune mota berezi batekin lotua, bere zinta, non sinboloen sekuentziak gorde (eta gero berreskuratu) ditzakeen ", baita Stone 1972:8 non "makina" hitza komatxo artean dagoen.
2. ↑ Stone 1972:8 baieztatzen du ""Makina" hau eredu matematiko abstraktua da", ere cf. Sipser 2006: 137 "Turing makinaren modeloa" deskribatzen du. Rogers 1987 (1967): 13 "Turingen karakterizazioa" aipatzen du, Boolos Burgess eta Jeffrey 2002:25 "idealizatutako makina mota espezifiko" bat aipatzen dute.
3. ↑ Sipser 2006:137 "Turing makina batek ordenagailu erreal batek egin dezakeen guztia egin dezake".