Universele Turing-machine

In de wiskunde en de theoretische informatica, is een universele Turing-machine (UTM) (ook bekend als de universele rekenmachine, universele machine (UM), U-machine, U en A_TM) een Turing-machine die elke willekeurige Turing-machine op elke willekeurige input kan simuleren. De universele Turing-machine slaagt hier in essentie in door zowel de beschrijving van de te simuleren machine als de input daarvan van haar eigen tape te lezen.

Een universele Turing-machine is een Turing-machine die ${\displaystyle \langle M,w\rangle }$ als input neemt, en deze input accepteert wanneer:

• ${\displaystyle M}$ een correcte stringcodering is van een Turing-machine,
• ${\displaystyle w}$ een woord is in het alfabet van de door ${\displaystyle M}$ gecodeerde Turing-machine, en
• ${\displaystyle M}$ voor het woord ${\displaystyle w}$ stopt in de accepterende toestand

Pas wanneer ${\displaystyle \langle M,w\rangle }$ aan al deze voorwaarden voldoet stopt de universele Turingmachine in de accepterende toestand^[1]. Een formele notatie is: ${\displaystyle A_{TM}=\{\langle M,w\rangle \mid M{\text{ is een Turing-machine en }}M{\text{ accepteert }}w\}}$.

Een belangrijke observatie is dat de universele Turingmachine een herkenner is van ${\displaystyle \langle M,w\rangle }$, en dus geen beslisser. Dit is het geval omdat het mogelijk is dat M oneindig doorrekent bij input ${\displaystyle w}$ en dus nooit de afwijzende toestand bereikt. De universele Turing-machine zou dan ook nooit de afwijzende toestand berkeiken. We hebben hier te maken met het stopprobleem.

Het idee van een universele Turing-machine werd in 1936^[2] geïntroduceerd door Alan Turing. Dit model wordt door sommigen (bijvoorbeeld Martin Davis (2000)) beschouwd als de oorsprong van de stored program-computer - door John von Neumann (1946) gebruikt voor zijn "Electronic Computing Instrument" dat nu zijn naam draagt: de von Neumann-architectuur.

De alledaagse computer wordt ook wel eens een universele Turing-machine genoemd. Enerzijds is dit correct, aangezien het principe van de universele Turing-machine is dat het een arbitrair programma met arbitraire input kan uitvoeren; wat alledaagse computers praktisch gezien ook kunnen. Anderzijds heeft de theoretische universele Turing-machine een oneindig geheugen. Praktisch gezien kan wel gezegd worden dat een alledaagse computer een universele Turing-machine is, aangezien het geheugen dat de meeste computers hebben voor zeer veel problemen voldoende is, terwijl dit puur theoretisch gezien dus niet correct is.

• Martin Davis, Engines of Logic: Mathematicians and the origin of the Computer, 1e editie, 2000, New York NY, W.W. Norton & Company, ISBN 0-393-32229-7
• Alan Turing, On Computable Numbers, With an Application to the Entscheidungsproblem (zie hier), Proceedings of the London Mathematical Society, 1936, vol. 42, issue 2
• Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem: A correction, Proceedings of the London Mathematical Society, 1937, vol. 43, issue 6, blz. 544-46, herdrukt in Martin Davis red. (1965) The Undecidable, Raven Press, Hewlett NY blz. 115-154; met correcties aan Turings UTM door Emil Post cf voetnoot 11 in Davis 1965 blz. 299.