# Undecidability

July 25, 2010 Leave a comment

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

Q. Prove that is undecidable.

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

Assume, for the sake of contradiction, that is decidable.

We will construct a Turing machine, such that is regular if and only if accepts .

Let operate as follows on input :-

If is of the form , then “Accept”.

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

This ends the construction of .

We can see that :-

1. If accepts , then is the set of all strings, and hence, is regular.

2. If does not accept , then is not regular.

That is, is regular iff accepts . If is decidable, then is decidable.

Contradiction.