The Turing Hierarchy of Unsolvability
| Autor: | Borut Robič |
|---|---|
| Rok vydání: | 2020 |
| Předmět: | |
| Zdroj: | The Foundations of Computability Theory ISBN: 9783662624203 The Foundations of Computability Theory ISBN: 9783662448076 |
| DOI: | 10.1007/978-3-662-62421-0_12 |
| Popis: | At this point we only know of two degrees of unsolvability: the T-degree shared by all the decidable decision problems, and the T-degree shared by all undecidable decision problems that are T-equivalent to the Halting Problem. In this chapter we will prove that, surprisingly, for every undecidable decision problem there exists a more difficult decision problem. This will in effect mean that there is an infinite hierarchy of degrees of unsolvability and that there is no most difficult decision problem. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|