Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | |||
| turing_degree [2025/02/12 10:05] – external edit 127.0.0.1 | turing_degree [2025/02/12 10:19] (current) – lpatey | ||
|---|---|---|---|
| Line 3: | Line 3: | ||
| 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 ===== | ||