计算理论¶

计算理论研究最根本的问题：什么是可计算的？计算的边界在哪里？课程从离散数学的工具出发，建立字母表、字符串和语言的形式化定义（Kleene 星、拼接、幂运算），讨论关系性质、等价关系、偏序、等势性以及康托定理的对角线证明。在形式语言层面，依次覆盖正则语言与有限自动机（及其等价性证明）、上下文无关语言与下推自动机，最终引入图灵机的形式化定义——五元组 \((K, \Sigma, \delta, s, H)\)、转移函数、配置和状态转换，并以此为基础严格证明不可判定性问题的存在。

专业课学习，授课老师：郑乾。