The use of lists in the study of undecidable problems in automata theory

DOI10.1016/S0022-0000(71)80007-7zbMath0234.02024OpenAlexW1991961178MaRDI QIDQ2551463

Juris Hartmanis, Forbes D. Lewis

Publication date: 1971

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(71)80007-7

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Automata and formal grammars in connection with logical questions (03D05) Turing machines and related notions (03D10)

Related Items

Index sets and presentations of complexity classes, P-selectivity: Intersections and indices, Some lowness properties and computational complexity sequences, A second step towards complexity-theoretic analogs of Rice's Theorem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing degrees of unsolvability
• Gödel numberings of partial recursive functions
• Number theoretic concepts and recursive well-orderings
• General Problems of Formal Grammars
• Recursive Predicates and Quantifiers
• Recursively enumerable sets of positive integers and their decision problems
• Creative sets