CS701 Assignment 2 Solution and Discussion

[zareen]

CS701 – Theory of Computation

Due Date: December 06, 2019

Assignment 2

Instructions to Solve Assignments

The purpose of assignments is to give you hands on practice. It is expected that students will solve the assignments themselves. Following rules will apply during the evaluation of assignment.

• Cheating from any source will result in zero marks in the assignment.
• Any student found cheating in any two of the assignments submitted will be awarded “F” grade in the course.
• No assignment after due date will be accepted.

Question 1: Total Points (20)
Consider following instances of Post Correspondence Problem (PCP). Is it possible to find a match for every PCP instance given below? If YES, then give the dominos arrangement which will result in a match. If NO, then prove.
a.
b.

Question 2: Total Points (15)
Is the following statement TRUE or FALSE? Justify your answer.

∀x∀y∃z [ R1(x, y, z) ∨ R1(y, x, z) ∨ R2(x, y) ], where universe is the set of positive integers and R1 = MINUS, that is, MINUS (x, y, z) = TRUE whenever x – y = z, and R2(x, y) = TRUE whenever x = y.

Question 3: Total Points (15)
a. Prove that A is Turing-recognizable if and only if A ≤m ATM.
b. Prove that ATM ETM. In other words, you have to prove that it is not possible to reduce ATM to ETM.