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?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top