# 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

**Teacher:** Juliette Kennedy

**Scope:** 10 cr

**Type:** Advanced studies

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

**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)=(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).

### Exercise classes

Group | Day | Time | Room | Instructor |
---|---|---|---|---|

1. | Thursday | 10-12 | C129 | Miguel Moreno |

## Course feedback

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