Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines

DOI10.2307/1970290zbMath0105.00802OpenAlexW2061970672WikidataQ29032060 ScholiaQ29032060MaRDI QIDQ775202

Marvin L. Minsky

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

zbMATH Keywords

mathematical logic

Related Items

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 ⋮ The theory of languages ⋮ Counter machines and counter languages ⋮ The undecidability of the Turing machine immortality problem ⋮ The theory of languages ⋮ Algorithmic properties of structures ⋮ The many-one equivalence of some general combinatorial decision problems ⋮ A note on some systems of lindenmayer ⋮ Multi-stack-counter languages ⋮ On the complexity of decision problems for some classes of machines and applications ⋮ On some algebraic ways to calculate zeros of the Riemann zeta function ⋮ Computability by Normal Algorithms ⋮ Generalizations of Checking Stack Automata: Characterizations and Hierarchies ⋮ Computing with chemical reaction networks: a tutorial ⋮ Synchronizing deterministic push-down automata can be really hard ⋮ Decision problems for tag systems ⋮ Unnamed Item ⋮ Percentile queries in multi-dimensional Markov decision processes ⋮ ON ONE-MEMBRANE P SYSTEMS OPERATING IN SEQUENTIAL MODE ⋮ RESTRICTED SETS OF TRAJECTORIES AND DECIDABILITY OF SHUFFLE DECOMPOSITIONS ⋮ NON-RECURSIVE TRADE-OFFS FOR TWO-WAY MACHINES ⋮ Iterated uniform finite-state transducers on unary languages ⋮ Recursed Is Not Recursive: A Jarring Result ⋮ The undecidability theorem for the Horn-like fragment of linear logic (Revisited) ⋮ On the Ambiguity and Finite-Valuedness Problems in Acceptors and Transducers ⋮ Iterative arrays with finite inter-cell communication ⋮ Input-driven multi-counter automata ⋮ Monogenic normal systems are universal ⋮ On the Class of Predicates Decidable by Two-Way Multitape Finite Automata ⋮ Weak Cost Register Automata are Still Powerful ⋮ Semilinearity of Families of Languages ⋮ Continuous One-counter Automata ⋮ On Boolean closed full trios and rational Kripke frames ⋮ Transductions and the parallel generation of languages^† ⋮ The Complexity of Small Universal Turing Machines: A Survey ⋮ Alternating two-way AC-tree automata ⋮ Unnamed Item ⋮ An Alternative Direct Simulation of Minsky Machines into Classical Bunched Logics via Group Semantics ⋮ An undecidable problem in correspondence theory ⋮ The undecidability of the disjunction property of propositional logics and other related problems ⋮ Reachability in Succinct and Parametric One-Counter Automata ⋮ The ∀∃-theory of ℛ(≤,∨,∧) is undecidable ⋮ Sufficient-completeness, ground-reducibility and their complexity ⋮ Register machine proof of the theorem on exponential diophantine representation of enumerable sets ⋮ Tag systems and lag systems ⋮ On the complexity of decision problems for counter machines with applications to coding theory ⋮ Uncountable realtime probabilistic classes ⋮ Parallel communicating grammar systems: the context-sensitive case ⋮ Undecidability of the identity problem for finite semigroups ⋮ Solvable problems for transformers with reversal-bounded counters ⋮ Deletion operations on deterministic families of automata ⋮ Programs=data=first-class citizens in a computational world ⋮ Many-one degrees associated with problems of tag ⋮ Minsky Machines and Algorithmic Problems ⋮ Language models for some extensions of the Lambek calculus ⋮ MOST SIMPLE EXTENSIONS OF ARE UNDECIDABLE ⋮ On two-way weak counter machines ⋮ On counting functions and slenderness of languages ⋮ Insertion operations on deterministic reversal-bounded counter machines ⋮ Spectra and satisfiability for logics with successor and a unary function ⋮ Bit-complexity of classical solutions of linear evolutionary systems of partial differential equations ⋮ On the Density of Context-Free and Counter Languages ⋮ Undecidability in diagonalizable algebras ⋮ Infinitary action logic with multiplexing ⋮ A rewriting framework and logic for activities subject to regulations ⋮ Unnamed Item ⋮ ON COUNTER MACHINES, REACHABILITY PROBLEMS, AND DIOPHANTINE EQUATIONS ⋮ Bad News on Decision Problems for Patterns ⋮ Isomorphisms of scattered automatic linear orders ⋮ First-order concatenation theory with bounded quantifiers ⋮ A framework for linear authorization logics ⋮ Reachability relations of timed pushdown automata ⋮ Inclusion is undecidable for pattern languages ⋮ New decidability results concerning two-way counter machines and applications ⋮ Modeling multitape Minsky and Turing machines by three-tape Minsky machines ⋮ The undecidability of second order linear logic without exponentials ⋮ The Boolean algebra of logic ⋮ Quantitative Automata under Probabilistic Semantics ⋮ Domain-Freeλµ-Calculus ⋮ Expressing additives using multiplicatives and subexponentials ⋮ From Mathesis Universalis to Provability, Computability, and Constructivity ⋮ Programs, Grammars and Arguments: A Personal View of some Connections between Computation, Language and Logic ⋮ Alternation in simple devices ⋮ Tag systems and Collatz-like functions ⋮ VERIFICATION IN QUEUE-CONNECTED MULTICOUNTER MACHINES ⋮ Decidability Questions for Insertion Systems and Related Models ⋮ Word problem for knotted residuated lattices. ⋮ Undecidability of the problem of recognizing axiomatizations of superintuitionistic propositional calculi ⋮ System NEL is Undecidable ⋮ Decidability of code properties ⋮ Diem-Grade Logischer Entscheidungsprobleme ⋮ Beitrag zur Reduktion des Entscheidungsproblems auf Klassen von Hornformeln mit kurzen Alternationen ⋮ On decision problems for parameterized machines ⋮ Unnamed Item ⋮ Stack and register complexity of radix conversions ⋮ Unnamed Item ⋮ On the Containment and Equivalence Problems for GSMs, Transducers, and Linear CFGs ⋮ On Synchronized Multitape and Multihead Automata ⋮ Playing with Repetitions in Data Words Using Energy Games ⋮ Halteprobleme von Fang-Systemen (tag systems) ⋮ The Riemann hypothesis in computer science ⋮ Counting Time in Computing with Cells ⋮ One-Reversal Counter Machines and Multihead Automata: Revisited ⋮ SIMULATIONS BY TIME-BOUNDED COUNTER MACHINES ⋮ Bemerkung zu Gurevich's Arbeit über das Entscheidungsproblem für Standardklassen ⋮ Simulations by Time-Bounded Counter Machines ⋮ Time-restricted sequence generation ⋮ On Affine Reachability Problems ⋮ What makes some language theory problems undecidable ⋮ On decidability and closure properties of language classes with respect to bio-operations ⋮ On the overlap assembly of strings and languages ⋮ Algorithmic Analysis of Array-Accessing Programs ⋮ Maurice Margenstern’s Contributions to the Field of Small Universal Turing Machines ⋮ Decision Problems for Finite Automata over Infinite Algebraic Structures ⋮ Characterizations of the decidability of some problems for regular trace languages ⋮ Pushdown automata with counters ⋮ Deciding reachability problems in Turing-complete fragments of Mobile Ambients ⋮ Comparison of max-plus automata and joint spectral radius of tropical matrices ⋮ On composition and lookahead delegation of \(e\)-services modeled by automata ⋮ SOME DECISION QUESTIONS CONCERNING THE TIME COMPLEXITY OF LANGUAGE ACCEPTORS ⋮ Some undecidable theories with monadic predicates and without equality ⋮ ON REACHABILITY AND SAFETY IN INFINITE-STATE SYSTEMS ⋮ Finite degree clones are undecidable ⋮ The Developments of the Concept of Machine Computability from 1936 to the 1960s ⋮ Some complexity results for stateful network verification ⋮ About \(P\) systems with symport/antiport ⋮ The stability of the deterministic Skorokhod problem is undecidable ⋮ Closing the Circle: An Analysis of Emil Post's Early Work ⋮ The word problem and the isomorphism problem for groups ⋮ Looking at mean-payoff and total-payoff through windows ⋮ On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words ⋮ Prefix classes of krom formulae with identity