LAST PRIORITY ARGUMENT IN C122 FRIDAY MAY 20 AT 13:00.
THEN STARTS LOGIC WEEK, SEE:
This is an introductory course to computability theory. In the text Computability: An Introduction to Recursive Function Theory the intention is to cover chapters 1 to 7.
Weeks 3-9 and 11-18, Tuesday 10-12 and Wednesday 10-12 in room C122.
Exams FINAL EXAM MAY 4 DURING CLASS TIME. IF YOU CHOOSE TO PRESENT A PRIORITY ARGUMENT YOU ARE EXEMPT FROM THE FINAL EXAM. PRIORITY ARGUMENTS WILL BE PRESENTED ON FRIDAY MAY 13, 9-12, room B322.
The text for the course is Computability: An Introduction to Recursive Function Theory by Nigel Cutland
Did you forget to register? What to do?
- Set 11: p. 160, 1,3,5. p. 165, 1,4,5.
- Set 10, p. 146, exercise 1.6; p. 156, exercise 4.3; p. 160, exercises 1,2,3.
- Set 9 p. 122, exercises 1,2. p. 132, exercises 2,6, 8,13. p. 138, exercises 1,2.
- Set 8. p.94, exercises 1-5. Also begin reading friedberg.pdf.
- Set 7: p.80, 1,4; p.84, 1,2,3; p.90, 1.
- Set 6: Do exercises 1.6 on page 76 of Cutland; 2.3 on page 77; 3.2 1-4 on page 80
- Set 1: Read the first 14 pages of chapter 1 of Cutland's book. Do exercise 2.2 on page 14.
- Set 2: Do exercises 2.2, 2.3, 3.3 (1-4) on pages 14,16,21-22
- Set 3: p. 23: exercise 4.3 (a,b,c). p. 24: exercise 5.2 (1,2). p. 32: exercise 1. Write the program showing that the function y=2x+1 is computable.
- Set 4: Give a Turing machine that computes the function: f(x,y)=xy; f(x)=(x+2)^2. Give a Post system that computes these functions. (As always, do the best you can!)
- Set 5: About example 5.5 on page 46 of Cutland: In the proof sketch that the Ackerman function is computable:
- Prove the following claim made on p. 46: to compute the value of the Ackerman function on a pair x,y ,
only a finite number of earlier values are used. Prove this by mathematical induction on the number of earlier values.
- Prove that the computation of the Ackerman function (definition on pa. 47, line -7) is independent of the suitable system S. That is, if S on an input (x,y) gives z, and if S' on an input (x,y) gives z', then z=z'. This is proved by a double induction on the input (x,y).
Course feedback can be given at any point during the course. Click here.