Machine Configuration and Word Problems of Given Degree of Unsolvability

From MaRDI portal
Publication:5545521

DOI10.1002/malq.19650110210zbMath0161.00803OpenAlexW1977949996MaRDI QIDQ5545521

John C. Shepherdson

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 problemsUnsolvable algorithmic problems for semigroups, groups and ringsThe many-one equivalence of some general combinatorial decision problemsMany-one degrees associated with problems of tagDecision problems for cellular automata and their semigroupsWord problems and ceersClassifying word problems of finitely generated algebras via computable reducibilityCellular automata and intermediate degrees.The reachability problem for Petri nets and decision problems for Skolem arithmeticDecision problems for tag systemsDegrees of unsolvability associated with Markov algorithmsOn the classifiability of cellular automataCombinatorial systems defined over one- and two-letter alphabetsINPUT/OUTPUT CODINGS AND TRANSITION FUNCTIONS IN EFFECTIVE SYSTEMSRecursively enumerable degress and the conjugacy problemOn recognising properties of groups which have solvable word problemRepresentation of Turing reducibility by word and conjugacy problems in finitely presented groupsOn the complexity of individual identity problems in semigroupsCombinatorial systems. I: Cylindrical problemsRepresentation of one-one degrees by decision problems for system functionsDegree problems for modular machinesMany-one degrees associated with semi-Thue systemsFinite complete rewriting systems and the complexity of word problemSome undecidability results for non-monadic Church-Rosser Thue systems