### CS4123 Theory of Computation  Homework 3 - B 2004

Due Date: Friday, December 3rd at 12:00 noon.
NO SUBMISSIONS WILL BE ACCEPTED AFTER 12:05 PM.

1. Consider the following language:

SUBSETTM = { <M1,M2> | M1 and M2 are Turing machines, and L(M1) is a subset of L(M2)}.

1. (10 points) Prove that the language SUBSETTM is undecidable. In other words, prove that there is no Turing machine (i.e. algorithm) that solves the following problem:
• Input: Two Turing machines M1 and M2
• Output:
• accept, If L(M1) is a subset of L(M2). That is, every word accepted by M1 is also accepted by M2.
• reject, otherwise. That is, there is a word w in Sigma* such that w belongs to L(M1), but it doesn't belong to L(M2)

2. (10 points) Prove that the language SUBSETTM is not semi-decidable.

3. (10 points) Prove that the language SUBSETTM is not co-semi-decidable. That is, prove that its complement, SUBSETCTM, is not semi-decidable.

Hint: Prove both of the following two parts:

• EQTM <=m SUBSETTM.
• If A and B are two languages and if A <=m B, then AC <=m BC.
Explain clearly and in detail why the two parts above imply that SUBSETTM is undecidable, not semi-decidable, and not co-semi-decidable.

2. Consider the following language:

LOOPSTM = { <M> | M is a Turing machine and there is at least one word w in Sigma* such that M doesn't halt (i.e. it loops) when it is run on input w}.

1. (10 points) Prove that the language LOOPSTM is undecidable. In other words, prove that there is no Turing machine (i.e. algorithm) that solves the following problem:
• Input: A Turing machine M
• Output:
• accept, If there is a word w in Sigma* such that M loops (doesn't halt) on input w.
• reject, otherwise. That is, M halts on each and every input string.

2. (10 points) Prove that the language LOOPSTM is not semi-decidable.

3. OPTIONAL (10 points): Is the language LOOPSTM co-semi-decidable or is it not co-semi-decidable? That is, determine whether this language's complement, LOOPSCTM, is semi-decidable or is not semi-decidable. Prove your answer.

Hint: Prove that HALTCTM <=m LOOPSTM (or equivalently that ACTM <=m LOOPSTM). Explain in detail why this implies that LOOPSTM is undecidable and also that it is not semi-decidable.

3. Let A and B be two languages on the same Sigma alphabet. Assume that A <=m B, that is A is mapping reducible to B.
For each of the following pair of statements:

• (2 points each) Determine and state which of the two statements is correct and which one is incorrect given that A <=m B.

• (5 points each) Prove that the correct statement is true.
Hint: See Theorems and Corollaries 5.16, 5.17, 5.22, and 5.23. In your HW solutions, you need to provide all the details of the proofs that are missing in the textbook.

• (6 points each) Show that the incorrect statement is in fact incorrect by showing an example of a language A and a language B such that A <=m B, the language in the "IF" part of the statement satisfies the "IF" condition, but the language in the "THEN" part of the statement doesn't satisfy the "THEN" condition.
Make sure you prove in detail all your claims.

Pair of statements:

• 1.1. If A is decidable then B is decidable

• 1.2. If B is decidable then A is decidable

• 2.1. If A is semi-decidable then B is semi-decidable

• 2.2. If B is semi-decidable then A is semi-decidable

• 3.1. If A is undecidable then B is undecidable

• 3.2. If B is undecidable then A is undecidable

• 4.1. If A is not semi-decidable then B is not semi-decidable

• 4.2. If B is not semi-decidable then A is not semi-decidable