Optimal Results on ITRM-recognizability
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2013
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913138028314624 |
|---|---|
| author | Carl, Merlin |
| author_facet | Carl, Merlin |
| contents | Exploring further the properties of ITRM-recognizable reals, we provide a detailed analysis of recognizable reals and their distribution in Gödels constructible universe L. In particular, we show that, for unresetting infinite time register machines, the recognizable reals coincide with the computable reals and that, for ITRMs, unrecognizables are generated at every index bigger than the first limit of admissibles. We show that a real r is recognizable iff it is $Σ_{1}$-definable over $L_{ω_ω^{CK,r}}$, that $r\in L_{ω_ω^{CK,r}}$ for every recognizable real $r$ and that either all or no real generated over an index stage $L_γ$ are recognizable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1306_5128 |
| institution | arXiv |
| publishDate | 2013 |
| record_format | arxiv |
| spellingShingle | Optimal Results on ITRM-recognizability Carl, Merlin Logic Exploring further the properties of ITRM-recognizable reals, we provide a detailed analysis of recognizable reals and their distribution in Gödels constructible universe L. In particular, we show that, for unresetting infinite time register machines, the recognizable reals coincide with the computable reals and that, for ITRMs, unrecognizables are generated at every index bigger than the first limit of admissibles. We show that a real r is recognizable iff it is $Σ_{1}$-definable over $L_{ω_ω^{CK,r}}$, that $r\in L_{ω_ω^{CK,r}}$ for every recognizable real $r$ and that either all or no real generated over an index stage $L_γ$ are recognizable. |
| title | Optimal Results on ITRM-recognizability |
| topic | Logic |
| url | https://arxiv.org/abs/1306.5128 |