About: Post–Turing machine

An Entity of Type: Person100007846, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

A Post–Turing machine is a "program formulation" of a type of Turing machine, comprising a variant of Emil Post's Turing-equivalent model of computation. Post's model and Turing's model, though very similar to one another, were developed independently. Turing's paper was received for publication in May 1936, followed by Post's in October. A Post–Turing machine uses a binary alphabet, an infinite sequence of binary storage locations, and a primitive programming language with instructions for bi-directional movement among the storage locations and alteration of their contents one at a time. The names "Post–Turing program" and "Post–Turing machine" were used by Martin Davis in 1973–1974 (Davis 1973, p. 69ff). Later in 1980, Davis used the name "Turing–Post program" (Davis, in Steen p. 241).

thumbnail
Property Value
dbo:abstract
  • A Post–Turing machine is a "program formulation" of a type of Turing machine, comprising a variant of Emil Post's Turing-equivalent model of computation. Post's model and Turing's model, though very similar to one another, were developed independently. Turing's paper was received for publication in May 1936, followed by Post's in October. A Post–Turing machine uses a binary alphabet, an infinite sequence of binary storage locations, and a primitive programming language with instructions for bi-directional movement among the storage locations and alteration of their contents one at a time. The names "Post–Turing program" and "Post–Turing machine" were used by Martin Davis in 1973–1974 (Davis 1973, p. 69ff). Later in 1980, Davis used the name "Turing–Post program" (Davis, in Steen p. 241). (en)
dbo:thumbnail
dbo:wikiPageID
  • 3688147 (xsd:integer)
dbo:wikiPageLength
  • 22414 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1081512808 (xsd:integer)
dbo:wikiPageWikiLink
dbp:align
  • center (en)
dbp:alt
  • 2 (xsd:integer)
dbp:caption
  • The HALT instruction adds the 15th state. (en)
  • A "run" of the 2-state busy beaver with all the intermediate steps of the Post–Turing machine shown. (en)
dbp:direction
  • vertical (en)
dbp:header
  • The state diagram of a two-state busy beaver converts to the equivalent Post–Turing machine with the substitution of 7 Post–Turing instructions per "Turing" state. (en)
dbp:image
  • 2 (xsd:integer)
  • State diagram 2 state busy beaver 2.JPG (en)
dbp:width
  • 777 (xsd:integer)
dbp:wikiPageUsesTemplate
dcterms:subject
rdf:type
rdfs:comment
  • A Post–Turing machine is a "program formulation" of a type of Turing machine, comprising a variant of Emil Post's Turing-equivalent model of computation. Post's model and Turing's model, though very similar to one another, were developed independently. Turing's paper was received for publication in May 1936, followed by Post's in October. A Post–Turing machine uses a binary alphabet, an infinite sequence of binary storage locations, and a primitive programming language with instructions for bi-directional movement among the storage locations and alteration of their contents one at a time. The names "Post–Turing program" and "Post–Turing machine" were used by Martin Davis in 1973–1974 (Davis 1973, p. 69ff). Later in 1980, Davis used the name "Turing–Post program" (Davis, in Steen p. 241). (en)
rdfs:label
  • Post–Turing machine (en)
owl:sameAs
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:knownFor of
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is dbp:knownFor of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License