Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
From MaRDI portal
Publication:775202
DOI10.2307/1970290zbMath0105.00802OpenAlexW2061970672WikidataQ29032060 ScholiaQ29032060MaRDI QIDQ775202
Publication date: 1961
Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/1970290
Related Items (only showing first 100 items - show all)
On the solvability of a class of Diophantine equations and applications ⋮ Linear logic as a logic of computations ⋮ A direct method for simulating partial recursive functions by Diophantine equations ⋮ Formal analysis of oscillatory behaviors in biological regulatory networks: an alternative approach ⋮ Two-way automata with more than one storage medium ⋮ Iterated uniform finite-state transducers on unary languages ⋮ Parsimonious computational completeness ⋮ The conformon-P system: a molecular and cell biology-inspired computability model ⋮ On two-way FA with monotonic counters and quadratic Diophantine equations ⋮ Catalytic P systems, semilinear sets, and vector addition systems ⋮ Some decision problems for parallel communicating grammar systems ⋮ On the determinacy problem for two-way pushdown automata ⋮ The complexity of finding SUBSEQ\((A)\) ⋮ An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines ⋮ On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes ⋮ Symbolic automatic relations and their applications to SMT and CHC solving ⋮ The complexity of reachability in distributed communicating processes ⋮ Petri nets, Horn programs, linear logic and vector games ⋮ Conway's work on iteration ⋮ Counter machines and distributed automata -- a story about exchanging space and time ⋮ Pushdown automata with reversal-bounded counters ⋮ Unsolvable algorithmic problems for semigroups, groups and rings ⋮ On the computational complexity of membrane systems ⋮ Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. III ⋮ Problems concerning fairness and temporal logic for conflict-free Petri nets ⋮ Mutation calculi ⋮ Linear logic automata ⋮ Reachability problems and abstract state spaces for time Petri nets with stopwatches ⋮ Decision problems for pushdown threads ⋮ Simple counter machines and number-theoretic problems ⋮ On the complex behavior of simple tag systems -- an experimental approach ⋮ The equivalence of stack-counter acceptors and quasi-realtime stack- counter acceptors ⋮ \(\mathcal C\)-graph automatic groups. ⋮ Indirect addressing and the time relationships of some models of sequential computation ⋮ Low dimensional hybrid systems -- decidable, undecidable, don't know ⋮ Herbrand strategies and the greater deducibility relation ⋮ The reachability problem for Petri nets and decision problems for Skolem arithmetic ⋮ The complexity of decision problems for finite-turn multicounter machines ⋮ Applying abstract acceleration to (co-)reachability analysis of reactive programs ⋮ On the complexity and decidability of some problems involving shuffle ⋮ A decidability result for the model checking of infinite-state systems ⋮ On synchronized multi-tape and multi-head automata ⋮ The immortality problem for Lag systems ⋮ Two-way deterministic multi-weak-counter machines ⋮ Computational power of two stacks with restricted communication ⋮ A survey of state vectors ⋮ On the decision problem for MELL ⋮ Normality and automata ⋮ Undecidability of ground reducibility for word rewriting systems with variables ⋮ On information invariants in robotics ⋮ The submonoid and rational subset membership problems for graph groups. ⋮ Decision problems for propositional linear logic ⋮ Dynamical systems in categories ⋮ Further remarks on DNA overlap assembly ⋮ Narrowing based procedures for equational disunification ⋮ Counter machines, Petri nets, and consensual computation ⋮ Accepting runs in a two-way finite automaton ⋮ Communication for alternating machines ⋮ Confusion of memory ⋮ On two-way nondeterministic finite automata with one reversal-bounded counter ⋮ On incomparable abstract family of languages (AFL) ⋮ A dynamical system which must be stable whose stability cannot be proved ⋮ When ambients cannot be opened ⋮ P systems with symport/antiport simulating counter automata ⋮ On the universe, disjointness, and containment problems for simple machines ⋮ Computation by assembly ⋮ Remarks on the complexity of nondeterministic counter languages ⋮ One-reversal counter machines and multihead automata: revisited ⋮ Instruction sequence processing operators ⋮ Quantum versus deterministic counter automata ⋮ Finite automata with multiplication ⋮ Grammatical characterizations of NPDAs and VPDAs with counters ⋮ Complexity of some problems in Petri nets ⋮ Das Entscheidungsproblem der Klasse von Formeln, die höchstens zwei Primformeln enthalten ⋮ Remarks on blind and partially blind one-way multicounter machines ⋮ Clocked population protocols ⋮ The complexity of small universal Turing machines: A survey ⋮ Existential arithmetization of Diophantine equations ⋮ Cut-type rules for calculi of general type ⋮ A technique for proving decidability of containment and equivalence of linear constraint queries ⋮ Undecidable properties of extensions of the logic of provability ⋮ Computation with finite stochastic chemical reaction networks ⋮ Weighted automata ⋮ What is a universal computing machine? ⋮ The complexity of the word problems for commutative semigroups and polynomial ideals ⋮ The word and order problems for self-similar and automata groups ⋮ Nondecidable intermediate calculus ⋮ Bad news on decision problems for patterns ⋮ Typability and type checking in System F are equivalent and undecidable ⋮ Counter machines and verification problems. ⋮ Augmenting the discrete timed automaton with other data structures. ⋮ One-way probabilistic reversible and quantum one-counter automata. ⋮ Complexity and decidability for chain code picture languages ⋮ A characterization of reversal-bounded multipushdown machine languages ⋮ The undecidability of the first-order theories of one step rewriting in linear canonical systems ⋮ \(\Pi_ 1^ 1\)-universality of some propositional logics of concurrent programs ⋮ Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. I ⋮ Counter machines ⋮ The \(\exists\forall^2\) fragment of the first-order theory of atomic set constraints is \(\Pi_1^0\)-hard ⋮ \(\forall \exists^{5}\)-equational theory of context unification is undecidable
This page was built for publication: Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
