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 en U) 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.

Het idee van een universele Turing-machine werd in 1936-37 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.

ReferentiesBewerken

  • 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.