Conference Paper/Proceeding/Abstract 978 views 263 downloads
Computability on the Countable Ordinals and the Hausdorff-Kuratowski Theorem (Extended Abstract)
Arno Pauly 
Mathematical Foundations of Computer Science 2015, Volume: 9234, Pages: 407 - 418
Swansea University Author:
Arno Pauly
-
PDF | Accepted Manuscript
Download (398.55KB)
DOI (Published version): 10.1007/978-3-662-48057-1_32
Abstract
While there is a well-established notion of what a computable ordinal is, the question which functions on the countable ordinals ought to be computable has received less attention so far. We propose a notion of computability on the space of countable ordinals via a representation in the sense of com...
| Published in: | Mathematical Foundations of Computer Science 2015 |
|---|---|
| ISBN: | 978-3-662-48056-4 978-3-662-48057-1 |
| ISSN: | 0302-9743 1611-3349 |
| Published: |
Berlin
Springer
2015
|
| Online Access: |
Check full text
|
| URI: | https://cronfa.swan.ac.uk/Record/cronfa36019 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Abstract: |
While there is a well-established notion of what a computable ordinal is, the question which functions on the countable ordinals ought to be computable has received less attention so far. We propose a notion of computability on the space of countable ordinals via a representation in the sense of computable analysis. The computability structure is characterized by the computability of four specific operations, and we prove further relevant operations to be computable. Some alternative approaches are discussed, too. As an application in effective descriptive set theory, we can then state and prove computable uniform versions of the Lusin separation theorem and the Hausdorff-Kuratowski theorem. Furthermore, we introduce an operator on the Weihrauch lattice corresponding to iteration of some principle over a countable ordinal. |
|---|---|
| College: |
Faculty of Science and Engineering |
| Start Page: |
407 |
| End Page: |
418 |