Question

3b. Consider the language FIN = { | M is a Turing machine and L(M) is finite }. Prove FIN is not decidable.

Answer 1

Answer is as follows :

We have

FIN = { | M is a Turing machine and L(M) is finite }

So it satisfy the following properties :

• FIN_TM is a language of Turing Machines.
• If M₁ ≡ M₂ (ie L(M₁) = L( M₂)), then either both M₁ and M₂ are in FIN_TM or both are not.
• There are TMs M₁ and M₂, such that M₁ ∈ FIN_TM and M₂ ∉ FIN_TM.

So let  L be a language over Turing machines. Assume that L satisfies the following properties :

For TM's

M₁ and M₂, if M₁ ≡ M₂ then M₁ ∈ L ⇔ M₂ ∈ L

but

There are TM's M₁ and M₂, such that M₁ ∈ L and M₂ ∉ L

Than L is undecidable because TM's for same set is not belongs to same language.

So we can say that FIN is not decidable i.e. undecidable.

if there is any query please ask in comments....