Max and min limiters
| Autor: | Georgia A. Martin, William Gasarch, James C. Owings |
|---|---|
| Rok vydání: | 2002 |
| Předmět: | |
| Zdroj: | Archive for Mathematical Logic. 41:483-495 |
| ISSN: | 1432-0665 0933-5846 |
| Popis: | If and the function is partial recursive, it is easily seen that A is recursive. In this paper, we weaken this hypothesis in various ways (and similarly for ``min'' in place of ``max'') and investigate what effect this has on the complexity of A. We discover a sharp contrast between retraceable and co-retraceable sets, and we characterize sets which are the union of a recursive set and a co-r.e., retraceable set. Most of our proofs are noneffective. Several open questions are raised. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|