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 ATM) 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 als input neemt, en deze input accepteert wanneer: * een correcte is van een Turing-machine, * een woord is in het alfabet van de door gecodeerde Turing-machine, en * voor het woord stopt in de accepterende toestand Pas wanneer aan al deze voorwaarden voldoet stopt de universele Turingmachine in de accepterende toestand. Een formele notatie is: . Een belangrijke observatie is dat de universele Turingmachine een herkenner is van , en dus geen beslisser. Dit is het geval omdat het mogelijk is dat M oneindig doorrekent bij input 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 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.