TIFR CSE 2010 | Part B | Question: 31

Question

Consider the following computation rules. Parallel-outermost rule: Replace all the outermost occurrences of F (i.e., all occurrences of F which do not occur as arguments of other F's) simultaneously. Parallel - innermost rule: Replace all the innermost occurrences of F (i.e.,all occurrences of F with all arguments free of F's) simultaneously. Now consider the evaluations of the recursive program over the integers.  

F(x, y) <== if x = 0 then 0 else   
            [ F(x + 1, F(x, y)) * F(x - 1, F(x, y))] 

 where the multiplication functions * is extended as follows:  

0 * w & w * 0 are 0
a * w & w * a are w (for any non-zero integer a)
w * w is w  

We say that $F(x, y) =$ w when the evaluation of $F(x, y)$ does not terminate. Computing $F(1, 0)$ using the parallel - innermost and parallel - outermost rule yields

• A. $w$ and $0$ respectively
• B. $0$ and $0$ respectively
• C. $w$ and $w$ respectively
• D. $w$ and $1$ respectively
• E. none of the above
   

Comments

This is actually an easy question, decoding is the longest part. :p

Answer 1

Decoding the question :-

Parallel-outermost rule :-Replace all the outermost occurrences of F.Now what does outermost occurrence mean? it means those occurrences of F which are not appeared inside F as argument.

$F(1,0)$ it's outermost occurrence as didn't appear inside any $F$.So replace it.See out recurrence relation this will be replaced by ${\color{Red} F(2,F(1,0))} *{\color{Blue} F(0,F(1,0))}$ Now here again Red color $F$ and blue color $F$ are outmost occurrences for each other as they are not occurred as argument of some other $F$.(other $F$ which are uncolored are not included as 'outermost occurrence' as they are appeared as argument in some $F$)

So now replace only outermost occurrences(simultaneously). We don't have to replace other occurrences (uncolored) of $F$.

So overall it will become

$[F(3,F(2,F(1,0)))*F(1,F(2,F(1,0)))] *0$          //$F(0,F(1,0))$ will become $0$

Now we can observe some part will never terminate and some part will become $0$ so overall we can say it would be something like $W*0$ and which would result into $0$. So i think Applying parallel-outermost rule will result into $0$ .

---

Parallel-innermost rule:- Replace all the innermost occurrences of $F$. Here innermost occurrences mean those whose arguments are free from $F$.

Like in $F(1,0)$ argument of $F$ are $1,0$ which are free from $F$ so replace it by recurrence relation and hence it would become

$F(2,{\color{Red} F(1,0)})*F(0,{\color{Blue} F(1,0)})$ Here i colored another innermost occurrences of $F$ which we have to replace again.uncolored $F$ are not innermost occurrences as they contain such arguments which are not themselves function of $F$.

So overall it would become

$F(2,[F(2,F(1,0))*F(0,F(1,0))]) * F(0,[F(2,F(1,0))*F(0,F(1,0))])$

Here we can observe this that everytime we have to expand only function $F(1,0)$ because that's the only function whose arguments are free from any $F$ So in that way , overall it would become $W*W$ type which would result into $W$.

So option A is the correct answer.

Comments

nice explanation @ rupendra choudhary sir

Answer 2

Answer is A) $w$ and $0$

If we solve using parallel innermost rule 

$F(1,0) = F(2,F(1,0)) * F(0,F(1,0))$

$=F(2, F(2,F(1,0)) * F(0,F(1,0))  ) * F(0,  F(2,F(1,0)) * F(0,F(1,0)) )$

Since computation of $F(1,0)$ goes on

We assign $F(1,0)$ to $w$.

So, $F(1,0)= w$

Using parallel outermost rule:

$F(1,0)= F(2,F(1,0)) * F(0,F(1,0))$

$ = F(2,F(1,0)) * 0$

$= 0$

Comments

why it cant be 0,0 ....cause w*0 is 0.......plz explain

---

@khamer

In parallel inermost  execution we will keep exploring  $F(1,0)$  , so if condition will always be true as in this case  $X$  is always  $1$ .

It will not be $Zero$   because we are not touching outermost $F$ which  $X$  is zero , so  $if$ condition will always holds  $true$