Semi decidability proof

Question

I'm studying for my theory of computation exam and came accross the following question:

Construct an appropriate Turing machine for the following language and prove or disprove it's semi-decidability:

$A := \{w \in \{0, 1\}^*\ |\ \exists x \in \{0, 1\}^* .f_w(x) = |x| \}$

The way I interpret this is that $A$ consists of all TM encodings $w$ which describe a TM $M'$ that for at least one input $x\in\{0, 1\}^*$ outputs the length of $x$. So now I try to come up with a TM $M$ for $A$, this TM should simulate TM encodings $w\in\{0, 1\}^*$ and check whether the TM $M'$ it simulates computes $f(x) = |x|$ for at least one $x$. In order to do this, $M$ would have to try computing all possible inputs for $M'$ and check if $f(x) = |x|$ is true for at least one input, if such an input $x$ exists than $M$ will terminate and accept the encoding of $M'$ which is $w$. If such an input $x$ doesn't exist then $M$ will keep simulating $M'$ forever and therefore won't halt. Hence I conclude that $A$ is semi decidable since it halts if a solution exists and otherwise doesn't.

Does this make any sense?

Also, since I need to prove/disprove $A$'s semi-decidability, I conclude that $A$ is not decidable (Rice's theorem), is that correct?

Answer 1

What you have to do is systematic search for a string $x$ such that $f_w(x) = |x|$ or in other words $M_w(x) = |x|$. Given $w$ your TM $M$ should try ALL input strings $x$, not just to simulate $M_w$ on a single $x$.

If you wait $M_w(x)$ until it halts then you ($M$) may stuck in case $M_w$ does not halt on $x$. So, that option is not possible.

One possible way is to systematically try all pairs $(x,i)$ which means "simulate $M_w(x)$ for $i$ steps". Your strings may be encoded an put in one to one correspondence with integers. So a pair $(i,j)$ means simulate $i$th string $s_i$ for $j$ steps on $M_w$. Each time you simulate $(i,j)$ you check if after $j$ steps $M_w(s_i)$ halts and if yes then compare its output with $|s_i|$. If the output is equal to $|s_i|$ then ACCEPT and halt, otherwise you go to the next pair $(i,j)$. Thus so on until you ($M$) find a pair $(i,j)$ such that $M_w(s_i)$ halts after $j$ steps and its output is equal to $|s_i|$.

In other words, you simply give a chance to your machine $M$ to run on every $x$ for a certain number of steps, and after running for the certain number of steps you check if it halts and if it halts you compare its output with the input length.

Now to prove that it is semi-decidable notice that if indeed there is $x$ such that $f_w(x) = |x|$ then there are integers $m$ and $n$ such that $s_m = x$ and $M_w(s_m)$ halts after $n$ steps. You will eventually find that pair $(m, n)$ after a finite number of steps since you systematically try all pairs $(i,j)$. If such pair does not exist at all then your machine never halts and will run forever. Thus that set is semi-decidable. Similar post