Last modified by jkennedy@helsinki_fi on 2024/03/27 10:27
Show last authors
1 = (% style="color: rgb(255,0,0);" %)LAST PRIORITY ARGUMENT IN C122 FRIDAY MAY 20 AT 13:00.(%%) =
2
3 = (% style="color: rgb(255, 0, 0); color: rgb(0, 128, 0)" %)THEN STARTS **LOGIC WEEK**, SEE: (%%) =
4
5 = (% style="color: rgb(255,0,0);" %)[[https:~~/~~/wiki.helsinki.fi/display/Logic/Model+theory+and+set+theory+days>>url:https://wiki.helsinki.fi/display/Logic/Model+theory+and+set+theory+days||shape="rect"]](%%) =
6
7 (% style="color: rgb(255,0,0);" %)
8
9
10
11
12 {{panel}}
13
14
15 **Teacher:** [[Juliette Kennedy>>doc:mathstatHenkilokunta.Kennedy, Juliette]]
16
17 **Scope:** 10 cr
18
19 **Type:** Advanced studies
20
21 **Teaching:**
22
23 **Topics: Computability**
24
25 **Prerequisites: Some basic logic is good but not absolutely necessary.**
26 {{/panel}}
27
28 === {{toc maxLevel="4" minLevel="2" indent="20px"/}} ===
29
30 == News ==
31
32 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.
33
34 == Teaching schedule ==
35
36 Weeks 3-9 and 11-18, Tuesday 10-12 and Wednesday 10-12 in room C122.
37
38 == Exams(% style="color: rgb(255,0,0);" %) **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.**(%%) ==
39
40 (% style="color: rgb(0,0,0);" %) (% style="color: rgb(0, 0, 0); font-size: 20px" %)Course material
41
42 The text for the course is //Computability: An Introduction to Recursive Function Theory //by// //Nigel Cutland
43
44 == **[[COMPUTABILITY_COURSE_LECTURE_1.pdf>>attach:COMPUTAIBILTY_COURSE_LECTURE_1.pdf]]** ==
45
46 == [[Registration>>url:https://oodi-www.it.helsinki.fi/hy/opintjakstied.jsp?html=1&Tunniste=57072||shape="rect"]] ==
47
48
49 (% style="color: rgb(96,96,96);" %)Did you forget to register? (%%)[[What to do?>>url:https://wiki.helsinki.fi/display/mathstatOpiskelu/Kysymys4||style="text-decoration: underline;" shape="rect"]]
50
51 == Exercises ==
52
53 === Assignments ===
54
55
56
57
58
59 * Set 11: p. 160, 1,3,5. p. 165, 1,4,5.
60 * Set 10, p. 146, exercise 1.6; p. 156, exercise 4.3; p. 160, exercises 1,2,3.
61 * Set 9 p. 122, exercises 1,2. p. 132, exercises 2,6, 8,13. p. 138, exercises 1,2.
62 * Set 8. p.94, exercises 1-5. Also begin reading [[attach:friedberg.pdf]].
63 * Set 7: p.80, 1,4; p.84, 1,2,3; p.90, 1.
64 * Set 6: Do exercises 1.6 on page 76 of Cutland; 2.3 on page 77; 3.2 1-4 on page 80
65 * Set 1: Read the first 14 pages of chapter 1 of Cutland's book. Do exercise 2.2 on page 14.
66 * Set 2: Do exercises 2.2, 2.3, 3.3 (1-4) on pages 14,16,21-22
67 * (% style="color: rgb(255,102,0);" %)Set 3: p. (% style="color: rgb(255, 102, 0); color: rgb(0, 0, 255)" %)**23**:(% style="color: rgb(255,102,0);" %) exercise 4.3 (a,b,c). p. (% style="color: rgb(255, 102, 0); color: rgb(0, 0, 255)" %)**24**(% style="color: rgb(255,102,0);" %): exercise 5.2 (1,2). p.(% style="color: rgb(255, 102, 0); color: rgb(0, 0, 255)" %)** 32:** (% style="color: rgb(255,102,0);" %)exercise 1. Write the program showing that the function y=2x+1 is computable.
68 * (% style="color: rgb(255,102,0);" %)Set 4: Give a Turing machine that computes the function: (% style="color: rgb(255, 102, 0); color: rgb(0, 51, 102)" %)f(x,y)=xy; f(x)=(x+2)^2(% style="color: rgb(255,102,0);" %). Give a Post system that computes these functions. (As always, do the best you can!)
69 * (% style="color: rgb(255,102,0);" %)Set 5: About example 5.5 on page 46 of Cutland: In the proof sketch that the Ackerman function is computable:
70
71 1. (% style="color: rgb(255,102,0);" %)Prove the following claim made on p. 46: to compute the value of the Ackerman function on a pair x,y ,(%%)
72 (% style="color: rgb(255,102,0);" %)only a finite number of earlier values are used. Prove this by mathematical induction on the number of earlier values.
73 1. (% style="color: rgb(255,102,0);" %)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).(%%)
74 (% style="color: rgb(255,102,0);" %)\\(% style="color: rgb(0, 0, 0); color: rgb(255, 102, 0)" %)
75
76
77 === Exercise classes ===
78
79 |=(((
80 Group
81 )))|=(((
82 Day
83 )))|=(((
84 Time
85 )))|=(((
86 Room
87 )))|=(% colspan="1" %)(((
88 Instructor
89 )))
90 |(((
91 1.
92 )))|(((
93 Thursday
94 )))|(((
95 10-12
96 )))|(((
97 C129
98 )))|(% colspan="1" %)(((
99 Miguel Moreno
100 )))
101
102 == Course feedback ==
103
104 Course feedback can be given at any point during the course. Click [[here>>url:https://elomake.helsinki.fi/lomakkeet/11954/lomake.html||style="line-height: 1.4285;" shape="rect"]].