3. (13 points) [A,B,D] Proving REC and RE are closed under set union. I will use...

Transcribed Image Text:

3. (13 points) [A,B,D] Proving REC and RE are closed under set union. I will use 's on programs involved in the proof that RE is closed under set union. (a) (1 point) [B] Express the closure property that REC is closed under set union in first-order logic. (b) (1 point) [B] Express the closure property that RE is closed under set union in first-order logic. (c) (1 point) [A] To prove that REC is closed under set union, we can assume we have two C++ programs P and P which do what? (d) (1 point) [A] To prove that RE is closed under set union, we can assume we have two C++ programs P and P which do what? (e) (1 point) [B] To prove that REC is closed under set union, we want to create a C++ program P3 that does what? (f) (1 point) [B] To prove that RE is closed under set union, we want to create a C++ program P3 that does what? (g) (1 point) [A] What should program P3 do on any string in Y (P)UY(P)? (h) (1 point) [A] What should program P3 do on any string in Y(P) UY (P)? (i) (1 point) [A] What should program P3 do on any string not in Y(P) UY(P)? (i) (1 point) [A] What should program P3 do on any string not in Y(P) UY (P)? 3. (13 points) [A,B,D] Proving REC and RE are closed under set union. I will use 's on programs involved in the proof that RE is closed under set union. (a) (1 point) [B] Express the closure property that REC is closed under set union in first-order logic. (b) (1 point) [B] Express the closure property that RE is closed under set union in first-order logic. (c) (1 point) [A] To prove that REC is closed under set union, we can assume we have two C++ programs P and P which do what? (d) (1 point) [A] To prove that RE is closed under set union, we can assume we have two C++ programs P and P which do what? (e) (1 point) [B] To prove that REC is closed under set union, we want to create a C++ program P3 that does what? (f) (1 point) [B] To prove that RE is closed under set union, we want to create a C++ program P3 that does what? (g) (1 point) [A] What should program P3 do on any string in Y (P)UY(P)? (h) (1 point) [A] What should program P3 do on any string in Y(P) UY (P)? (i) (1 point) [A] What should program P3 do on any string not in Y(P) UY(P)? (i) (1 point) [A] What should program P3 do on any string not in Y(P) UY (P)?

Answer rating: 100% (QA)

a The closure property that REC is closed under set union can be expressed in firstorder logic as fo... View the full answer