The Solvability of the Halting Problem for 2-State Post Machines

DOI10.1145/321420.321426MaRDI QIDQ5546787zbMATH OpenOpenAlexFDO

Authors Stål Aanderaa, Patrick C. Fischer

Publication date 1967

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/321420.321426

zbMATH Keywords

recursion theory, constructive mathematics

Cited in

(3)

• The complexity of small universal Turing machines: A survey
• Complexity of algorithms and computations
• The Complexity of Small Universal Turing Machines: A Survey

This page was built for publication: The Solvability of the Halting Problem for 2-State Post Machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5546787)