In their arXiv preprint, "Infinite Time Turing Machines" ([arXiv:math/9808093v1](https://arxiv.org/abs/math/9808093v1) [math.LO] 21 Aug 1998) Hamkins and Lewis state the Lost Melody Theorem for ITTM's as follows:



> 
> Lost Melody Theorem 4.9 [pg. 28 in the preprint above—my comment]. There is a real, $c$, such that {$c$} is decidable, but $c$ is not writable. Consequently, there is a constant, total function which is not computable, but whose graph is nevertheless decidable: $f(x)= c$.
> 
> 
> 


Consider also the following quote from the Carl, Schlicht, and Welch paper, "[Recognizable Sets and Woodin Cardinals: Computations Beyond the Constructible Universe](https://doi.org/10.1016/j.apal.2017.12.007)" (pg. 5 in my copy):



> 
> A typical phenomenon for infinitary computations is the existence of sets of ordinals which are recognizable, but not computable. Following [HL00][that is, the Hamkins /Lewis paper just referred to—my comment], we call such sets *lost melodies*.
> 
> 
> 


Finally, to return to the Hamkins/Lewis paper, consider further their motivation for the Lost Melody Theorem found in the little paragraph directly above the statement of the theorem:



> 
> Like the previous theorem, the next identifies a surprising divergence [as in 'not in'?—my comment] from the classical theory [the "classical theory" presumably being ordinary recursion theory—my comment]. The real $c$ in the theorem is like a forgotten melody that you cannot produce on your own but which you can recognize when someone sings it to you.
> 
> 
> 


My motivation for the question hangs both on this metaphor and on the fact two groups of authors seem to claim that such 'lost melodies' are an infinitary phenomenon, yet I would wager that many (including myself) have had times where we could not remember some melody but recognized it when hummed (or sung) back to us (a decidedly finite phenomenon). Indeed, if one assumes that the human brain can be instantiated by a Turing machine (otherwise we would have to accept J.R. Lucas-like arguments as valid), there would have to be an analogue of the Lost Melody Theorem in ordinary recursion theory, wouldn't there (perhaps it would be a type of computational-complexity theorem)?



Is there an analogue of the Lost Melody Theorem in ordinary recursion theory and if not, why not?
Note that reals have an odd "double role" in the ITTM setting; besides being sets of natural numbers, they are also individual inputs to type-$2$ functionals. In the latter role they are analogous to *natural numbers* in ordinary recursion theory; more accurately, though, IT recursion theory simply has a distinct "flavor" from classical recursion theory in that it is fundamentally $3$-typed (numbers, reals, and functionals) as opposed to $2$-typed (numbers and reals).


Instead, IT recursion theory is more analogous to **(effective) descriptive set theory** (indeed it can be thought of as part of descriptive set theory). And here we do indeed have a lost melody theorem, in the guise of **singletons**. A $\Pi^0\_2$ singleton, for example, is a real which is the unique real satisfying some $\Pi^0\_2$ formula. Note that this formula has a *real*, as opposed to *number*, variable; $\Pi^0\_2$ singletons can in general be vastly more complicated than $\Pi^0\_2$ sets. For instance, for every ordinal notation $n\in\mathcal{O}$ the real $H\_n(0)$ is a $\Pi^0\_2$ singleton, even when $n$ is a notation for an ordinal much bigger than $2$. In this sense, recognizing a $\Pi^0\_2$ singleton is in general vastly easier than building it.




---


Meanwhile, I don't buy at all the argument that humans actually experience a lost melody phenomenon in any meaningful way; the name of the theorem is simply a vague analogy, and *neither* aspect of it stands up to scrutiny:


* I may *never* be able to confidently recognize the original melody when played back to me. If you've ever tried to track down "that one performance" of a particular piece of music, you'll know what I mean: you find a wide spectrum of similar-sounding melodies, and the correct one doesn't stand out particularly well.
* Conversely, I *may* be able to brute-force-search for it in principle. Nobody would ever *actually* enumerate all possible melodies of the appropriate length, but that's not an obstacle in principle. And in fact sometimes we do do something close to this: if I don't exactly remember a melody, I can sit down at a piano and try to bang out various combinations of notes until I get it right. As long as I remember some things about the *form of* the melody, I have a decent chance of pulling this off.


