LAST PRIORITY ARGUMENT IN C122 FRIDAY MAY 20 AT 13:00.

THEN STARTS LOGIC WEEK, SEE: 

https://wiki.helsinki.fi/display/Logic/Model+theory+and+set+theory+days

The [toc] macro is a standalone macro and it cannot be used inline. Click on this message for details.
This macro generates standalone content. As a consequence you need to make sure to use a syntax that separates your macro from the content before and after it so that it's on a line by itself. For example in XWiki Syntax 2.0+ this means having 2 newline characters (a.k.a line breaks) separating your macro from the content before and after it.

News

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.

Teaching schedule

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.

 Course material

The text for the course is Computability: An Introduction to Recursive Function Theory by Nigel Cutland

COMPUTABILITY_COURSE_LECTURE_1.pdf

Registration

 
Did you forget to register? What to do?

Exercises

Assignments

• 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+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:

1. 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.  
2. 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).
   
   

Exercise classes

Course feedback

Course feedback can be given at any point during the course. Click here.