Machine Configuration and Word Problems of Given Degree of Unsolvability
From MaRDI portal
Publication:5545521
DOI10.1002/malq.19650110210zbMath0161.00803OpenAlexW1977949996MaRDI QIDQ5545521
Publication date: 1965
Published in: Mathematical Logic Quarterly (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/malq.19650110210
Related Items
The equivalence of some general combinatorial decision problems ⋮ Unsolvable algorithmic problems for semigroups, groups and rings ⋮ The many-one equivalence of some general combinatorial decision problems ⋮ Many-one degrees associated with problems of tag ⋮ Decision problems for cellular automata and their semigroups ⋮ Word problems and ceers ⋮ Classifying word problems of finitely generated algebras via computable reducibility ⋮ Cellular automata and intermediate degrees. ⋮ The reachability problem for Petri nets and decision problems for Skolem arithmetic ⋮ Decision problems for tag systems ⋮ Degrees of unsolvability associated with Markov algorithms ⋮ On the classifiability of cellular automata ⋮ Combinatorial systems defined over one- and two-letter alphabets ⋮ INPUT/OUTPUT CODINGS AND TRANSITION FUNCTIONS IN EFFECTIVE SYSTEMS ⋮ Recursively enumerable degress and the conjugacy problem ⋮ On recognising properties of groups which have solvable word problem ⋮ Representation of Turing reducibility by word and conjugacy problems in finitely presented groups ⋮ On the complexity of individual identity problems in semigroups ⋮ Combinatorial systems. I: Cylindrical problems ⋮ Representation of one-one degrees by decision problems for system functions ⋮ Degree problems for modular machines ⋮ Many-one degrees associated with semi-Thue systems ⋮ Finite complete rewriting systems and the complexity of word problem ⋮ Some undecidability results for non-monadic Church-Rosser Thue systems
