0
$\begingroup$

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

$\endgroup$
9
  • 1
    $\begingroup$ 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? $\endgroup$ Aug 18, 2021 at 18:55
  • 1
    $\begingroup$ The set $W_x$ consists of all inputs on which the Turing machine encoded by $x$ halts. $\endgroup$ Aug 18, 2021 at 18:57
  • 1
    $\begingroup$ 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$. $\endgroup$ Aug 18, 2021 at 20:32
  • 1
    $\begingroup$ @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 ? $\endgroup$ Aug 18, 2021 at 20:51
  • 1
    $\begingroup$ Right, that's one way of solving this. $\endgroup$ Aug 18, 2021 at 23:47

1 Answer 1

0
$\begingroup$

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$

$\endgroup$

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.