The degree diagram of undecidable problems of formal grammars
Dennis F. Cudia · ACM SIGACT News · 1969
Let O be the degree of all solvable problems, let O' be the degree of unsolvability of the halting problem for Turing machines, let O'' be the degree of unsolvability of the problem of whether an arbitrary Turing machine eventually halts for only finitely many finite initial configurations, and let O''' be the degree of unsolvability of the problem of whether an arbitrary Turing machine never halts for only finitely many finite initial configurations. Let ≤ denote the partial ordering of Turing reducibility. Then using results and methods of 1. and 2., the following degree diagram refinement of a table of solvable and unsolvable problems, which appears in 3., p. 230, may be obtained.