Showing that $L$ is recognizable

273 Views Asked by At

Let $L$ be the language of all the words with the shape $<M_1,M_2,w>$ such that $M_1$ and $M_2$ are turing muchines that both accepts the word $w$.

Show that $L$ is recognizable

I thought to build a new machine $M_3$ such that $M_3$ will accept $L$, any ideas how can I build such a machine?

1

There are 1 best solutions below

0
On BEST ANSWER

A possible construction for $M_3$ would be:

$M_3= \;$On input $<M_1, M_2, w>$
$\quad\quad\quad\quad$ simulate $M_1$ on $w$
$\quad\quad\quad\quad$ simulate $M_2$ on $w$
$\quad\quad\quad\quad$ if both $M_1$ and $M_2$ accept $w$
$\quad\quad\quad\quad\quad$ accept
$\quad\quad\quad\quad$ else
$\quad\quad\quad\quad\quad$ reject

$M_3$ is not a decider because if either $M_1$ or $M_2$ loops, then $M_3$ will loop