Wat is Turing-volledigheid?

Turing-volledigheid is wanneer een programmeertaal de functies van een Turing-machine kan uitvoeren. Dit is een concept voor een zeer eenvoudige mechanische computer, soms beschreven als de eenvoudigste machine die als een computer kan worden beschouwd. Vrijwel alle programmeertalen die tegenwoordig worden gebruikt, en in theorie, de computers waarop ze worden uitgevoerd, hebben Turing-volledigheid.

Het concept van Turing-volledigheid komt van Alan Turing, een Britse computerwetenschapper wiens werk gecodeerde berichten tijdens de Tweede Wereldoorlog omvatte. Onder zijn werk op het gebied van informatica was de ontwikkeling van een filosofie van wat een computer eigenlijk zou kunnen doen. Dit omvatte het concept dat computers eenvoudig werken door algoritmen uit te voeren. Dat wil zeggen dat ze een vaste set regels volgen om gegevens te verwerken en op hun beurt problemen op te lossen. Dit betekent dat een computer niet "denkt" of beslissingen neemt zoals een persoon dat kan.

Om het concept te illustreren, beschreef Turing een hypothetische machine die hij een "a-machine" noemde, waarbij de "a" voor automatisch staat; anderen noemden het later de Turing-machine. De machine verwerkt een rol tape die vooruit of achteruit kan bewegen en een rij symbolen bevat. Op elk moment kan de machine één symbool verwerken en, indien nodig, wijzigen. Voor het doel van het concept kan de bandrol oneindig lang zijn, wat betekent dat het geheugen van de computer niet inherent beperkt was. Dit is een analogie voor het idee dat zodra een computer een set instructies moet volgen, de hoeveelheid gegevens waarop deze instructies kunnen worden toegepast, alleen aan fysieke limieten is onderworpen.

Ironisch genoeg hebben de meeste computers tegenwoordig geen Turing-volledigheid. Dit komt omdat ze beperkingen hebben op de beschikbare opslagruimte en dus op de gegevens die ze kunnen verwerken. Ze hebben ook fysieke beperkingen, met name dat ze uiteindelijk verslijten. Het is eigenlijk de programmeertaal die Turing-volledigheid heeft. Daarom is een computer met een dergelijk programma geen Turing-computer, maar kan deze worden gesimuleerd.

Turing-volledigheid moet niet worden verward met de Turing-test. Dit was een experiment ontworpen door Turing om te zien of computers in natuurlijke taal kunnen converseren. Het principe van de test is dat als een mens het verschil tussen een alleen-tekstgesprek met de computer en een ander mens niet kan zien, de computer de test doorstaat. Hoewel sommige computers de test hebben doorstaan ​​wanneer het bereik van gespreksonderwerpen beperkt is, heeft geen enkele dit gedaan in een onbeperkt gesprek.