De bekende Turing-machine is gebaseerd op een solide en op zichzelf staande wiskundige structuur met kwaliteiten voor het oplossen van wiskundige bewerkingen door middel van algoritmisch gebruik. Hoewel deze definitie zeer complex is, is de realiteit dat dit niet het geval is.
Simpel gezegd is deze machine een apparaat uit 1936 dat computergegevens oneindig kan berekenen. Zonder twijfel markeert de ontwikkeling ervan een belangrijke gebeurtenis in de geschiedenis van de computer . We kunnen er zelfs van uitgaan dat dankzij deze machine de computers die we kennen vandaag de dag bestaan.
Simpel gezegd: de Turingmachine is niet ingewikkeld. Integendeel, een van de belangrijkste kenmerken is juist de gemakkelijke uitvoering. Het maakt eenvoudigweg gebruik van symbolische representaties op een band die verschillende processen volgen. Het feit dat het eenvoudig is, betekent echter niet dat het nutteloos is. Het is precies het tegenovergestelde.
Een Turingmachine accepteert allerlei algoritmische code van verschillende computers. In die zin simuleert het naadloos de logica van computergedrag.
Deze machine dankt zijn naam aan zijn uitvinder Alan Turing van Engelse afkomst. Dit personage viel tijdens zijn leven op verschillende gebieden op. Hij blonk vooral uit als logisch genie. Op basis van het bovenstaande werd de machine aanvankelijk een “logische computermachine” genoemd.
De Turing-machine vertegenwoordigt een van de meest relevante bijdragen in de geschiedenis van de computer.
Geschiedenis van de creatie van de Turingmachine
Tegen de 19e eeuw had de wiskunde op veel gebieden aan relevantie gewonnen. Dit was echter nog steeds niet officieel gemaakt. De meeste vakexperts hebben hard gewerkt om dit vakgebied tot stand te brengen.
Het was een kwestie van het implementeren van een hypothese op een groep symbolen en methoden waarvan de realisatie de leiding zou hebben over een machine.
Alan Turing onthulde zijn Turingmachine-initiatief in 1936 . Dit gebeurde precies in de presentatie van zijn onderzoek “Over berekenbare getallen, met een toepassing op het Entscheidungsprobleem” . De publicatie uit hetzelfde jaar analyseerde David Hilberts benadering van de beslisbaarheid van de wiskunde.
Met andere woorden, de aanpak was om het bestaan van een vaste procedure te bevestigen die van toepassing is op elk wiskundig antwoord en dat deze op zijn beurt bevestigt of het resultaat waar is of niet. Op basis van het bovenstaande ontwierp Alan Turing de Turing-machine, waarmee hij bevestigde dat sommige machines verschillende algoritmen kunnen oplossen.
Tot nu toe heeft Turing een belangrijke erfenis nagelaten. Hoewel zijn werk niet gericht is op fysieke representatie, kan de relevantie ervan voor modern computerontwerp niet worden ontkend. Voor dit alles geldt dat wanneer we het gedrag van een computer observeren, we te maken krijgen met een Turing-machine.
Hoe wordt de Turingmachine gemaakt?
Een Turing-machine heeft een onbeperkt aantal tapes, onderverdeeld in beheersecties die als opslagapparaat fungeren. Bovendien heeft het een kop die codes leest en naar de tape schrijft. Aan de andere kant is ditzelfde onderdeel verantwoordelijk voor het verplaatsen van de tape van de ene ruimte naar de andere.
Het bevat ook een statuscontrolerecord en een verkorte procestabel. Deze laatste wordt ook wel de actietafel genoemd. Zoals we eerder vermeldden, werkt de Turing-machine automatisch . Om verschillende soorten algoritmen te ontcijferen, wordt het daarom beheerst door de Chomsky-hiërarchie.
- Lint : Dit lint is opgedeeld in secties en elk is overeenkomstig de ander gepositioneerd. Alle cellen hebben symbolen van een beperkte primer. De primer heeft op zijn beurt een bepaald symbool genaamd “B”. Bovendien bevat het andere aanvullende symbolen. De tape strekt zich in beide richtingen (links of rechts) uit, net zo ver als nodig is voor uw werk.
- Hoofd – Dit deel van de Turing-machine leest en genereert codes op de tape. Bovendien is het verantwoordelijk voor het verplaatsen van de tape in de overeenkomstige richting. Afhankelijk van het hoofdmodel kan deze bewegen. Als dat zo is, is de band gerepareerd.
- Status opslaan – Zoals de naam al doet vermoeden, moet u de status van het apparaat opslaan. Dit verwijst naar een beperkte staat. Bovendien is er een bepaalde inaugurele staat waarmee het register begint te werken. Alan Turing stelt dat elk van deze toestanden de ‘mentale toestand’ vervangt wanneer een individu een bepaalde wiskundige bewerking uitvoert.
- Instructietabel – In principe zorgt het voor alle aanwijzingen van de Turing-machine. Dat wil zeggen, het geeft aan wat het apparaat op een bepaald moment zou moeten doen. Verplaats bijvoorbeeld het hoofd, schrijf een symbool of verwijder het.
Hoe werkt de Turingmachine?
Een Turing-machine voert drie essentiële taken uit zodra de kop op de tape is geplaatst. Dit apparaat leest het symbool in een bepaalde cel, verandert de waarde van het symbool in een cel, of verplaatst de strip naar rechts of links om de aangrenzende cel te ontcijferen en te vervangen.
Bovendien kan elk van de waarden een gerelateerde taak hebben. Dat wil zeggen, als het gelezen symbool bijvoorbeeld overeenkomt met het getal 1, schrijft de Turing-machine 0 en verplaatst de strip naar rechts. Als het gelezen symbool echter 0 is, schrijft de machine het getal 1.
Deze taak die door de Turing-machine wordt uitgevoerd, wordt inversie genoemd. Dit betekent dat binaire waarden een inzet hebben. Zo wordt een Turing-machine geprogrammeerd om specifieke taken uit te voeren, die zeer complexe algoritmen ontcijferen. Het centrale doel van dit apparaat zijn getallen die worden berekend door wiskundige bewerkingen.
Waar wordt de Turingmachine voor gebruikt?
In feite heeft de Turing-machine door de geschiedenis heen talloze toepassingen gehad. En niet in de laatste plaats is het een revolutionaire uitvinding die de manier waarop we wiskunde zien en interpreteren heeft veranderd. Vroeger werd het bijvoorbeeld gebruikt als taalgenerator .
Er zijn echter veel toepassingen die op dit punt kunnen worden besproken. Enkele van de belangrijkste zijn:
- Theory of Computation – Deze theorie maakt deel uit van de studie van informatica en wiskunde. Het hoofddoel is de analyse van de essentiële kwaliteiten en beperkingen van computers. In het bijzonder probeert deze theorie wiskundige procedures te vinden die de mogelijkheid bieden een operatie te berekenen en te classificeren op basis van het complexiteitsniveau ervan.
- Oracle Machine : Dit is een type Turing-machine met een orakel dat vragen beantwoordt die verband houden met een specifieke numerieke symboliek.
Welke soorten Turing-machines bestaan er?
Er zijn verschillende soorten Turing-machines. Elk van hen is geboren met als doel de realisatie van algoritmische problemen te vereenvoudigen. De vijf typen worden hieronder beschreven:
- Turingmachine met verblijfsrichtlijn – Deze machine heeft een onbeperkte band die in één richting beweegt. Meestal beweegt de band naar rechts. De mobiliteit naar links is uitgeschakeld.
- Bidirectionele Turing-machine – Als een Turing-machine een onbeperkt aantal banden heeft, kan deze werken als een bidirectionele machine, maar dan met twee sporen. In dit geval wordt de informatie gelokaliseerd op basis van de lay-out van de banden, indien van toepassing.
- Multitape Turing Machine – Zoals de naam al doet vermoeden, heeft deze meerdere tapes. Het bijzondere is dat elk van hen zijn eigen hoofd heeft. Daarom werkt elk van deze onderdelen onafhankelijk. Aan de andere kant is het niet nodig dat ze in dezelfde richting of gelijktijdig bewegen.
- Multidimensionale Turing-machine : In dit geval heeft de machinestrip verschillende afmetingen. Dat wil zeggen, een tweedimensionale band die naar rechts, links, omhoog en omlaag beweegt. Afhankelijk van de toestand van de machine en het te ontsleutelen algoritme wordt de toestand gewijzigd.
- Niet-deterministische Turing-machine : Het is mogelijk om een deterministische machine te simuleren met een niet-deterministische machine en omgekeerd. In het geval van de deterministiek is deze gebaseerd op welke, voor het stripsymbool en de huidige status, bestaat uit een beperkt aantal getallen om uit te kiezen.
Wat zijn de voordelen van de Turingmachine?
Een van de belangrijkste voordelen van dit type machine, vergeleken met andere, is dat de taal vrij uitgebreid is. Aan de andere kant kan het algoritme worden geautoriseerd of geweigerd zonder dat het volledig opnieuw hoeft te worden gelezen. De bewerkingen worden hoe dan ook berekend als het om een Turing-machine gaat. Bovendien is de codering ervan beslisbaar .
Deze machines vermelden of inventariseren de taal. Aan de andere kant is de autonomie die ze hebben niet vergelijkbaar met die van andere. Met dit laatste kan het tussen verschillende staten springen. Het is niet nodig om logische vergelijkingen samen te vatten, omdat het geheugen groot genoeg is.