Question

Investigate and Prove that the following closure properties hold for Turing machines

Theorem 7: Both the Turing-recognizable and Turing- decidable languages are closed under concatenation and star.

Answer 1

Ans.1 Turing-recognizable languages are closed under concatenation and star. this statement is true.

Prove:

Concatenation : Let K and L be two Turing recognizable languages, and let M_K and M_L denote the Turing machines that recognize K and L respectively. We construct a non-deterministic Turing machine M_KL that recognizes the language KL.

i. Non-deterministically cut input w into w₁ and w₂

ii. Run M_K on w₁. If it halts and rejects, reject.

iii. Run M_L on w₂. If it accepts, accept. If it halts and rejects, reject.

Note the difference between the Turing machines for recognizable and decidable languages. Here, we need to take care of the fact that the machines M_K and M_L need not halt.

Star : For a Turing recognizable language L, we construct a nondeterministic Turing machine M_L∗ that recognizes L^∗. The idea is similar to the decidable case.

i. On input w, non-deterministically cut w into parts w₁ w₂···w_n.

ii. Run M_L on w_i for all i. If M_L accepts all of them, accept. If M_L halts and rejects for any i, reject.

If there is a way to cut w into strings w₁ w₂···w_n such that each w_i ∈ L, then there is a computation path in M_L∗ that accepts w in a finite number of steps.

Turing-decidable languages are closed under concatenation and star. this statement is true.

Prove:

Concatenation: Let K, L be decidable languages. The concatenation of languages K and L is the language KL = {xy|x ∈ K and y ∈ L}. Since K and L are decidable languages, it follows that there exist Turing machines M_K and M_L that decide the languages K and L respectively. In order to prove that KL is decidable, we can construct a Turing machine that decides KL.

This machine, M_KL can use the machines M_K and M_L to decide if a string is in KL or not. The machine can be constructed as follows :

Consider an input string w. We need to decide if w is of the form xy for x ∈ K and y ∈ L. If this is the case, there must be a position at which we can partition w into x and y. Since there are only finitely many ways to partition the string, we can try all possibilities and accept if there is such a partition and reject otherwise. We will describe a nondeterministic Turing machine since it is easier to describe.

i. On input w, non-deterministically partition w into strings xy.

ii. Input x to M_K and y to y on M_L.

iii. accept if both M_K and M_L accept, else reject.

If there is an accepting computation path, then we have found a successful split and the string is in KL. If all computation paths reject, then the string is not in KL. In either case, it is easy to see that the machine M_KL halts. Thus, KL is decidable.

Star: For a language L, L^∗ = {x ∈ L∪ LL ∪ LLL ∪···}. i.e. all strings obtained by concatenating L with itself, and so on. To show that L^∗ is decidable, the idea is similar to the previous solution. We want to find cuts of the input string w, such that each of them is accepted by the Turing machine M_L that decides L. Let M_L∗ be the machine that that decides L^∗.

i. On input w : For each way to cut w into parts w₁ w₂···w_n

ii. Run M_L on w_i for i = 1,···,n.

iii. If M_L accepts each of the strings w_i accept.

iv. If all cuts have been tried without success, reject.