Turing Machines for Dummies

DOI10.1007/978-3-642-27660-6_2zbMath1298.68092OpenAlexW2169821472MaRDI QIDQ2891358

Peter van Emde Boas

Publication date: 15 June 2012

Published in: SOFSEM 2012: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-27660-6_2

Mathematics Subject Classification ID

Cites Work

• A simplified proof of the real-time recognizability of palindromes on Turing machines
• A characterization of the power of vector machines
• Domino-tiling games
• Relationships between nondeterministic and deterministic tape complexities
• An Optimal Simulation of Counter Machines
• Register machine proof of the theorem on exponential diophantine representation of enumerable sets
• Nondeterministic Space is Closed under Complementation
• Alternation
• Two-Tape Simulation of Multitape Turing Machines
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Turing Machines for Dummies