---
# System prepended metadata

title: Exercise 7

---

# Exercise 7

## Question 1 and 2

Solutions on slides



## Question 3
* Quiz

We discussed in the slides that for this question one needs to reduce the problem MR(Y) to Halting problem. That is if we know solution to MR(Y) then we can solve Halting Problem. We know that halting problem is undecidable hence MR(Y) is undecidable.

Write the reduction by appropriately modifying the below code snipet

    problemA(a = instance of problem A)
        c = modify input a
        d = problemB(c)
        use d to output solution of problemA
        
    

* **Q3.1.** What should be ProblemA?
    i) Halting Problem
    ii) MR(Y)

* **Q3.2.** What should be ProblemB?
    i) Halting Problem
    ii) MR(Y)

* **Q3.3.** How will you use d to output solution of problemA? 

* **Q3.4** Prove that the reduction is correct.

## Question 4 (Take Home, if time permits we come back to this)

## Question 5
In the slides, we discussed that we need to prove that the number of configurations of a TM are finite when the memory of TM is limited to be finite.

* **Q5.1** What is the number of configurations? work with your group to find that out.

* **Q5.2** How does the finite number of configurations allow you to argue that the TM will halt in finite time? Can you think of an argument?


## Question 6
Prove that given algorithm of Knapsack is correct and satisfies the time guarantee

* **Time Complexity**
    * How many calls of A(P,S,K) did we make?

* **Correctness**
    * What is the invariant that is maintained about P in the for loop    
    * Is there a element  $p \in P$ which exists in P during the return such that $p$ is not used in Knapsack?