Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
From MaRDI portal
Publication:775202
DOI10.2307/1970290zbMath0105.00802WikidataQ29032060 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
On the computational complexity of membrane systems, Mutation calculi, Undecidability of ground reducibility for word rewriting systems with variables, A dynamical system which must be stable whose stability cannot be proved, P systems with symport/antiport simulating counter automata, Undecidable properties of extensions of the logic of provability, Nondecidable intermediate calculus, On the solvability of a class of Diophantine equations and applications, The complexity of finding SUBSEQ\((A)\), Reachability problems and abstract state spaces for time Petri nets with stopwatches, Decision problems for pushdown threads, The immortality problem for Lag systems, The submonoid and rational subset membership problems for graph groups., Confusion of memory, The complexity of small universal Turing machines: A survey, Existential arithmetization of Diophantine equations, Computation with finite stochastic chemical reaction networks, What is a universal computing machine?, Bad news on decision problems for patterns, Complexity and decidability for chain code picture languages, A characterization of reversal-bounded multipushdown machine languages, Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. I, Two-way automata with more than one storage medium, 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, The complexity of reachability in distributed communicating processes, Pushdown automata with reversal-bounded counters, Unsolvable algorithmic problems for semigroups, groups and rings, Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. III, Problems concerning fairness and temporal logic for conflict-free Petri nets, Simple counter machines and number-theoretic problems, Indirect addressing and the time relationships of some models of sequential computation, 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, Two-way deterministic multi-weak-counter machines, Decision problems for propositional linear logic, Narrowing based procedures for equational disunification, Communication for alternating machines, On incomparable abstract family of languages (AFL), Computation by assembly, Remarks on the complexity of nondeterministic counter languages, Finite automata with multiplication, 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, Cut-type rules for calculi of general type, Typability and type checking in System F are equivalent and undecidable, \(\Pi_ 1^ 1\)-universality of some propositional logics of concurrent programs, Linear logic as a logic of computations, A direct method for simulating partial recursive functions by Diophantine equations, Some decision problems for parallel communicating grammar systems, On the determinacy problem for two-way pushdown automata, The equivalence of stack-counter acceptors and quasi-realtime stack- counter acceptors, 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, On two-way nondeterministic finite automata with one reversal-bounded counter, When ambients cannot be opened, Quantum versus deterministic counter automata, A technique for proving decidability of containment and equivalence of linear constraint queries, The complexity of the word problems for commutative semigroups and polynomial ideals, Counter machines and verification problems., Augmenting the discrete timed automaton with other data structures., One-way probabilistic reversible and quantum one-counter automata., The undecidability of the first-order theories of one step rewriting in linear canonical systems, 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, Petri nets, Horn programs, linear logic and vector games, Linear logic automata, On decision problems for parameterized machines, Alternating two-way AC-tree automata, Tag systems and lag systems, Tag systems and Collatz-like functions, Time-restricted sequence generation, What makes some language theory problems undecidable, Pushdown automata with counters, On composition and lookahead delegation of \(e\)-services modeled by automata, About \(P\) systems with symport/antiport, Sufficient-completeness, ground-reducibility and their complexity, Domain-Freeλµ-Calculus, VERIFICATION IN QUEUE-CONNECTED MULTICOUNTER MACHINES, Reachability in Succinct and Parametric One-Counter Automata, Many-one degrees associated with problems of tag, Closing the Circle: An Analysis of Emil Post's Early Work, ON COUNTER MACHINES, REACHABILITY PROBLEMS, AND DIOPHANTINE EQUATIONS, Bad News on Decision Problems for Patterns, Counting Time in Computing with Cells, Simulations by Time-Bounded Counter Machines, Algorithmic Analysis of Array-Accessing Programs, Deciding reachability problems in Turing-complete fragments of Mobile Ambients, Register machine proof of the theorem on exponential diophantine representation of enumerable sets, Solvable problems for transformers with reversal-bounded counters, On two-way weak counter machines, Halteprobleme von Fang-Systemen (tag systems), Some undecidable theories with monadic predicates and without equality, The word problem and the isomorphism problem for groups, Prefix classes of krom formulae with identity, Transductions and the parallel generation of languages†, The undecidability of the disjunction property of propositional logics and other related problems, Parallel communicating grammar systems: the context-sensitive case, Undecidability in diagonalizable algebras, Programs, Grammars and Arguments: A Personal View of some Connections between Computation, Language and Logic, Beitrag zur Reduktion des Entscheidungsproblems auf Klassen von Hornformeln mit kurzen Alternationen, Unnamed Item, Characterizations of the decidability of some problems for regular trace languages, The ∀∃-theory of ℛ(≤,∨,∧) is undecidable, The undecidability of second order linear logic without exponentials, Decidability of code properties, Monogenic normal systems are universal, On the Class of Predicates Decidable by Two-Way Multitape Finite Automata, 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, Computability by Normal Algorithms, Decision problems for tag systems, 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, Unnamed Item, An undecidable problem in correspondence theory, Undecidability of the identity problem for finite semigroups, The Boolean algebra of logic, Diem-Grade Logischer Entscheidungsprobleme, Bemerkung zu Gurevich's Arbeit über das Entscheidungsproblem für Standardklassen
