Degrees of unsolvability associated with Markov algorithms
From MaRDI portal
Publication:4052103
DOI10.1007/BF00987253zbMath0298.02040MaRDI QIDQ4052103
Publication date: 1972
Published in: International Journal of Computer & Information Sciences (Search for Journal in Brave)
Word problems, etc. in computability and recursion theory (03D40) Other degrees and reducibilities in computability and recursion theory (03D30) Turing machines and related notions (03D10) Algorithms in computer science (68W99) Thue and Post systems, etc. (03D03)
Related Items
Combinatorial systems defined over one- and two-letter alphabets ⋮ Diem-Grade Logischer Entscheidungsprobleme ⋮ Many-one degrees associated with semi-Thue systems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Word problems and recursively enumerable degrees at unsolvability. A first paper on Thue systems
- Machine Configuration and Word Problems of Given Degree of Unsolvability
- The equivalence of some general combinatorial decision problems
- Quantificational variants on the halting problem for turing machines
- The many-one equivalence of some general combinatorial decision problems
- Recursively enumerable sets of positive integers and their decision problems