0
$\begingroup$

The question is in the title. This question is in response to the following paragraph found at the end of Prof. Hamkins' answer to my MathOverflow question, Are ITTM's necessary to compute Turing's "computable numbers" and what dos that mean for ordinary recursion theory:

Regarding infinite time Turing machines, these are concerned frankly with much larger ordinals than $\omega$, and their consequences and effects are realized on a much larger scale.

$\endgroup$
3
  • 2
    $\begingroup$ The question requires clarification. What does it mean for 'lost melodies' to occur in an ordinal? I am familiar with the idea of lost melodies from the Hamkins-Lewis paper but I still can't make sense of what you are asking. $\endgroup$ – Wojowu Jun 3 at 21:22
  • $\begingroup$ @Wojowu: Your interpretation of my my question in your answer is correct. Thank you very much. $\Sigma$ $=_{df} $sup{$\beta$| $\beta$ has an accidently writable ordinal}, correct? $\endgroup$ – Thomas Benjamin Jun 7 at 20:54
  • $\begingroup$ Yes, that's right. $\endgroup$ – Wojowu Jun 7 at 21:03
4
$\begingroup$

I interpret this question as asking, what is the first ordinal $\alpha$ such that there is some lost melody (in the sense of Hamkins-Lewis Theorem 4.9) in $L_\alpha$.

The answer is $\alpha=\Sigma+1$ (or $\Sigma+\omega$ if you really insist on it being limit). Indeed, the argument in Theorem 4.9 of the paper produces a lost melody inside $L_{\beta+1}$, where $\beta$ is the least ordinal with the following property: $\beta$ is countable inside $L_{\beta+1}$, and every ITTM either halts or repeats by time $\beta$. From Welch's work we can deduce $\beta=\Sigma$: indeed, by the argument in Corollary 2.3, every machine repeats by time $\Sigma$, and to see $\Sigma$ is countable in $L_{\Sigma+1}$ we can use the fact that $\Sigma$ is not admissible (Corollary 3.4) to get a definable sequence $\alpha_n$ in $L_\Sigma$ tending to $\Sigma$. The elements $\alpha_n$ are countable (and uniformly so) because we can pick out a bijection to $\mathbb N$ defined by their first occurrence of a real coding $\alpha_n$ in some machine listing all accidentally writeable reals. Therefore $\beta=\Sigma$ and so we have a lost melody in $L_{\Sigma+1}$.

On the other hand, all reals in $L_\Sigma$ are accidentally writeable, since they are computable from accidentally writeable ordinals (as explained in the proof of Theorem 4.9) and accidentally writeable reals can't be lost melodies (since we can list all accidentally writeable reals and check them one by one).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.