Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
| turing_degree [2025/02/10 15:53] – created lpatey | turing_degree [2025/02/12 10:19] (current) – lpatey | ||
|---|---|---|---|
| Line 2: | Line 2: | ||
| The concept of **Turing degree** is fundamental in computability theory and provides a way to classify the relative complexity of undecidable problems. Two sets of natural numbers have the same Turing degree if they are **Turing equivalent**, | The concept of **Turing degree** is fundamental in computability theory and provides a way to classify the relative complexity of undecidable problems. Two sets of natural numbers have the same Turing degree if they are **Turing equivalent**, | ||
| + | |||
| + | < | ||
| ===== Definition ===== | ===== Definition ===== | ||