Computer Science 750 (2022) Assignment 1
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Computer Science 750 (2022)
Assignment 1
Questions
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.
3. Question 3 [Mathematical modeling]
(d) Define the property “the infinite binary sequence contains a monochromatic arithmetic progression” .
(e) Does every infinite binary sequence contain a monochromatic arithmetic progression? Justify with proof your answer.
(f) Answer questions a) and b) for ternary sequences. Justify with proof your answers.
2022-10-02