國立陽明大學心智哲學研究所 九十九學年度 第一學期 研究所課程

計算理論
Theory of Computability



授課教師王文方 教授

學分數3 學分

上課時間:星期一 14:30-17:30

上課教室:心哲所會議室

教學目標

當代認知科學的主流學派為計算學派,因此計算理論是任何計畫研究心靈哲學與相關形上學與
知識論問題的學生必備的知識基礎。本課程提供學生完整的計算理論。

授課進度

Date

Feature

Week 1

1. Enumerability

Week 2

2. Diagonalization

Week 3

3. Turing computability

Week 4

4. Uncomputability

Week 5

5. Abacus computability

Week 6

6. Recursive functions

Week 7

7. Recursive sets and relations

Week 8

8. Equivalent definitions of computability

Week 9

9. A precis of first-order logic: syntax

Week 10

10. A precis of first-order logic: semantics
11. The undecidability of first-order logic

Week 11

12. Models
13. The existence of models

Week 12

14. Proofs and completeness
15. Arithmetization

Week 13

16. Representability of recursive functions
17. Indefinability, undecidability, incompleteness

Week 14

18. The unprovability of consistency
19. Normal forms

Week 15

20. The Craig interpolation theorem
21. Monadic and dyadic logic

Week 16

22. Second-order logic
23. Arithmetical definability

Week 17

24. Decidability of arithmetic without multiplication
25. Non-standard models

Week 18

26. Ramsey's theorem
27. Modal logic and provability.


指定閱讀及參考書目

指定閱讀書目:
Boolos, G. S., Burgess, J. P., & Jeffrey, R. C. (2007). Computability and Logic (5th ed.).
Cambridg: Cambridge University Press.

教學方式

本課程以授課老師的介紹與講授帶領選課學生的參與討論,希望藉由老師提綱挈領的介紹,
引發學生對問題的更深層思考及討論。

成績考核

Mid-term exam: 30%
Final exam: 30%
Participations: 40%

 

 

版權所有 Copyright © 陽明大學心智哲學研究所