Let $\varphi_e$ denote the p.c. function computed by the Turing Machine with code number $e$. I am looking at the set $M = \lbrace x : \neg (x < y)[\varphi_x=\varphi_y] \rbrace$. This set is clearly infinite. Now $M$ has an infinite c.e. subset if and only if there exists a one-to-one computable function $f$ such that $f(\omega) \subseteq M$. But it seems like the Recursion Theorem should furnish a fixed point $x_0$ such that $\varphi_{x_0}=\varphi_{f(x_0)}$ and $x_0 < f(x_0)$. This would mean that $M$ has no infinite c.e. subset, but I cannot seem to prove this. Can anyone help me resolve this question in either direction?
[Math] Infinite set with/without infinite c.e. subsets
computability-theory
Related Solutions
No, we can construct a computable tree with no computable paths such that there is a probabilistic Turing machine which with nonzero probability constructs a path.
The basic idea is this: kill off a small-measure subset of $2^\omega$ containing all computable reals, and pick our branch completely at random (so that our probability of success is exactly the measure of the complement of the set we kill off).
Here's one way to do it. Call a sequence $\sigma\in 2^{<\omega}$ dangerous if for some $e$, we have $\Phi_e(n)[\vert\sigma\vert]\downarrow=\sigma(n)$ for all $n<4^e$. Note that the set of dangerous strings is computable, and that every infinite computable sequence extends a dangerous string.
Now let $T$ be the tree of all non-dangerous strings, and use the probabilistic Turing machine which simply picks a random extension without thinking at all. Since the function $e\mapsto 4^e$ grows sufficiently fast, we have a positive probability of getting a path. However, $T$ clearly has no computable paths.
Re: question $2$, I don't have an answer but here's a quick observation: we can defeat the coin-flipping algorithm. (I suspect the answer to 2 is yes, by diagonalizing against probabilistic Turing machines - kill nodes to shrink the measure of branches built by a given machine - but I don't immediately see the details.)
Say $\sigma$ is risky if for some $e$, we have
$\Phi_e(2^n)[\vert\sigma\vert]\downarrow=\sigma(2^n)$ for all $n<4^e$, or
for some $m$ not of the form $2^k$ we have $\sigma(m)\not=1$ (say).
Again, take the tree of non-risky strings. Note that every computable sequence extends a risky string, so this tree has no computable paths, and every sequence with only non-risky initial segments has asymptotic-density-$1$ many $1$s, so the set of paths is null.
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.
Best Answer
I assume that you mean $M=\{ y\mid \neg\exists x\lt y\ \varphi_x=\varphi_y\}$. And in this case, the argument you've already given seems to solve the problem. If $M$ had an infinite c.e. subset $A$, then let $f(n)$ be the first element enumerated into $A$ above $n$. So $n\lt f(n)\in A\subset M$ for every $n$. By the Kleene recursion theorem, as you mentioned, there is $x_0$ with $\varphi_{x_0}=\varphi_{f(x_0)}$, but as $f(x_0)\in A\subset M$ and $x_0\lt f(x_0)$, this contradicts the definition of $M$. Thus, $M$ can have no infinite c.e. subset.