Wat Is Turingvolledigheid?

Turingvolledigheid is wanneer een programmeertaal is in staat om de functies van een Turing machine uit te voeren. Dit is een concept voor een zeer eenvoudige mechanische computer, soms beschreven als de eenvoudigste machine die kan worden beschouwd als een computer. Vrijwel alle programmeertalen in gebruik zijn, en in theorie, de computers die ze uit te voeren, hebben Turingvolledigheid.

Het concept van Turingvolledigheid komt van Alan Turing, een Brits informaticus wiens werk opgenomen ontcijferen van gecodeerde berichten tijdens de Tweede Wereldoorlog. Onder zijn werk op het computergebruik was de ontwikkeling van een filosofie van wat een computer kon eigenlijk doen. Dit omvatte het concept dat computers werken simpelweg door het uitvoeren van algoritmen. Dat wil zeggen dat zij volgen een vaste set van regels om gegevens te verwerken en op zijn beurt problemen op te lossen. Dit betekent dat een computer niet "denken" of beslissingen nemen als een persoon kan.

Om het concept te illustreren, Turing beschreef een hypothetische machine die hij een 'een-machine, "met de" a "staat voor automatische; anderen later noemde het de Turing machine. De machine zou een rol tape die terug of vooruit kon bewegen en bevatte een lijn van symbolen te verwerken. Op elk moment de machine één symbool te verwerken en, eventueel, aan veranderen. Voor de toepassing van het concept, kan de haspel van de tape oneindig lang zijn, waardoor het geheugen van de computer niet inherent beperkt. Dit is een analogie voor het idee dat zodra een computer heeft een reeks instructies te volgen, de hoeveelheid data kan deze instructies gelden voor alleen afhankelijk is van fysieke grenzen.

Ironisch genoeg hebben de meeste computers tegenwoordig niet echt Turingvolledigheid. Dit is omdat ze beperkingen op de beschikbare opslagruimte en dus de gegevens kunnen verwerken. Ze hebben ook fysieke beperkingen, met name dat uiteindelijk zullen ze slijten. Het is eigenlijk de programmeertaal die Turingvolledigheid heeft. Hierdoor een computer met een dergelijk programma geen Turing computer, maar kan worden gebruikt om één simuleren.

Turingvolledigheid moet niet worden verward met de Turing-test. Dit was een experiment ontworpen door Turing om te zien of computers kunnen converseren in natuurlijke taal. Het principe van de test is dat als een mens het verschil tussen alleen tekst gesprek met de computer en een ander mens niet kan zeggen, de computer de test doorstaat. Terwijl sommige computers zijn geslaagd voor de test als het bereik van gespreksonderwerpen beperkt is, hebben niets gedaan in onbeperkte gesprek.