1.  Question 1 [Program analysis]

Goldbach’s conjecture states that every even integer greater than 2 is the sum of two prime numbers.

a) Construct an algorithm A(N) that on every even integer N > 2 decides whether N is the sum of two primes.

b) Does A(N) halt for every N? Justify with proof your answer.

c) Assume A(N) returns 1 if N is the sum of two prime numbers and 0 otherwise. Does the algorithm:

1. G = 1.

2. N = 1.

3. If A(N) = 1, N = N + 1, go to 2.

4. G = 0.

5. Stop.

halt? Justify with proof your answer.

Does it solve the Goldbach conjecture? Justify with proof your answer.

2.  Question 2 [Research quation]

Write 800- 1000 words discussing the claim that

Any function can be computable. Use can use the reference: John Baez, Computing the Uncomputable,

https://johncarlosbaez.wordpress.com/2016/04/02/computing-the-uncomputable/.

(a)  State and explain the main result.

(b) Explain in your own words the proof.

(c) Does the main result contradict the Halting Theorem? Justify with proof your answer.