1
$\begingroup$

Consider the definition of "lost melody" given by Merlin Carl in his arXiv preprint, "The Lost Melody Phenomenon" (arXiv: 1407.3624v5 [math.LO] 16 Mar 2015):

A lost melody is a real number $x \subseteq \omega$ which is recognizable, i.e., for some ITTM program $P$, the the computation of $P$ with $y$ on the input tape (which plays the role of a real oracle for an ITTM) is defined for all $y$ and outputs 1 iff $y = x$ and otherwise outputs 0, but not computable, i.e., no program computes the characteristic function of $x$.

Furthermore, Prof. Carl understands the notion of ITTM as follows:

These machines, which are basically classical Turing machines equipped with transfinite running time….

Hamkins and Lewis define the conditions under which ITTMs can be considered "ordinary Turing machines" and in such manner show that classical computability theory can be deemed a subtheory of ITTM-computability theory:

Thus, restricting to the case of finite input and time, a function $f: 2^{\lt {\omega}} \rightarrow 2^{\lt {\omega}}$ is $\omega$-computable exactly when it is computable in the Turing machine sense.

With this in mind I will rewrite Prof. Carl's definition without mentioning ITTM's:

A lost melody is a real number $x \subseteq \omega$ which is recognizable, i.e., from some Turing machine program $P$, the computation of $P$ with $y$ on the input tape (which plays the role of a real oracle for a Turing machine) is defined for all $y$ and outputs 1 iff $y = x$ and otherwise outputs 0 but not computable, i.e., no Turing machine program computes the characteristic function of $x$ [note that such oracles are standard in classical computability (recursion) theory—my comment (see Hartley Rogers Jr's text, chapter 9.2, "Turing Machines with Auxiliary Tapes", pg. 130)].

All that remains is to note that both $\{x \mathrel| \text{$\varphi_{x}$ is total}\}$ and its complement are both productive sets, and not recursively (computably) enumerable (which means, to me at least, not writable by any recursive function).

So can the singleton $\{\{x \mathrel| \text{$\varphi_{x}$ is total}\}\}$ be decidable by Prof. Carl's oracle (restricted to classical recursion theory)?

I believe it can for the following reason: i) if one assumes that the oracle in question has multiple oracle tapes—$2^{\aleph_0}$ of them in fact (one tape for each set of natural numbers)—when one compares the elements of $x$ with the elements of $y$ by the oracle, it will, in fact, show that $y \neq x$ in a finite number of steps, but only show that $y = x$ if the oracle machine does not halt. Now if one wishes to consider the oracle machine an ITTM (for the reason that if $y = x$ the the oracle machine does not halt), by the limsup rule the oracle machine must output a 1, but this is a trivial use of an ITTM.

$\endgroup$

1 Answer 1

2
$\begingroup$

If we disregard the model of computation we want to use, a lost melody is a decidable singleton $\{x\}$ such that the point $x$ is non-computable. Classical computability theory cannot admit any lost melodies in $2^\omega$ because there are no decidable singletons in the first place, and it cannot admit lost melodies in $\mathbb{N}$ because there are no non-computable points.

We could weaken the requirement (as you may be doing in your question), and only ask for $\{x\}$ to be $\Pi^0_1$, meaning that we can recognize the complement of $\{x\}$ but not necessarily $\{x\}$ itself. With $2^\omega$ as ambient space, this still doesn't give us any examples. However, if use $\omega^\omega$, then we see that every hyperarithmetical Turing degree has a representative $x$ such that $\{x\}$ is $\Pi^0_1$.

Another way to get lost melodies without using a more powerful model of computation would be to move towards computable analysis, and to use general represented spaces as ambient spaces. This allows us trivial constructions such as considering any singleton $\{p\}$ for $p \in 2^\omega$ as ambient space in its own right, and since $\{p\}$ is trivially a decidable subset of $\{p\}$, we have plenty of lost melodies here. On the other hand, "nice" represented spaces would generally be computably separable, which immediately implies that every computably open (ie $\Sigma^0_1$) singleton consists of a computable point.

$\endgroup$
5
  • $\begingroup$ Thank you for your answer--it is both interesting and helpful. However, your statement, "If we disregard the model of computation we want to use, a lost melody is a decidable singleton {$x$} such that the point $x$ is non-computable", might be a little too general (though it is a very interesting question in its own right , and in that sense, helpful). As I understand it (and if I am misunderstanding something here, please let me know) Prof. Carl's definition of a lost melody is that the non-computable point $x$'s singleton {$x$} is decidable by an oracle, whence my question. $\endgroup$ Sep 9, 2021 at 20:27
  • $\begingroup$ @ThomasBenjamin You are misunderstanding him. The reason why he is mentioning oracles is that a input from $2^\omega$ is treated akin to how an oracle would be used in the context of ordinary computability theory for functions of type $f : \mathbb{N} \to \mathbb{N}$. $\endgroup$
    – Arno
    Sep 9, 2021 at 20:36
  • $\begingroup$ (cont.)(Just to let you know, that seems to me a kind of cheat because one can always find an 'oracle' to decide the 'undecidable' (as in degree theory---thank you for hour last comment). In that case, in which context (you mention two in your answer) can {{ $x$|$\varphi_{x}$ total}} be considered (if at all) a 'lost melody'? $\endgroup$ Sep 9, 2021 at 20:41
  • 1
    $\begingroup$ @ThomasBenjamin Oracles don't trivialize everything! If you were to allow to use oracles for $\{x\}$, then you would be asking for non-computable isolated points in some space. The answer remains: "Natural" spaces don't have them, but you make them happen if you want. $\endgroup$
    – Arno
    Sep 9, 2021 at 20:47
  • $\begingroup$ Very interesting and helpful. Thank you. $\endgroup$ Sep 9, 2021 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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