Question

Turing Machine and Closure Operations

Show that Turing-recognizable languages are closed under the following operations:

• union

• concatenation

• star

Each answer needs only be a short informal description of a Turing Machine (but it must still be sufficiently precise so someone could reconstruct a formal machine if needed).

Also, be careful with non-termination (when appropriate)!

Answer 1

1.

Turing-recognizable languages are closed under union.

Let L1 and L2 be two Turing-recognizable languages and M1 and M2 be corresponding Turing Machines that recognize them.

To see that they are closed under union, do

Non-Determinstically guess whether a string x belongs to L1 or L2 and then run it on M1 or M2.

But problem is that if the string does not belong to L1 , running it on M2, it might not even halt(non termination).

To overcome this, we run the string on M1 and M2 simultaneously, i.e. one step in M1 and then one step in M2.

If either of M1 or M2 accepts, accept.

2.

Turing-recognizable languages are closed under concatination.

Let L1 and L2 be two Turing-recognizable languages and M1 and M2 be corresponding Turing Machines that recognize them.

given an input string x, nondeterministically break into 2 parts x=uv. run u on M1 and v on M2 .

if both M1 and M2 accept, accept x.

3.

Turing-recognizable languages are closed under star.

Let L be a turing regognizable language and M be the Turing maching that recognizes it.

This is similar to concatination .

first nodeterministically guess a number n and break the input string x into n parts.

run each part on M and if all parts are acceptes accept.