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

Cited In (only showing first 100 items - show all)

Undecidability of the problem of recognizing axiomatizations of superintuitionistic propositional calculi
The undecidability of the first-order theories of one step rewriting in linear canonical systems
Das Entscheidungsproblem der Klasse von Formeln, die höchstens zwei Primformeln enthalten
Counter machines
\(\forall \exists^{5}\)-equational theory of context unification is undecidable
The \(\exists\forall^2\) fragment of the first-order theory of atomic set constraints is \(\Pi_1^0\)-hard
The developments of the concept of machine computability from 1936 to the 1960s
On the decision problem for MELL
System NEL is undecidable
Cut-type rules for calculi of general type
On reachability and safety in infinite-state systems
Comparison of max-plus automata and joint spectral radius of tropical matrices
Modeling multitape Minsky and Turing machines by three-tape Minsky machines
A technique for proving decidability of containment and equivalence of linear constraint queries
On Affine Reachability Problems
Percentile queries in multi-dimensional Markov decision processes
SOME DECISION QUESTIONS CONCERNING THE TIME COMPLEXITY OF LANGUAGE ACCEPTORS
Accepting runs in a two-way finite automaton
Bit-complexity of classical solutions of linear evolutionary systems of partial differential equations
On the complexity of decision problems for counter machines with applications to coding theory
Quantum versus deterministic counter automata
ON COUNTER MACHINES, REACHABILITY PROBLEMS, AND DIOPHANTINE EQUATIONS
Title not available (Why is that?)
Counter machines and distributed automata -- a story about exchanging space and time
Symbolic automatic relations and their applications to SMT and CHC solving
\(\Pi_ 1^ 1\)-universality of some propositional logics of concurrent programs
Simulations by time-bounded counter machines
Conway's work on iteration
Grammatical characterizations of NPDAs and VPDAs with counters
Clocked population protocols
On the Class of Predicates Decidable by Two-Way Multitape Finite Automata
On decidability and closure properties of language classes with respect to bio-operations
On counting functions and slenderness of languages
On the density of context-free and counter languages
A direct method for simulating partial recursive functions by Diophantine equations
Undecidability of multiplicative subexponential logic
Some complexity results for stateful network verification
Language models for some extensions of the Lambek calculus
The many-one equivalence of some general combinatorial decision problems
Some decision problems for parallel communicating grammar systems
A framework for linear authorization logics
Weighted automata
The undecidability of second order linear logic without exponentials
Computing with chemical reaction networks: a tutorial
Computability by Normal Algorithms
Computational power of two stacks with restricted communication
Title not available (Why is that?)
Word problem for knotted residuated lattices.
First-order concatenation theory with bounded quantifiers
Computation by assembly
Decision Problems for Finite Automata over Infinite Algebraic Structures
Minsky Machines and Algorithmic Problems
On the computational complexity of membrane systems
Reachability problems and abstract state spaces for time Petri nets with stopwatches
A rewriting framework and logic for activities subject to regulations
Spectra and satisfiability for logics with successor and a unary function
Counter machines and counter languages
Counter machines and verification problems.
The undecidability of the disjunction property of propositional logics and other related problems
Multi-stack-counter languages
The equivalence of stack-counter acceptors and quasi-realtime stack- counter acceptors
Normality and automata
Formal analysis of oscillatory behaviors in biological regulatory networks: an alternative approach
Decision problems for pushdown threads
Undecidability in diagonalizable algebras
Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. I
P systems with symport/antiport simulating counter automata
Closing the Circle: An Analysis of Emil Post's Early Work
Complexity of some problems in Petri nets
Linear logic as a logic of computations
Remarks on the complexity of nondeterministic counter languages
The Boolean algebra of logic
\(\mathcal C\)-graph automatic groups.
Instruction sequence processing operators
On the universe, disjointness, and containment problems for simple machines
Decidability questions for insertion systems and related models
Decision problems for propositional linear logic
Applying abstract acceleration to (co-)reachability analysis of reactive programs
A decidability result for the model checking of infinite-state systems
Computation with finite stochastic chemical reaction networks
The theory of languages
Typability and type checking in System F are equivalent and undecidable
Complexity and decidability for chain code picture languages
Undecidable properties of extensions of the logic of provability
The theory of languages
Mutation calculi
What makes some language theory problems undecidable
Characterizations of the decidability of some problems for regular trace languages
Looking at mean-payoff and total-payoff through windows
Catalytic P systems, semilinear sets, and vector addition systems
Counting Time in Computing with Cells
Remarks on blind and partially blind one-way multicounter machines
Petri nets, Horn programs, linear logic and vector games
Decidability of code properties
ON ONE-MEMBRANE P SYSTEMS OPERATING IN SEQUENTIAL MODE
When ambients cannot be opened
On incomparable abstract family of languages (AFL)
A survey of state vectors
The conformon-P system: a molecular and cell biology-inspired computability model
NON-RECURSIVE TRADE-OFFS FOR TWO-WAY MACHINES

This page was built for publication: Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q775202)