Turingmasjien

duimnael|'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. 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), wat simbole op 'n strook band manipuleer volgens 'n tabel met reëls. Ten spyte van die model se eenvoud, is dit in staat om enige rekenaaralgoritme te implementeer. geheueband verdeel in diskrete selle, 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, 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, wat dit 'n "a-masjien" (outomatiese masjien) genoem het. Dit was Turing se doktorale adviseur, Alonzo Church, wat later die term "Turing-masjien" in 'n oorsig geskep het. 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? 

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).

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

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 
duimnael|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 
duimnael|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 
* Gedagtemodel

## Verwysings 
## Eksterne skakels 
* Reuleaux-versameling van meganismes en masjiene aan die Cornell-universiteit