BASICS 2014 Summer SchoolLogic Summer School in China 2014 的主要讲授内容为:

  1. 有穷损害方法。美国逻辑学家 Post 曾提出过一个重要的问题:是否存在一个难度严格介于停机问题和可判定问题之间的递归可枚举问题,即是否存在一个介于00' 之间的 r.e. 图零度。这一问题最终被美国逻辑学家 Friedberg 和前苏联逻辑学家 Muchnik 独立解决。为了解决该问题,他们引入了有穷损害方法。后来该方法被广泛地应用于递归论中,并且被推广至无穷损害,0''' 方法,成为递归论的基本工具。

  2. 一般图灵度的结构。虽然Post问题被解决了,但仍然没有找到一个自然的介于 00'之间的图零度。后来 Sacks、Martin、Lachlan 等人形式化这一想法,试图从不同的角度解决这一问题。这些努力导致了后来的 Martin 猜想,Sacks 猜想等。这些猜想使得描述集合论、递归论、大基数、内模型理论等看似完全不同的逻辑分支得以深刻地结合。通过 Lachlan、Steel、Slaman 等人的工作,这一方向已取得重要进展。

  3. 算法随机性理论。算法随机性理论是由 Chaitin、Kolmogorov、Levin、Martin-Löf 等人创立的。这一领域是当前递归论最为热门的方向。递归论学家通过应用递归论的经典方法,解决了大量的长期悬而未决的算法随机性领域的公开问题。我们将对这一领域做初步的介绍。

预备知识:初步的数理逻辑知识,比如哥德尔不完备性定理及其证明。初等的递归论知识,包括图灵机,Church-Turing 论题等。

参考材料

  1. “Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets”, Chapter VII, Robert I. Soare, Springer 1987.
  2. “Degrees of Unsolvability: Local and Global Theory”, Chapter II and IV, Manuel Lerman, Springer 1983.
  3. “Algorithmic Randomness and Complexity Series: Theory and Applications of Computability”, Chapter 3 and 6, Downey, Rodney G., Hirschfeldt, Denis R. Springer 2010.
  4. “Computability and Randomness”, Chapter 2 and 3, André Nies, Oxford Logic Guides 2009.