CIS 4930/6930: Programs, Functions, Strange Loops, and Consciousness Programs and Functions Assignment 3.

CIS 4930/6930: Programs, Functions, Strange Loops, and Consciousness Programs and Functions Assignment 3 1. (5 pts.) If f = [while p do g], which one of the following, according to the Iteration R ecursion Lemma (IRL), is functionally equivalent to [while p do g]? Circle ONE only. a. [if p then f;g end_if] b. [if p then gof end_if] c. [if p then g else f end_if_else] d. [if p then f else g end_if_else] e. [if p then g end_if] f. [if p then f end_if; g] then f end_if] i. (none of the above) 2. (14 pts.) Match each assertion of functional correctness below to the appropriate Correctness Condition(s) among the following. (Note: Correctness Condition(s) may be appropriate for none, one, or more than one assertion.) A. (f = gohok) E. term(f,S), pog  (f = g), ¬(pog)  (f = fog) B. p  (f = g), ¬p  (f = h) F. term(f,S), p  (f = fog) ¬p  (f = I) C. (f = kohog) G. term(f,S), gop  (f = g), ¬(gop)  (f = gof) 2 3. (12 pts.) Determine (but do not formally verify) the function of the following program: x := y-2 while x5 do x := x-1 end_while Give your answer in the simplified form: (p  x,y := ?,?) where p is a Boolean predicate which specifies the domain of the program function. (Hint: Use heuristics to identify the function of the while loop and then use the Axiom of Replacement and function composition to determine the program function.) program function: 4. Suppose that you wish to prove that the program, M, below computes the given intended function, f, by showing (1) term(f,M), (2) p  ( f=fog ), and (3) ¬p  ( f=I ). end_while a. (4 pts.) Express “g” as a concurrent assignment function in terms of variables k and t. b. (2 pts.) What is “p” from correctness conditions (2) and (3) above? (Give the actual expression that p represents.) 3 c. (4 pts.) It can be shown that wp(M, true) = true. Does this imply term(f,M) holds? d. (8 pts.) Prove that correctness condition (2) holds by completing the following proof template.