tag

#turing degrees

4 pages tagged

Maths › 03. Logic and Foundations ›

12.4 Post’s Problem

12.4 Post’s Problem (Overview) The halting problem shows that some sets are not computable. Turing degrees refine this by measuring how hard such sets are. A natural question arises: is there any degree strictly between computable sets and the halting problem? Let: $$ \mathbf{0} $$ be the degree of computable sets, and: $$ \mathbf{0'} $$ be the degree of the halting problem. Post’s problem asks whether there exists a recursively...
computability post problem priority method turing degrees May 2, 2026
Maths › 03. Logic and Foundations ›

12.5 Structure of Degrees

12.5 Structure of Degrees Turing degrees organize problems by computational power. After Post’s problem, it becomes clear that this structure is highly complex. It is not a simple linear hierarchy but a rich partially ordered system. Partial Order Turing degrees are ordered by reducibility: $$ \mathbf{a} \leq_T \mathbf{b} $$ means every set in degree $\mathbf{a}$ is computable using an oracle for any set in degree $\mathbf{b}$. This order has three...
computability degree structure turing degrees logic May 2, 2026
Maths › 03. Logic and Foundations ›

12.2 Turing Degrees

12.2 Turing Degrees Turing reducibility compares sets by computational power. If $$ A \leq_T B $$ then an oracle for $B$ is strong enough to decide $A$. This comparison naturally groups sets into equivalence classes. Two sets $A$ and $B$ have the same Turing degree if each can compute the other: $$ A \equiv_T B $$ where: $$ A \leq_T B \quad \text{and} \quad B \leq_T A $$ A Turing...
computability turing degrees oracle computation degree theory May 2, 2026
Maths › 03. Logic and Foundations ›

12. Degrees of Unsolvability

Degrees of unsolvability study how undecidable problems can be compared according to their relative computational difficulty, rather than treating all undecidable problems as having the same level of complexity. The chapter begins with reducibility, where one problem is transformed into another in a computable way, so that a solution to the second problem would also give a solution to the first. Turing degrees are then introduced as equivalence classes of...
logic computability turing degrees reducibility recursively enumerable sets May 2, 2026