Question

Let $J=\left\{w\right|$either$w=0x$for some,$x\in A_{TM}$ or$w=1y$for some $y\in \overline{A_{TM}}\}$. Show that neither Jnor$\overline{J}$is Turing-recognizable.

Short answer

Both J and $\overline{J}$ are not Turing Recognizable.

Step-by-step solution

 Introduction to Turing Recognizable

A language L is said to be Turing Recognizable if and only if there exist any Turing Machine (TM) which recognize it i.e., TM halt and accept strings belong to language L and will reject or not halt on the input strings that doesn’t belong to language L.

 Proving neither J nor J are Turing Recognizable

In order to prove J and $\overline{J}$both are not Turing-Recognizable,

First we will show that$A_{TM}{⩽}_{m}J$.

To prove this, we will construct TM Q

$Q=oninput\left(M,w\right)$

Write symbol 0 and $\left(M,w\right)$then in the tape and make it halt. We have:

localid="1662181827790"

So, we are able to obtain a reduction mapping of A_TM to J .

Now, we will show that$A_{TM}{⩽}_m\overline{J}$ . For this we will construct a Turing Machine R:
$R=oninput\left(M,w\right)$

Write symbol 1 and then $\left(M,w\right)$in the tape and make it halt. We have:

This is similar to:

So, we are able to obtain a reduction mapping of A_TM to J.

Sincelocalid="1662181817969" $A_{TM}{\le }_{m}J\Rightarrow {\le }_m\overline{J}$,. This signifies that $\overline{J}$ is not Turing-recognizable as A_TM is not Turing-recognizable.

In same way, since. This signifies that J is not Turing recognizable.

Hence both J and $\overline{J}$are not Turing-recognizable.