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
The word problem and the isomorphism problem for groups
Diem-Grade Logischer Entscheidungsprobleme
Alternation in simple devices
Iterated uniform finite-state transducers on unary languages
Parsimonious computational completeness
Beitrag zur Reduktion des Entscheidungsproblems auf Klassen von Hornformeln mit kurzen Alternationen
On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
The complexity of finding SUBSEQ\((A)\)
On two-way FA with monotonic counters and quadratic Diophantine equations
A dynamical system which must be stable whose stability cannot be proved
Title not available (Why is that?)
Transductions and the parallel generation of languages^†
Algorithmic Analysis of Array-Accessing Programs
Alternating two-way AC-tree automata
Pushdown automata with reversal-bounded counters
Unsolvable algorithmic problems for semigroups, groups and rings
RESTRICTED SETS OF TRAJECTORIES AND DECIDABILITY OF SHUFFLE DECOMPOSITIONS
On two-way weak counter machines
A note on some systems of lindenmayer
Bad News on Decision Problems for Patterns
One-reversal counter machines and multihead automata: revisited
One-reversal counter machines and multihead automata: revisited
On the complexity of decision problems for some classes of machines and applications
Linear logic automata
Reachability relations of timed pushdown automata
Communication for alternating machines
On the ambiguity and finite-valuedness problems in acceptors and transducers
Indirect addressing and the time relationships of some models of sequential computation
From mathesis universalis to provability, computability, and constructivity
Augmenting the discrete timed automaton with other data structures.
Herbrand strategies and the greater deducibility relation
The reachability problem for Petri nets and decision problems for Skolem arithmetic
Existential arithmetization of Diophantine equations
Pushdown automata with counters
About \(P\) systems with symport/antiport
On decision problems for parameterized machines
Undecidability of the identity problem for finite semigroups
What is a universal computing machine?
The complexity of reachability in distributed communicating processes
Decision problems for tag systems
Register machine proof of the theorem on exponential diophantine representation of enumerable sets
Programs, Grammars and Arguments: A Personal View of some Connections between Computation, Language and Logic
The immortality problem for Lag systems
The word and order problems for self-similar and automata groups
Nondecidable intermediate calculus
Time-restricted sequence generation
Semilinearity of families of languages
A characterization of reversal-bounded multipushdown machine languages

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)