Frontier between decidability and undecidability: A survey
From MaRDI portal
Publication:1575913
DOI10.1016/S0304-3975(99)00102-4zbMath0956.03041OpenAlexW2134468631MaRDI QIDQ1575913
Publication date: 23 August 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(99)00102-4
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (16)
The Complexity of Small Universal Turing Machines: A Survey ⋮ Universality in Molecular and Cellular Computing ⋮ Abstract geometrical computation. VIII: Small machines, accumulations \& rationality ⋮ Small Universal Devices ⋮ On Goles' universal machines: a computational point of view ⋮ On the complex behavior of simple tag systems -- an experimental approach ⋮ Inclusion problems for patterns with a bounded number of variables ⋮ The power of reachability testing for timed automata ⋮ The word problem for one-relation monoids: a survey ⋮ Fractal dimension versus process complexity ⋮ Tag systems and Collatz-like functions ⋮ Small Turing machines and generalized busy beaver competition ⋮ ON THE OPTIMAL NUMBER OF INSTRUCTIONS FOR UNIVERSAL TURING MACHINES CONNECTED WITH A FINITE AUTOMATON ⋮ Wang's B machines are efficiently universal, as is Hasenjaeger's small universal electromechanical toy ⋮ The complexity of small universal Turing machines: A survey ⋮ Maurice Margenstern’s Contributions to the Field of Small Universal Turing Machines
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Busy beaver competition and Collatz-like problems
- An undecidable problem about rational sets and contour words of polyominoes
- Investigations on algorithmic questions of algebra
- Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors
- An aperiodic set of 13 Wang tiles
- A note on Post's correspondence problem
- The (generalized) Post correspondence problem with lists consisting of two words is decidable
- Splicing semigroups of dominoes and DNA
- Turing computability with neural nets
- Undecidable tiling problems in the hyperbolic plane
- Computation and construction universality of reversible cellular automata
- Analog computation via neural networks
- Small universal Turing machines
- Small deterministic Turing machines
- On machines, universal by extensions
- Small universal register machines
- Computing by splicing
- Self-reproduction in a reversible cellular space
- Das Identitätsproblem für Gruppen mit einer definierenden Relation
- Complete formal systems for equivalence problems
- DNA computing based on splicing: Universality results
- Using DNA to solve the bounded Post correspondence problem
- A computation-universal two-dimensional 8-state triangular reversible cellular automaton
- Nine test tubes generate any RE language
- Self-reproduction in small cellular automata
- Solvability of the halting problem for certain classes of Turing machines
- Linear cellular automata, finite automata and Pascal's triangle
- Left-divisibility and word problems in single relation monoids
- Tag systems and lag systems
- Undecidability and nonperiodicity for tilings of the plane
- The 3x + 1 Problem and Its Generalizations
- Towards a Precise Characterization of the Complexity of Universal and Nonuniversal Turing Machines
- Universal diophantine equation
- The laterality problem for non-erasing Turing machines on $\lbrace 0,1\rbrace $ is completely solved
- On the Word Problem for Single Relation Monoids with an Unbordered Relator
- The equivalence problem for deterministic pushdown automata is decidable
- Optimal simulation of automata by neural nets
- Conway's Prime Producing Machine
- Recursive Unsolvability of a problem of Thue
- Non-erasing turing machines: A new frontier between a decidable halting problem and universality
- Simulations between cellular automata on cayley graphs
- Small universal one-state linear operator algorithm
- The undecidability of the domino problem
- The Categorization of Tag Systems in Terms of Decidability
- An associative calculus with an unsolvable problem of equivalence
- Certain properties of E. L. Post’s apparatus of canonical calculi
- Logical Reversibility of Computation
- On Computable Numbers, with an Application to the Entscheidungsproblem
- Checker Boards and Polyominoes
- On the Forms of the Predicates in the Theory of Constructive Ordinals
- A logical calculus of the ideas immanent in nervous activity
This page was built for publication: Frontier between decidability and undecidability: A survey