Turingen makina

Automata klaseak.

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.

Historia

Alan Turing-en argazkia, 16 urterekin.

Turing-en makina 1936an asmatu zuen Alan Turing-ek[4][5]. 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?[6] 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[7].

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[8].

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

Turing makina baten bistaratzea. Bertan burua eta irakurtzen den zinta ikusten dira.

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):
    1. Ikur bat ezabatu edo idazten du (aj aj1-rekin ordezkatuz).
    2. Burua mugitu.
    3. Egoera bera edo egoera berri bat preskribatzen da (qi1 egoerara joan).

Erreferentziak

  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".
  4. ↑ Hodges, Andrew. (2012). Alan Turing: The Enigma (The Centenary ed.). Princetongo Unibertsitateko prentsa. ISBN 978-0-691-15564-7..
  5. ↑ Ideia hori 1935. urtearen erdialdean bururatu zitzaion, M. H. A. Newmanek bere hitzaldietan egindako galdera baten ondoren: "Metodo definitu bat zegoen, edo Newmanek esan zuen bezala, enuntziatu matematiko bati aplika zekiokeen "prozesu mekaniko" bat, frogatzeko modukoa ote zen erantzuna emango zuena" (Hodges 1983:93). Turingek 1936ko maiatzaren 31n aurkeztu zion artikulua London Mathematical Societyri, bere Aktak egiteko. (Hodges 1983:112), baina 1937ko hasieran argitaratu zen eta separatak 1937ko otsailean zeuden eskuragarri. (Hodges 1983:129).
  6. ↑ Turing 1936 The Undecidable 1965: 132-134; Turingen definizioa, "Zirkularra", 119. orrialdean dago.
  7. ↑ Turing 1936 The Undecidable 1965:145
  8. ↑ Sipser 2006:137 "Turing makina batek ordenagailu erreal batek egin dezakeen guztia egin dezake. Hala ere, Turing makina batek ere ezin ditu arazo batzuk konpondu. Zentzu oso errealean, arazo hauek konputazioaren muga teorikoetatik haratago daude ".

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