The laterality problem for non-erasing Turing machines on \lbrace 0,1\rbrace is completely solved
From MaRDI portal
Publication:4349780
DOI10.1051/ITA/1997310201591zbMATH Open0878.68063OpenAlexW85833935MaRDI QIDQ4349780FDOQ4349780
Authors: M. Margenstern 
Publication date: 25 August 1997
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/92557
Recommendations
- scientific article; zbMATH DE number 522863
- Non-erasing turing machines: A new frontier between a decidable halting problem and universality
- Element distinctness on one-tape Turing machines: a complete solution
- Turing L-machines and recursive computability for L-maps
- Formalization of the class of problems solvable by a nondeterministic Turing machine
- scientific article; zbMATH DE number 3988715
- On the generic undecidability of the halting problem for normalized Turing machines
- On algorithmic solvability of a completeness problem for linear automata
- Undecidability of the speed positiveness problem in reversible and complete Turing machines
- Turing Definability in the Ershov Hierarchy
Cites Work
- Title not available (Why is that?)
- On Computable Numbers, with an Application to the Entscheidungsproblem
- Small universal Turing machines
- Title not available (Why is that?)
- Solvability of the halting problem for certain classes of Turing machines
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (7)
- Title not available (Why is that?)
- Frontier between decidability and undecidability: A survey
- Maurice Margenstern's contributions to the field of small universal Turing machines
- The Complexity of Small Universal Turing Machines: A Survey
- Wang's B machines are efficiently universal, as is Hasenjaeger's small universal electromechanical toy
- Turing machines with two letters and two states
- The complexity of small universal Turing machines: A survey
This page was built for publication: The laterality problem for non-erasing Turing machines on $\lbrace 0,1\rbrace $ is completely solved
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4349780)
