Turingen makina

Turing-en makina edo Turing makina makina abstraktu bat definitzen duen konputaziozko modelo matematikoa da, erregela - taula baten arabera zinta tira baten gainean sinboloak manipulatzen dituena. Sinplea bada ere, Turing makina edozein konputazio-algoritmo simulatzeko 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.

Historia 

Turing-en makina 1936an asmatu zuen Alan Turing-ek. Eredu horrekin, teoriko britainiarra gai izan zen bi galderari erantzuteko: ba al dago makinaren bat beste makina arbitrario batek bere zintan "zirkularra" den ala ez zehaztu dezakeena? Eta ba al dago makina bat beste makina arbitrario batek bere zintan inoiz sinbolo jakin bat inprimatu duen ala ez determinatzeko gai dena? Honela, kalkulu arbitrarioak egiteko gai den gailu sinple baten deskribapen matematiko bat ematean, konputazioaren propietateak orokorrean eta, bereziki, Entscheidungsproblem-aren konputaezintasuna frogatu ahal izan zituen.

Turingen makinari esker konputazio mekanikoaren potentzian oinarrizko mugak zeudela frogatzeko gai izan zen Alan Turing, eta makina batek konpondu ezin zituen arazoak zeudela egiaztatu zuen.

Gaur egun, kontagailu, erregistro, ausazko sarbide makinak eta Turingen makina dira oraindik ere konputazioaren teoriari buruzko gaiak ikertzen dituzten teorikoek aukeratzen dituzten modeloak. Bereziki, konplexutasun konputazionalaren teoriak Turingen makina erabiltzen du.

Jatorrian, Alan Turing matematikari ingelesak definitu zuen "makina automatiko" gisan 1936an, Proceedings of London Mathematical Society,  aldizkarian. Turing makina ez dago diseinatua konputazio-teknologia praktiko modura, baizik eta, konputazio-makina adierazten duen gailu hipotetiko modura. Turing makinak laguntzen die zientzialariei kalkulu mekanikoaren mugak ulertzen.

Turingek esperimentuaren definizio laburra eman zuen 1948ko "Makina adimendun" saiakeran. 1936ko bere argitalpena aipatuz, Turingek idatzi zuen Turing makina, hemen logika-konputazioko makina deitua, honakoa zela:

Deskribapena 

Turingen makinak zinta baten gainean mekanikoki lan egiten duen makina bat modelatzen du matematikoki. Zinta honetan makinak irakurri eta idatz ditzakeen ikurrak daude, ekintza bakarra aldi berean, zintak irakurle/idazle buru bat erabiliz. Eragiketa erabat determinatuta dago instrukzio elementalen multzo finitu baten bidez, hala nola, "42. egoeran, ikusitako sinboloa 0 bada, 1 idatzi; ikusitako sinboloa 1 bada, 17. egoerara aldatu; 17. egoeran ikusitako sinboloa 0 bada, 1 idatzi eta 6. egoerara aldatu; etab.".

Turing makina batek honako atal hauek ditu:

 Zinta bat, bata bestearen ondoan dauden gelaxketan banatzen dena. Gelaxka bakoitzak alfabeto finitu baten ikur bat dauka. Suposatzen da zinta arbitrarioki hedagarria dela, hau da, beti izango du konputatzeko behar duen beste zinta.
 Buru bat, zintan ikurrak irakurri eta idatz ditzakeena eta aldi berean zinta ezkerretara eta eskuinetara gelaxka bat aldi berean mugi dezakeena.
 Egoera-erregistro bat, Turingeko makinaren egoera gordetzen duena. Hasierako egoera berezi batekin hasten da egoera-erregistroa.
 Instrukzio-taula finitu bat, makinaren egoera (qi) eta zintan irakurtzen ari den sinboloa (aj) kontuan hartuta (buru azpian dagoena), makinari sekuentzian honako hau egitea adierazten diona (5-tuplako modeloetarako):
 Ikur bat ezabatu edo idazten du (aj aj1-rekin ordezkatuz).
 Burua mugitu.
 Egoera bera edo egoera berri bat preskribatzen da (qi1 egoerara joan).

Erreferentziak

Bibliografia 

 Hodges, Andrew (1983). Alan Turing: The Enigma. Erresuma Batua: Burnett Books/Hutchinson. ISBN 0-671-49207-1.
 Minsky, Marvin (1967). «Unsolvability of the Halting Problem». Computation: Finite and Infinite Machines. NJ: Prentice–Hall, Inc.
 Turing, A.M. (1936). «On Computable Numbers, with an Application to the Entscheidungsproblem». Proceedings of the London Mathematical Society. 2 (1937) 42: 230-265.
 Turing, A.M. (1938). «On Computable Numbers, with an Application to the Entscheidungsproblem: A correction». Proceedings of the London Mathematical Society. 2 (1937) 43 (6): 544-6.

Kanpo estekak 

Informatika
Ingalaterrako asmakizunak
Konputazio ereduak
Programazio hizkuntzen gaiak
Konputagarritasuna
1936 zientzian
1936