Bounding lemmata for non-deterministic halting times of transfinite Turing machines
| Autor: | Philip D. Welch |
|---|---|
| Rok vydání: | 2008 |
| Předmět: |
Discrete mathematics
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES General Computer Science Hyperarithmetical theory Recursive ordinal Description number Computer Science::Computational Complexity Theoretical Computer Science Combinatorics Turing machine symbols.namesake TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Computability theory symbols Set theory Computer Science(all) Transfinite number Descriptive set theory Mathematics |
| Zdroj: | Theoretical Computer Science. 394:223-228 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2007.12.014 |
| Popis: | We use the methods of descriptive set theory and generalized recursion theory to prove various Bounding Lemmata that contribute to a body of results on halting times of non-deterministic infinite time Turing machine computations. In particular we observe that there is a Uniform Bounding Lemma which states that if any total algorithm halts before the first ordinal admissible in the input x, then there is a recursive ordinal γ by which the algorithm halts on all inputs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect