MAT6030-01 (2017학년도 2학기)

2017-06-15 12:39:09  2017-09-01 15:04:29 
계산가능성이론 I 
과254  화4,목3,4 
 
김병한  이과대학 수학 
Sci. 246   
bkim@yonsei.ac.kr
 
graduate students
In this course we mainly study the generalized Turing computable decision problems/sets. A decision problem (e.g. deciding whether a given number is prime of not) can correspond to a suitable subset of N(=the set of natural numbers). It is well-known that such a decision problem is solvable(=decidable) iff the corresponding set is Turing computable. But there too exist many problems shown to be undecidable (e.g. deciding the truth of arithmetic sentences) by Goedel, Turing, Church and else. Then using the notions of Turing-reducibility (or oracle Turing machines) a hierarchy of degrees of unsolvability can be given by supplying a Turing-reducibility order relation on the continuum many classes of an equivalence relation on the power set of N. Indeed all the Turing computable problems have the least degree 0. Among such degrees, computably enumerable (c.e.) degrees have been a central theme in the subject and hence have been studied intensively.
some basic knowledge of  mathematical logic
Homework and presentation
Recursively enumerable sets and degrees, by Robert I. Soare (Springer 1987)
http://web.yonsei.ac.kr/bkim/
2017-09-01 2017-09-07
Turing computable functions 
 
(9.1.) Fall semester classes begin
(9.5. - 9.7.) Course add and drop period 
2017-09-08 2017-09-14
Premitive recursive sets and functions 
 
 
2017-09-15 2017-09-21
recursively(=computably) enumerable sets and relations. 
 
 
2017-09-22 2017-09-28
Relative recursiveness 
 
 
2017-09-29 2017-10-05
 
 
(10.3.) National Foundation Day
(10.3. - 10.6.) Chuseok Holiday 
2017-10-06 2017-10-12
Incomparable r.e.(=c.e.) degrees 
 
(10.3. - 10.6.) Chuseok Holiday
(10.9.) Hangul Proclamation Day
(10.10.) First third of the semester ends
(10.11. - 10.13.) Course withdrawal period 
2017-10-13 2017-10-19
 
 
(10.11. - 10.13.) Course withdrawal period
(10.18. - 10.24.) Midterm Examinations 
2017-10-20 2017-10-26
 
 
(10.18. - 10.24.) Midterm Examinations 
2017-10-27 2017-11-02
minimal degrees 
 
 
10  2017-11-03 2017-11-09
 
 
 
11  2017-11-10 2017-11-16
 
 
(11.15.) Second third of the semester ends 
12  2017-11-17 2017-11-23
Jump inversion 
 
 
13  2017-11-24 2017-11-30
 
 
 
14  2017-12-01 2017-12-07
Forcing 
 
 
15  2017-12-08 2017-12-14
 
 
(12.8. - 12.21.) Self-study and Final Examinations 
16  2017-12-15 2017-12-21
splitting/Sack`s density theorem 
 
(12.8. - 12.21.) Self-study and Final Examinations