Turing Computations on Ordinals

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We define the notion of ordinal computability by generalizing standard Turing computability on tapes of length $ω$ to computations on tapes of arbitrary ordinal length. We show that a set of ordinals is ordinal computable from a finite set of ordinal parameters if and only if it is an element of Goedel's constructible universe L. This characterization can be used to prove the generalized continuum hypothesis in L.
Submitted to the Bulletin of Symbolic Logic, 20 pages

Keywords

Logic, 03D60, 03E45 (primary) 03D65, 03E10 (secondary)

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/74173

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0502264
 http://arxiv.org/abs/math/0502264

Collections

arXiv