Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-16T06:07:30.491Z Has data issue: false hasContentIssue false

OPTIMAL RESULTS ON RECOGNIZABILITY FOR INFINITE TIME REGISTER MACHINES

Published online by Cambridge University Press:  22 December 2015

MERLIN CARL*
Affiliation:
FACHBEREICH MATHEMATIK UND STATISTIK UNIVERSITÄT KONSTANZ 78457 KONSTANZ GERMANYE-mail: merlin.carl@uni-konstanz.de
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Exploring further the properties of ITRM-recognizable reals started in [1], we provide a detailed analysis of recognizable reals and their distribution in Gödels constructible universe L. In particular, we show that new unrecognizable reals are generated at every index $\gamma \, \ge \,\omega _\omega ^{CK}$. We give a machine-independent characterization of recognizability by proving that a real r is recognizable if and only if it is ${\Sigma _1}$-definable over ${L_{\omega _\omega ^{CK,\,r}}}$ and that $r\, \in \,{L_{\omega _\omega ^{CK,\,r}}}$ for every recognizable real r and show that either every or no r with $r\, \in \,{L_{\omega _\omega ^{CK,\,r}}}$ generated over an index stage ${L_\gamma }$ is recognizable. Finally, the techniques developed along the way allow us to prove that the halting number for ITRMs is recognizable and that the set of ITRM-computable reals is not ITRM-decidable.

Information

Type
Articles
Copyright
Copyright © The Association for Symbolic Logic 2015