7
$\begingroup$

Definition A set of reals $A$ is said to be ittm-eventually-semi-decidable if there is an Infinite Time Turing Machine programme $P_e$ so that $x\in A$ iff $P_e(x)$ has converged on “1” on its output tape from some point in time onwards.

(The difference with this concept and that of the halting “ittm-semi-decidable” is that the machine is not required to formally halt, but only to have settled output tape.)

Question 1: If $\{x\}$ is an eventually semi-decidable singleton, is $x\in L_{\Sigma^x}$?

Background: $\Sigma^x$ comes from the $\lambda$-$\zeta$-$\Sigma$ theorem, here relativised to the parameter $x$: thus $\lambda^x$-$\zeta^x$-$\Sigma^x$ is the lexicographically least triple so that $L_{\lambda^x}[x] \prec_{\Sigma_1}L_{\zeta^x}[x]\prec_{\Sigma_2}L_{\Sigma^x}[x]$. (See [1].) In the question $\Sigma^x$ could be replaced by $\lambda^x$. (It is easy to see that for any $x$, $x\in L_{\Sigma^x} \Rightarrow x \in L_{\lambda^x}$.) Thus to be a singleton set of this kind is to be able to compute your $L$-rank. For the stricter, so halting, semi-decidable singleton question (thus with the word ‘eventually’ deleted), the answer is positive. Thus semi-decidable singletons are ‘fast’ in that they are quickly constructible. Thus $F=\{x\mid x\in L_{\lambda^x}\}$ ( $= \{x\mid x\in L_{\zeta^x}\}$ ) is the analogue in ittm theory of the quickly constructed reals of Kleene recursion: $Q=\{ x\mid x\in L_{\omega_1^{ck}}\}$. Just as $Q$ is the largest thin $\Pi^1_1$ set so reals, so is $F$ the largest thin semidecidable set of reals.

However there are sound reasons for considering the notion of eventually decidable, and ev. semi-decidable where we do not formally require the machines to halt, but have nevertheless given some settled output, as more fundamental: the machine architecture naturally produces these eventually writable reals on their tapes; the analysis of the writable, so computable, sets of integers or reals requires a prior analysis of the eventually writable ordinals &c. to produce the basic $\lambda$-$\zeta$-$\Sigma$ theorem. In short to study the writable sets is to study the eventually writable ones. The eventually writable sets of integers/reals form Spector classes etc., etc. which properly contain the halting writable counterparts. Moreover the notion of eventually writable matches up with other notions of “quasi-inductive” in the literature. (A similar comment could be made for OTM's as well.)

Question 2: Is there are a largest thin eventually semi-decidable set of reals?

Note: for Kleene recursion, the notion of semi-decidable is $\Pi^1_1$, and it is well known that the $\Pi^1_1$ singletons appear cofinally in $\sigma$ - the least stable ordinal. Hence so do the ittm eventually semidecidables, and by a simple reflection argument they are also all in $L_\sigma$.

Question 3: Is there a reasonable pointclass $\Delta$ so that every eventually semi-decidable set of reals contain a $\Delta$ singleton?

This would provide a Basis Theorem, if true. If we stick to the stricter notion of halting semi-decidable sets of reals, each of these contains a halting semi-decidable singleton.

[This was edited from an earlier version of Question 3 when we had asked if taking Delta as the eventually semi-decidable class itself formed such a basis. However a negative answer was already known but forgotten by this writer (see [2] where it is shown that the Uniformisation Property fails for the eventually semi-decidable sets - although it and the Scale Property hold for the halting semi-decidable class).]

[1] P.D. Welch: Characteristics of discrete transfinite Turing machine models: halting times, stabilization times, and Normal Form Theorems in Theoretical Computer Science, vol. 410, Jan. 2009, 426-442 https://dx.doi.org/10.1016/j.tcs.2008.09.050

https://www.sciencedirect.com/science/article/pii/S0304397508007275?via%3Dihub

[2] Sy Friedman, P.D. Welch: Hypermachines in Journal of Symbolic Logic, 76, No.2, June 2011, 620-636. https://www.maths.bristol.ac.uk/~mapdw/Sigma-final2.pdf

$\endgroup$
3
  • $\begingroup$ I vaguely recall seeing a general theorem which in particular would give a positive answer to 2 under large cardinals (maybe in Martin's "The largest countable this, that, and the other") - does that sound plausible, or is my memory way off? $\endgroup$ Commented Jul 22, 2021 at 19:18
  • $\begingroup$ @Noah: if $\omega_1^L$ is countable then somewhat trivially the union of the ev. semi-decidable thin sets is countable hence thin, since the ev.semi-decidable sets are provably $\Delta^1_2$, and hence, if thin, are all contained in $L$. But even that does not quite seem to say that that union is ev.semi-decidable itself (however the union is ev. semi-decidable in a constructible real parameter.) We could get rid of that param. if we knew every thin ev. semi-decid. set $A\subset F$, which the question about the singletons is a first step towards. $\endgroup$ Commented Jul 22, 2021 at 20:04
  • $\begingroup$ What is a proof that the answer to Question 1 is positive when we drop the 'eventually'? $\endgroup$
    – Johan
    Commented Mar 2 at 15:16

0

You must log in to answer this question.