Spring Semester, 2016
Announcement
- Welcome to the class. Have fun! The important information will be announced here. Please check this webpage often.
General Information
- Level: Undergraduates (Junior)
- Time: 12:55pm – 3:40pm, Tuesday
- Place: Dong Zhong Yuan 3-103 (东中院3-103)
- Instructor:
- Name: Xiaofeng Gao (高晓沨)
- Email: gao-xf(at)cs.sjtu.edu.cn
- Office: Telecom Building 3-543
- Phone: 021-34207407
- Teaching Assistant:
- Name: Xudong Zhu(朱旭东)
- Email: nongeek.zv(at)gmail.com
- Office: Telecom Building 3-328
- Phone: 021-34207407
- Office Hour: 2:00 - 5:00pm, Wednesday (Week 4, 8, 12, 16)
- Textbook:
Title: Computability: An Introduction to Recursive Function Theory
Author: Nigel L., Cutland
Publisher: Cambridge University Press, 1980
ISBN-10: 0521294657
ISBN-13: 978-0521294652
Amazon: http://www.amazon.com/Computability-Introduction-Recursive-Function-Theory/dp/0521294657
Course Schedule
|
February 2016 |
|
March 2016 |
|
April 2016 |
||||||||||||||||||
week |
S |
M |
T |
W |
T |
F |
S |
week |
S |
M |
T |
W |
T |
F |
S |
week |
S |
M |
T |
W |
T |
F |
S |
|
|
1 |
2 |
3 |
4 |
5 |
6 |
(2) |
|
|
1 |
2 |
3 |
4 |
5 |
(6) |
|
|
|
|
|
1 |
2 |
|
7 |
8 |
9 |
10 |
11 |
12 |
13 |
(3) |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
(7) |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
14 |
15 |
16 |
17 |
18 |
19 |
20 |
(4) |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
(8) |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
(1) |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
(5) |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
(9) |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
(2) |
28 |
29 |
|
|
|
|
|
(6) |
27 |
28 |
29 |
30 |
31 |
|
|
(10) |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
May 2016 |
|
June 2016 |
|
Total: 18 weeks, 16 classes |
||||||||||||||||||
week |
S |
M |
T |
W |
T |
F |
S |
week |
S |
M |
T |
W |
T |
F |
S |
|
|
|
|
|
|
|
|
(11) |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
(15) |
|
|
|
1 |
2 |
3 |
4 |
|
|
|
Class Day |
||||
(12) |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
(16) |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
|
|
|
|
|
|
|
(13) |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
(17) |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
|
|
· |
Holiday |
||||
(14) |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
(18) |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
|
|
|
|||||
(15) |
29 |
30 |
31 |
|
|
|
|
|
26 |
27 |
28 |
29 |
30 |
|
|
|
|
· |
Final Exam Week |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Syllabus
Week |
Date |
Lecture Topic |
HW |
Exam |
1 |
Tue.23 |
Syllabus, Preliminary, Proof Schedule, Grading Policy, Set, Functions, Symbols, Notations. |
Lab-01 |
|
2 |
Mar.01 |
Chapter 1: Computable Functions Decidable, Computable, URM, Algorithms, etc. |
Lab-02 |
|
3 |
Mar.08 |
Chapter 2: Generating Computable Functions Basic Functions, Substitution, Recursion, Minimalisation, etc. |
Lab-03 |
|
4 |
Mar.15 |
Chapter 3: Church’s Thesis Godel-Kleene, Turing-Computability, Church’s Thesis, etc. |
Lab-04 |
|
5 |
Mar.22 |
Chapter 4: Numbering Computable Functions Numbering programs, Diagonal Method, s-m-n Theorem, etc. |
Lab-05 |
|
6 |
Mar.29 |
Chapter 5: Universal Programs Universal functions and programs, Applications, Effective Operations etc. |
Lab-06 |
|
7 |
Apr.05 |
Chapter 6: Decidability, Undecidability, and Partial Decidability Undecidable programs, Diophantine, Sturm’s algorithm, etc. |
Lab-07 |
|
8 |
Apr.12 |
Review from Chapter 1 to Chapter 6 Tutorials, Exercises |
No Lab |
|
9 |
Apr.19 |
Application. Exercises. Midterm. |
|
Midterm |
10 |
Apr.26 |
Chapter 7: Recursive and Recursively Enumerable Sets Recursive Sets, Recursively Enumerable Sets |
Lab-07 |
|
11 |
May 03 |
Chapter 7: Recursive and Recursively Enumerable Sets Productive Sets, Creative Sets, Simple Sets, etc. |
Lab-08 |
|
12 |
May 10 |
Chapter 7: Recursive and Recursively Enumerable Sets Comparisons, Exercises. |
Lab-10 |
|
13 |
May 17 |
Chapter 9: Reducibility and Degrees Many-One Reducibility, Degrees, etc. |
Lab-11 |
|
14 |
May 24 |
Chapter 9: Reducibility and Degrees Turing Reducibility, Turing Degrees, etc. |
Lab-12 |
|
15 |
May 31 |
NP Problem NP, NPC, NPH, NP Reduction, etc. |
Lab-13 |
|
16 |
Jun.07 |
Review from Chapter 7 to Chapter 9 Tutorials, Exercises |
No Lab |
|
17-18 |
TBD |
Review. Exercises. Tutoring. Final Exam |
|
Final |
Assignments and Readings
Submission:
- English writing only.
- Homework FTP: ftp://public.sjtu.edu.cn/ (User Name: dr0dir Password: public)
- Grading Webpage: http://202.120.38.29 (User Name: StudentID)
- Late submission is not accepted.
Lecture 1: Introduction to Computability
- Reading Materials
- Syllabus & Grading Policy: Syllabus-ComputabilityTheory.pdf
- History of Computability: Slide01-History.pdf (Print Version: 01-History.pdf)
- Prologue: Slide02-Prologue.pdf (Print Version: 02-Prologue.pdf)
- Textbook: http://pan.baidu.com/s/1NjyTw
- Homework 1: Proof (Due: 1:00pm, 3/01/2016)
- Complete self-introduction: http://www.sojump.com/jq/7212736.aspx
- Lab01-Proof: Lab01-Proof.pdf
- Latex Source: Lab01-Proof.tex
Please also send the source file to TA for his correction if you use Latex (Upload a folder, rename your submission as Lab01-LastnameFirstname.XXX). - Latex Help Document: Chinese.pdf, English.pdf
- Answer Key: Lab01-Solution.pdf
Lecture 2: Unlimited Register Machine (URM)
- Reading Materials
- Computable Functions: Slide03-URM.pdf (Print Version: 03-URM.pdf)
- (Optional) Shepherdson, J. C. and Sturgis, H. E., Computability of Recursive Functions, Journal of ACM, 10, 217-55, 1963: URM-Original.pdf
- An Interesting Webpage: URM Simulator.html
- Homework 2: URM
- Lab02-Unlimited Register Machines: Lab02-URM.pdf
- Latex Source: Lab02-URM.tex
- Answer Key: Lab02-Solution.pdf
Lecture 3: Recursive Function
- Reading Materials
- Recursive Function: Slide04-RecursiveFunction.pdf (Print Version: 04-RecursiveFunction.pdf)
- Wikipedia page for Ackermann Function: AckermannFunction.html
- Homework 3: Recursive Function (Due: 1:00pm, 3/15/2016)
- Lab03-Recursive Function: Lab03-RecursiveFunction.pdf
- Latex Source: Lab03-RecursiveFunction.tex
- Answer Key: Lab03-Solution.pdf
Lecture 4: Church's Thesis
- Reading Materials
- Church's Thesis: Slide05-ChurchThesis.pdf (Print Version: 05-ChurchThesis.pdf)
- Homework 4: Church's Thesis (Due: 1:00pm, 3/22/2016)
- Lab04-ChurchThesis: Lab04-ChurchThesis.pdf
- Latex Source: Lab04-ChurchThesis.tex
- Answer Key: Lab04-Solution.pdf
Lecture 5: Godel Coding
- Reading Materials
- Godel Coding: Slide06-GodelCoding.pdf (Print Version: 06-GodelCoding.pdf)
- Cantor's Diagonal Argument: Wikipedia Page
- Pairing Function: Wikipedia Page
- Homework 5: Numbering Programs (Due: 1:00pm, 3/29/2016)
- Lab05-Numbering Programs: Lab05-NumberingPrograms.pdf
- Latex Source: Lab05-NumberingPrograms.tex
- Picture: Fig-Pairing.png
- Answer Key: Lab05-Solution.pdf
Lecture 6: Universal Programs
- Reading Materials
- Universal Programs: Slide07-UniversalProgram.pdf (Print Version: 07-UniversalProgram.pdf)
- Homework 6: Universal Program (Due: 1:00pm, 4/05/2016)
- Lab06-Universal Program: Lab06-UniversalProgram.pdf
- Latex Source: Lab06-UniversalProgram.tex
- Answer Keys: Lab06-Solution.pdf
Lecture 7: Undecidability and Partial Decidability
- Reading Materials
- Undecidability: Slide08-Undecidability.pdf (Print Version: 08-Undecidability.pdf)
- Polynomial Time Reduction: Wikipedia Page
- Homework 7: Undecidability (In Class)
- Lab07-Undecidability: Lab07-Undecidability.pdf
- Answer Keys: Lab07-Undecidability.pdf (PSD: CS363-Decidability)
Lecture 8: Midterm Review and Exercises
- Reading Materials
- CheckList: CheckList01-Midterm.pdf
- No Homework This Week ~~~O(∩_∩)O~
Lecture 9-10: Recursively Enumerable Set
- Reading Materials
- R. Set & R. E. Set : Slide09-RESet.pdf (Print Version: 09-RESet.pdf)
- Wikipedia Page: Recursively Enumerable Set
- Homework 8: Recursively Enumerable Set (Due: 1:00pm, 5/03/2016)
- Lab08-Recursively Enumerable Set: Lab08-RESet.pdf
- Latex Source: Lab08-RESet.tex
- Answer Key: Lab08-Solution.pdf
- Homework 9: R. E. Set 2 (Due: 1:00pm, 5/10/2016)
- Lab09-R. E. Set: Lab09-RESet2.pdf
- Latex Source: Lab09-RESet2.tex
- Answer Key: Lab09-Solution.pdf
Lecture 11: Various Sets
- Reading Materials
- Comparison Table: Table01-VariousSets.pdf
- Homework 10: Various Sets (Due: 1:00pm, 5/17/2016)
- Lab10-Various Set: Lab10-VariousSets.pdf
- Latex Source: Lab10-VariousSets.tex
- Answer Key: Lab10-Solution.pdf
Lecture 12: Reducibility and Degree
- Reading Materials
- Reducibility and Degree: Slide10-Reducibility.pdf (Print Version: 10-Reducibility.pdf)
- Homework 11: Reducibility and Degree (Due: 1:00pm, 05/24/2016)
- Lab11-Reducibility: Lab11-Reducibility.pdf
- Latex Source: Lab11-Reducibility.tex
- Answer Key: Lab11-Solution.pdf
Lecture 13: Reduction and NP-Completeness
- Reading Materials
- Reduction: Slide11-Reduction.pdf (Print Version: 11-Reduction.pdf)
* Reference01-Reduction.pdf --Chapter 8.1-8.4, 8.9-8.10 in "Algorithm Design" by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005.
- Reduction: Slide11-Reduction.pdf (Print Version: 11-Reduction.pdf)
- Homework 12: Reduction (Due: 1:00pm, 5/31/2016)
- Lab12-Reduction: Lab12-Reduction.pdf
- Latex Source: Lab12-Reduction.tex
- Answer Keys: Lab12-Solution.pdf
- Lab12-Reduction: Lab12-Reduction.pdf
Lecture 14: NP-Reduction
- Reading Materials
- Reduction: Slide12-NPReduction.pdf (Print Version: 12-NPReduction.pdf)
* Reference02-NPReduction.pdf --Chapter 8.5-8.8 in "Algorithm Design" by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005. - Reduction Application: Slide13-ReductionApplication.pdf (Print Version: 13-ReductionApplication.pdf)
- Reduction: Slide12-NPReduction.pdf (Print Version: 12-NPReduction.pdf)
- Homework 13: NPReduction (Due: 1:00pm, 6/07/2016)
- Lab13-NPReduction: Lab13-NPReduction.pdf
- Latex Source: Lab13-NPReduction.tex
- Answer Keys: Lab13-Solution.pdf
- Lab13-NPReduction: Lab13-NPReduction.pdf
Lecture 15: Final Review
- Reading Materials
- CheckList: CheckList02-Final.pdf
- SymbolList: SymbolList-Final.pdf
- Course Evaluation Survey (Anonymous)
- Please fill out the survey and help me improve my course, Thanks~~~m(_ _)m
- URL: http://www.sojump.com/jq/8668897.aspx
- Office Hour for Final: 10:00am-11:59am, Tuesday, 6/14/2016 at SEIEE 3-328
Roster and Events
|
References
- Recursive Function:
- Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, by Robert I. Soare, published by Springer-Verlag Berlin Heidelberg, 1987.
- Computational Complexity:
- Theory of Computational Complexity, by Ding-Zhu Du, and Ker-I Ko, published by John Wiley & Sons, Inc., 2000.
- Introduction to Languages and the Theory of Computation, by John Martin, published by McGraw-Hill, 2002.