---
# System prepended metadata

title: Exercise 7 breakout room 2

---

# Exercise 7 breakout room 2

## 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

    HaltingProblem(a = instance of problem A)
        d = MR(a)
        if d = 0
            a (with empty input) does not halt
        else 
            a (with empty input) halts after d steps
        //use d to output solution of problemA 
        return (d>0) // == Halts(a)
    
* **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?

thinking out load...
Suppose MR(y) is computable (to get contradiction).
We will construct a halting checker.
let P be a program and x an input
insert x into P to get program P'
P' has finite length, say y
Compute MR(y). If MR(y) > 0 we know that (P,x) halts.
Contradiction. Something like this?
Not sure about the input y though...


for what i wrote below, Im not sure about how I used MR(y), if it is zero does it mean it does not halt?
haha it feels like it kind of makes sense
^^ m just writing whats above in pseudocode? 
HALTS(P,x):
    y = length(P <- x) #length of binary encoding (???)
    result = MR(y)
    if result = 0: #f(x) = 0 when program x dosent terminate
        return false
    else: 
        return true
    


* **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?