##### Child pages
• Computability theory, spring 2016
Go to start of banner

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

Teacher: Juliette Kennedy

Scope: 10 cr

Teaching:

Topics: Computability

Prerequisites: Some basic logic is good but not absolutely necessary.

## 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

## 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)=(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

GroupDayTimeRoomInstructor
1.Thursday 10-12 C129 Miguel Moreno

## Course feedback

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

• No labels