Question

Show that if A is Turing-recognizable and $A{⩽}_m\overline{A}$, then A is decidable.

Short answer

It is proved that A is decidable.

Step-by-step solution

Defining Turing Recognizability and Decidability

Turing Recognizability

A language Lis 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.

Decidability

A language is called ‘Decidable’ if it’s able to construct a Turing machine which accepts and halts on every string.

Proving A as decidable

Let’s assume that $A{⩽}_m\overline{A}$:, then $\overline{A}{⩽}_{m}A$by similar mapping reduction.

Now, it’s given that ifAis Turing-recognizable.

From this, it is also clear thatAisCo-Turing-recognizable.

SinceAis Turing-recognizable and Co-Turing-recognizable.

Therefore, A is decidable.