1
$\begingroup$

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)?

Improve this question
$\endgroup$
14
  • 1
    $\begingroup$ Wouldn't a complexity theoretic witness be essentially just P vs NP (or, if you insist the set to be a singleton, UP)? $\endgroup$
    – Wojowu
    Commented Mar 24, 2021 at 17:34
  • 2
    $\begingroup$ "if one assumes that the human brain can be instatiated by a turing machine, there would have to be an analogue of the Lost Melody Theorem in ordinary recursion theory, wouldn't there?" I don't see how that's justified at all. You have a vague analogy with a subjective situation, that doesn't mean it has to be reflected in a strong formal way. (Of course the question is still interesting.) $\endgroup$
    – Noah Schweber
    Commented Mar 24, 2021 at 18:43
  • 1
    $\begingroup$ As noted, you have examples in complexity theory. But in typical recursion theory, the reason you don't have examples is because there is a computable process that enumerates all potential input objects, i.e. all numbers. In the infinite time setting, inputs are reals, and there's no infinite time computable process that enumerates all reals. $\endgroup$
    – Dan Turetsky
    Commented Mar 24, 2021 at 21:18
  • 13
    $\begingroup$ The next time you find yourself unable to remember a melody, just sit down and hum every possible melody in some exhaustive fashion until you recognize the one you're thinking of. $\endgroup$
    – Dan Turetsky
    Commented Mar 24, 2021 at 21:19
  • 1
    $\begingroup$ @DanTuretsky: regarding a possible Lost Melody of yours--with the brute-force method you suggest--how many steps did it take to recover your Lost Melody....? $\endgroup$
    – Thomas Benjamin
    Commented Mar 25, 2021 at 20:57

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ I'm sure it's correct, but it sure reads strangely to someone not familiar with the subject: do you really (har!) mean that real numbers are sets of natural numbers? $\endgroup$
    – LSpice
    Commented Mar 25, 2021 at 22:11
  • 3
    $\begingroup$ @LSpice Yeah, in logic the term "real" gets abused a bit: it's often used to refer to elements of Baire space (= sequences of naturals) or of Cantor space (= binary sequences, equivalently sets of naturals). This is pretty standard usage, unfortunately. $\endgroup$
    – Noah Schweber
    Commented Mar 25, 2021 at 22:29
  • 1
    $\begingroup$ @NoahSchweber: Thank you for the nice answer. It was helpful. By the way, did you use P.D. Welch's "Higher Type Recursion for Transfinite Machine Theory" as background information to aid you in writing your answer? The reason I asked is that Prof. Welch (at least according to the abstract) "replaced" "ordinary Turing computability and inductive definability" with "Infinite Time Turing Machine computability and quasi-inductive definability" because of his claim that a quasi-inductive definition for ittm-theory corresponds to monotone inductive definitions for Kleene's Higher Type $\endgroup$
    – Thomas Benjamin
    Commented Mar 29, 2021 at 20:58
  • 1
    $\begingroup$ @ThomasBenjamin I'm familiar with that paper but I didn't use it specifically. The material in the first paragraph is already covered in the original ITTM paper, and the material in the second paragraph is covered e.g. in Sacks' book. $\endgroup$
    – Noah Schweber
    Commented Mar 29, 2021 at 21:04
  • 1
    $\begingroup$ (cont.) Recursion Theory. Does the notion of quasi-inductive definition allow for 'lost melody theorems" while monotone inductive definitions do not? $\endgroup$
    – Thomas Benjamin
    Commented Mar 29, 2021 at 21:06
2
$\begingroup$

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.

Improve this answer
$\endgroup$
12
  • $\begingroup$ Thank you for the nice answer and for the reference. I find both very helpful. $\endgroup$
    – Thomas Benjamin
    Commented Apr 5, 2021 at 20:55
  • $\begingroup$ I see you mentioned that "the 'domain enumeration ' property of classical Turing machines ban them from having lost melodies right away". Would it then be possible for you to augment your answer with a simple proof of this? That would help to complete your answer and help me see why, for ordinary Turing machines, RECOGNIZABLE = COMPUTABLE. Thank you so much. $\endgroup$
    – Thomas Benjamin
    Commented Apr 7, 2021 at 18:13
  • $\begingroup$ Suppose that P is a program that recognizes a natural number n; i.e., for any natural number k, P(k) halts with output 1 if and only if k=n and otherwise, P(k) halts with output 0. Now just let P run on inputs 0,1,2,... successively; eventually, n will be considered and identified. Then output n. The routine just described computes n; so any recognizable number is computable. $\endgroup$
    – user178295
    Commented Apr 17, 2021 at 19:35
  • $\begingroup$ user178295: Are you familiar with the following theorem: $A$ is infinite and recursively enumerable iff $A$ is recursively enumerable without repetitions ($A$ is recursively enumerable without repetitions if [by definition] $A$ = $range$ $f$ for some $f$ that is recursive and one-to-one). Would you say that non-r.e. sets are not recognizable (I am interested in the lost melody theorem as it pertains to sets of natural numbers, that is, is RECOGNIZABLE = COMPUTABLE as regards sets of natural numbers (0 counts as a natural number))? $\endgroup$
    – Thomas Benjamin
    Commented Apr 19, 2021 at 21:28
  • $\begingroup$ The problem with recognizing sets of natural numbers with a classical Turing machine is that a Turing machine needs to halt in finitely many steps, thus only reading out a finite portion of the oracle. Consequently, not even the empty set is recognizable in this sense. But since you talk about recursive enumerability, you may rather have in mind something like semi-recognizability, i.e., a Turing program that only halts on input x, but no other? The problem, of course, would persist - consider the portion read out by the program and change some bits after that to arrive at a contradiction. $\endgroup$
    – user178295
    Commented Apr 20, 2021 at 7:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .