# Uncomputability of least member selection

I want to show that there is no TM $$f$$ such that whenever $$W_x$$ is nonempty then $$f(x)$$ is defined and is the least member of $$W_x$$, Where $$W_x=\{w:w \in \Sigma^{*}\text{ and } M_x \text{ on }w \text{ Halts}\}$$

Usually when I want to show that such a problem is not member of RE, I use Rice's theorem, diagonalization, the recursion theorem, or I show that if such a problem is computable then $$\overline{HP}$$ is computable. But I think I did not fully understand this question. (Edit: Before i read comments i did not know what is the definition of $$W_x$$)

• If $W_x$ is not defined in the problem statement, it's probably in the index or list of symbols, if the book has those. Have you checked there? Aug 18, 2021 at 18:55
• The set $W_x$ consists of all inputs on which the Turing machine encoded by $x$ halts. Aug 18, 2021 at 18:57
• The problem is to show that there is no Turing machine $M$ such that if $W_x \neq \emptyset$, then $M$ halts on $x$ and returns $\min W_x$. Aug 18, 2021 at 20:32
• @YuvalFilmus Then we can build a TM $T$ s.t for every input $x \geq 2$ accept and for $x=1$ simmulate $M$ on $w$ if it halts accept. Hence if $f(T)=1$ then $\langle M,w \rangle \in HP$ otherwise $\langle M,w \rangle \notin HP$ , am i right ? Aug 18, 2021 at 20:51
• Right, that's one way of solving this. Aug 18, 2021 at 23:47

According to the comments, The problem is:

Show that there is no Turing machine $$M_f$$ such that if $$W_x \neq \emptyset$$, then $$M_f$$ halts on $$x$$ and returns $$\min W_x$$

To solve this, We assume $$f \in RE$$ then we show $$HP\in R$$ which is a contradiction.

Now we build a TM $$HP_{TM}$$ such that $$HP_{TM}(\langle M,w \rangle)=1 \Leftrightarrow M \text{ halts on }w$$ and we use $$M_f$$ to build that.

$$HP_{TM}(\langle M,w\rangle) = \left\{ \begin{array}{ll} \text{1- Build a new machine }T (x) = \left\{\begin{array}{ll} \text{If }(x\geq2)\text{ then ACCEPT}\\ \text{If }(x=1)\text{ then do:}\\ \hspace{14pt} \text{1- Simulate }M\text{ on input }w\\ \hspace{14pt} \text{2- ACCEPT}\\ \end{array}\\ \right.\\ \text{2- Compute }M_f(T)\\ \text{3- If }M_f(T)=1\text{ then ACCEPT}\\ \text{4- Otherwise REJECT} \end{array}\right.$$

Clearly we can build a TM $$T$$ in finite amount of time in Stage 1. Observe that $$W_t \neq \emptyset$$ and $$1 \in W_t \Leftrightarrow \langle M,w\rangle \in HP$$ hence $$HP_{TM}$$ decides $$HP$$ therefore $$HP \in R$$. We know $$HP \notin R$$ so this is a contradiction and we can conclude $$f\notin RE$$.

$$\blacksquare$$