91Ó°ÊÓ

A problem is undecidable if no Turing Machine exist which will halt in finite amount of time.

Let us assume P is a decidable language and let Turing Machine $R_P$ that decides P

.

We will design Turing Machine s that will decide $A_{TM}$by the use of$R_P$. First, let T' be a Turing Machine that always rejects for any input.

This means: $L\left(T\text{'}\right)=âˆ\dots$.

For clarity we will assume that so that we not proceed with $\stackrel{¯}{P}$ instead of P if . Because P is not trivial, so there exists a Turing Machine T with.

Now we will design Turing Machine S using $R_P$ because $R_P$

s= on input$\left(M,w\right)$

$M_w$=on input x $M_w=oninputx$$M_w=oninputx$

Run M on w .

If it halts and rejects, reject.

If it accepts, proceed to stage 2.

Run T on x . If it accepts, accept.

If YES, accept

Else

If NO, reject.

Turing Machine $M_w$ runs T if M accepts w .

Hence

• $L\left(M_W\right)=L\left(T\right)$if M accepts w
• If reject then $L\left(M\right)=âˆ\dots$.

Therefore, $M_W∈P$if and only if M accepts w.

But $A_{TM}$ is undecidable, so s which is made similar to $R_P$ cannot decide P .

Thus, P is undecidable.