Is there an analogue of the Lost Melody Theorem in ordinary recursion theory and if not, why not? In their arXiv preprint, "Infinite Time Turing Machines" (arXiv: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" (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)?
 A: 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.
A: It was already mentioned that the "domain enumeration" property of classical Turing machines ban them from having lost melodies right away. But (as was already hinted in the comments) when one introduces complexity bounds, the picture might change; there could be "ultrafinitist" lost melodies, so to say. The reason why "exhaustively hum all melodies until you hear the right one" would not work then is that, if you actually tried that, you would probably die before you get it right.
For example, I guess there could be natural numbers s, m such that some Turing machine with s states can recognize m, but no Turing machine with s states can compute m. (Of course, by the "enumerate and check everything"-argument, m will be computable with s+c many states, for some constant c that does not depend on m and s.) Similarly, one might have something like this for program length instead of state number. But this "lost melody" would probably strongly depend on details of the machine architecture and thus not be very interesting. If you limit the number of states, there could also be a natural number m such that {m} is semi-decidable by a program with that many states that halts in s many steps on input m, but it takes much longer for such a program to write m. (This possibility is mentioned at the end of https://arxiv.org/pdf/1407.3624.pdf ). But I would expect all of this to depend very much on the particular machine architecture, and thus not be very appealing.
