Undecidability

REGULAR_{TM} = { <M> | M is a Turing Machine and L(M) is regular}.

Q. Prove that REGULAR_{TM} is undecidable.

Solution. We will use the fact that A_{TM} = { <M,w> | M is a Turing machine and M accepts w} is undecidable.

Assume, for the sake of contradiction, that REGULAR_{TM} is decidable.

We will construct a Turing machine, M' such that L(M') is regular if and only if M accepts w.

Let M' operate as follows on input x:-

If x is of the form 0^n1^n, then “Accept”.

Else, simulate M on w, and “Accept” if M accepts w.

This ends the construction of M'.

We can see that :-

1. If M accepts w, then L(M') is the set of all strings, and hence, is regular.

2. If M does not accept w, then L(M') is not regular.

That is, L(M') is regular iff M accepts w. \therefore  If REGULAR_{TM} is decidable, then A_{TM} is decidable.

Contradiction.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: