Gaan na inhoud

Turingmasjien

in Wikipedia, die vrye ensiklopedie
'n Fisiese Turingmasjienmodel gebou deur Mike Davey. 'n Ware Turingmasjien sal meer geheue (band) benodig indien en wanneer nodig; fisiese modelle kan slegs 'n eindige hoeveelheid hê.

'n Turingmasjien is 'n wiskundige berekeningsmodel wat 'n abstrakte masjien beskryf.[1] In sy 1936-artikel het A. M. Turing die klas abstrakte masjiene gedefinieer wat nou sy naam dra. 'n Turing-masjien is 'n eindtoestandmasjien wat geassosieer word met 'n spesiale soort omgewing – sy band – waarin dit reekse simbole kan stoor (en later herstel),[2] wat simbole op 'n strook band manipuleer volgens 'n tabel met reëls.[3] Ten spyte van die model se eenvoud, is dit in staat om enige rekenaaralgoritme te implementeer.[4]

Die masjien werk op 'n oneindige[5] geheueband verdeel in diskrete selle,[6] wat elk 'n enkele simbool kan bevat wat getrek word uit 'n eindige stel simbole, genaamd die alfabet van die masjien. Dit het 'n "kop" wat op enige punt in die masjien se werking oor een van hierdie selle geplaas is, en 'n "toestand" gekies uit 'n eindige stel toestande. By elke stap van sy werking lees die kop die simbool in sy sel. Dan, gebaseer op die simbool en die masjien se eie huidige toestand, skryf die masjien 'n simbool in dieselfde sel, en beweeg die kop een stap na links of regs,[7] of stop die berekening. Die keuse van watter vervangingsimbool om te skryf, watter rigting om die kop te beweeg, en of om te stop, is gebaseer op 'n eindige tabel wat spesifiseer wat om te doen vir elke kombinasie van die huidige toestand en die simbool wat gelees word. Soos met 'n regte rekenaarprogram, is dit moontlik vir 'n Turing-masjien om in 'n oneindige lus te gaan wat nooit sal stop nie.

Die Turingmasjien is in 1936 deur Alan Turing uitgevind,[8][12] wat dit 'n "a-masjien" (outomatiese masjien) genoem het.[13] Dit was Turing se doktorale adviseur, Alonzo Church, wat later die term "Turing-masjien" in 'n oorsig geskep het.[14] Met hierdie model kon Turing twee vrae negatief beantwoord:

  • Bestaan daar 'n masjien wat kan bepaal of enige arbitrêre masjien op sy band "sirkelvormig" is (bv. vries, of versuim om sy berekeningstaak voort te sit)?
  • Bestaan daar 'n masjien wat kan bepaal of enige arbitrêre masjien op sy band ooit 'n gegewe simbool druk? [15][16]

Deur 'n wiskundige beskrywing van 'n baie eenvoudige toestel te verskaf wat arbitrêre berekeninge kan uitvoer, kon hy dus eienskappe van berekening in die algemeen bewys – en in die besonder die onberekenbaarheid van die Entscheidungsproblem, of ' beslisbaarheidsprobleem ' (of elke wiskundige stelling bewysbaar of weerlêbaar is).[17]

Turingmasjiene het die bestaan van fundamentele beperkings op die krag van meganiese berekening bewys.[4]

Alhoewel hulle arbitrêre berekeninge kan uitdruk, maak hul minimalistiese ontwerp hulle te stadig vir berekening in die praktyk: werklike rekenaars is gebaseer op verskillende ontwerpe wat, anders as Turingmasjiene, ewetoeganggeheue gebruik.

Turing-volledigheid is die vermoë van 'n berekeningsmodel of 'n instruksiestelsel om 'n Turingmasjien te simuleer. 'n Programmeertaal wat Turing-volledig is, is teoreties in staat om alle take uit te druk wat deur rekenaars uitgevoer kan word; byna alle programmeertale is Turing-volledig as die beperkings van eindige geheue geïgnoreer word.

Oorsig

[wysig | wysig bron]
Klasse van outomatiese masjiene.

'n Turingmasjien is 'n geïdealiseerde model van 'n sentrale verwerkingseenheid (SVE) wat alle datamanipulasie wat deur 'n rekenaar gedoen word, beheer, met die kanonieke masjien wat opeenvolgende geheue gebruik om data te stoor. Tipies word die opeenvolgende geheue voorgestel as 'n band van oneindige lengte waarop die masjien lees- en skryfbewerkings kan uitvoer.

In die konteks van formele taalteorie is 'n Turingmasjien (outomaat) in staat om 'n arbitrêre deelversameling van geldige stringe van 'n alfabet op te som. 'n Stel stringe wat op hierdie manier opgesom kan word, word 'n rekursief opsombare taal genoem. Die Turingmasjien kan ekwivalent gedefinieer word as 'n model wat geldige invoerstringe herken, eerder as om uitvoerstringe op te som.

Gegewe 'n Turingmasjien M en 'n arbitrêre string s, is dit oor die algemeen nie moontlik om te besluit of M uiteindelik s sal produseer nie. Dit is as gevolg van die feit dat die stilstandprobleem onoplosbaar is, wat groot implikasies het vir die teoretiese beperkings van berekening.

'n Turingmasjien wat enige ander Turingmasjien kan simuleer, word 'n universele Turingmasjien (UTM, of bloot 'n universele masjien) genoem. Nog 'n wiskundige formalisme, lambda-kalkulus, met 'n soortgelyke "universele" aard is deur Alonzo Church bekendgestel. Church se werk het met Turing s'n verweef om die basis te vorm vir die Church-Turing-tesis. Hierdie tesis verklaar dat Turingmasjiene, lambda-kalkulus en ander soortgelyke formalismes van berekening inderdaad die informele idee van effektiewe metodes in logika en wiskunde vasvang en dus 'n model bied waardeur 'n mens op 'n wiskundig presiese manier oor 'n algoritme of "meganiese prosedure" kan redeneer sonder om aan enige spesifieke formalisme gebonde te wees. Die bestudering van die abstrakte eienskappe van Turingmasjiene het baie insigte in rekenaarwetenskap, berekenbaarheidsteorie en kompleksiteitsteorie opgelewer.

Evaluasie

[wysig | wysig bron]
Illustrasie van 'n Turingmasjien deur KI gegenereer.

Die Turingmasjien is een van die mees invloedryke konseptuele gereedskappe in die geskiedenis van rekenaarkunde. Toe dit is in 1936 deur Alan Turing bekendgestel is was dit nie bedoel as 'n praktiese toestel nie, maar as 'n gedagte-eksperiment om te verduidelik wat dit beteken dat 'n berekening meganies uitgevoer word. Die model is doelbewus eenvoudig: dit verbeel 'n toestel wat simbole op 'n eindelose strook papier lees en skryf, volgens 'n vaste stel reëls. Vanuit hierdie beskeie opstelling het Turing gedemonstreer dat so 'n masjien in beginsel enige berekening kan uitvoer wat as 'n reeks logiese stappe beskryf kan word.

Die belangrikheid van die Turing-masjien lê in die manier waarop dit 'n presiese definisie van berekening verskaf het. Voor Turing se werk was daar geen universeel aanvaarde manier om te beskryf wat as 'n "berekenbare" proses getel word nie. Sy model het getoon dat alledaagse begrippe soos berekening, prosedure en algoritme op 'n ferm teoretiese grondslag geplaas kon word. Moderne rekenaars, ten spyte van hul spoed en kompleksiteit, oorskry nie die logiese vermoëns van 'n Turingmasjien nie; hulle implementeer bloot dieselfde basiese idees in fisiese vorm. Om hierdie rede word die Turingmasjien dikwels beskou as die konseptuele voorouer van die digitale rekenaar.

Net so betekenisvol was Turing se demonstrasie dat daar perke is aan wat masjiene kan doen. Deur sy eie model te analiseer, het hy bewys dat sommige probleme nie deur enige algoritme opgelos kan word nie, ongeag hoeveel tyd of geheue beskikbaar is. Hierdie insig het wiskunde, logika en rekenaarwetenskap hervorm deur te onthul dat die krag van berekening enorm is, maar nie onbeperk nie.

Oor die algemeen word die Turingmasjien minder waardeer as 'n bloudruk vir werklike hardeware en meer as 'n fundamentele teorie. Dit het die aard van berekening verduidelik, die intellektuele grondslag vir rekenaarwetenskap gelê en die inherente beperkings van gemeganiseerde redenasie onthul. Die eenvoud en diepte daarvan verseker dat dit 'n sentrale konsep bly in besprekings van logika, wiskunde en kunsmatige intelligensie.

Sien ook

[wysig | wysig bron]

Verwysings

[wysig | wysig bron]
  1. ↑ Minsky (1967, p. 107)
  2. ↑ Stone (1972, p. 8)
  3. ↑ Stone (1972, p. 8) stel: "Hierdie "masjien" is 'n abstrakte wiskundige model", vgl. ook.Sipser (2012, p. 165ff) wat die Turingmasjienmodel beskryf.Rogers (1987, p. 13) verwys na "Turing se karakterisering",Boolos, Burgess & Jeffrey (2002, p. 25) verwys na 'n "spesifieke soort geïdealiseerde masjien".
  4. 1 2 Sipser (2012, p. 165) observes that "[a] Die Turingmasjien kan alles doen wat 'n regte rekenaar kan doen. Nietemin kan selfs 'n Turingmasjien nie sekere probleme oplos nie. In 'n baie werklike sin is hierdie probleme buite die teoretiese perke van berekening."
  5. ↑ Cf.Sipser (2012, p. 165). Also, Rogers (1987, p. 13) beskryf "'n papierband van oneindige lengte in beide rigtings". Minsky (1967, p. 118) lui "Die band word as oneindig in beide rigtings beskou".Boolos, Burgess & Jeffrey (2002, p. 25) sluit die moontlikheid in dat "daar iemand aan elke kant gestasioneer is om ekstra leë blokkies by te voeg soos nodig".
  6. ↑ Cf. Rogers (1987, p. 13). Ander outeurs gebruik die woord "vierkant" e.g. Boolos, Burgess & Jeffrey (2002, p. 35), Minsky (1967, p. 117), Penrose (1989, p. 37).
  7. ↑ Boolos, Burgess & Jeffrey (2002, p. 25) illustreer die masjien soos dit langs die band beweeg.Penrose (1989, pp. 36–37) beskryf homself as "ongemaklik" met 'n oneindige band en merk op dat dit "moeilik kan wees om te skuif!"; hy "verkies om aan die band te dink as 'n voorstelling van 'n eksterne omgewing waardeur ons eindige toestel kan beweeg" en nadat hy opgemerk het dat die "'beweging' 'n gerieflike manier is om dinge voor te stel" en stel dan voor dat "die toestel al sy insette van hierdie omgewing ontvang. Sommige variasies van die Turing-masjienmodel laat ook die kop toe om in dieselfde posisie te bly in plaas daarvan om te beweeg of te stop.
  8. ↑ Hodges 2012.
  9. ↑ Hodges 1983, p. 93.
  10. ↑ Hodges 1983, p. 112.
  11. ↑ Hodges 1983, p. 129.
  12. ↑ Die idee het hom in die middel van 1935 opgekom (sien miskien meer in die Geskiedenis-afdeling) na 'n vraag wat M. H. A. Newman in sy lesings gestel het: "Was daar 'n definitiewe metode, of soos Newman dit gestel het, 'n "meganiese proses" wat op 'n wiskundige stelling toegepas kon word, en wat die antwoord sou gee of dit bewysbaar was".[9] Turing het sy referaat op 31 Mei 1936 by die London Mathematical Society ingedien vir sy Proceedings,[10] maar dit is vroeg in 1937 gepubliseer en afdrukke was in Februarie 1937 beskikbaar.[11]
  13. ↑ Sien voetnota in Davis (2000, p. 151)
  14. ↑ Sien nota in voorwoord Tyler & Emderton (2019)
  15. ↑ Turing 1936 in Davis (2004, pp. 132–134); Turing's definition of "circular" is found on page 119.
  16. ↑ Turing 1936, pp. 230–265.
  17. ↑ Turing 1936 in Davis (2004, p. 145)

Eksterne skakels

[wysig | wysig bron]
Ontsluit van "https://af.wikipedia.org/w/index.php?title=Turingmasjien&oldid=2873204"