Turingen makina
From Wikipedia, the free encyclopedia
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.