Tag: logic

Mathematical Logic 2020

Lecture: HGX308, M 9:55-11:35
Section: HGX307, R 18:30-20:10

Slides 01 (handout) Slides 02 (handout) Slides 03 (handout) Slides 04 (handout) Slides 05 (handout) Slides 06 (handout) Slides 07 (handout) Slides 08 (handout) Slides 09 (handout) Slides 10 (handout) Slides 11 (handout) Slides 12 (handout) Slides 13 (handout) Slides 14 (handout) Slides 15 (handout) Slides 16 (handout) Slides 17 (handout)

为什么能行可计算的就是图灵可计算的（递归的）


这是对知乎问题为什么能行可计算的就是图灵可计算的 的回答。

如果我没理解错的话，题主想要问的实际上就是丘奇-图灵论题（Church-Turing Thesis）为什么成立。丘奇-图灵论题简单地说就是：

一个自然数上的函数\(f:\mathbb{N}^n\to\mathbb{N}\)是能行可计算的（effectively computable），当且仅当它是图灵可计算的（Turing computable）。
Continue reading “为什么能行可计算的就是图灵可计算的（递归的）”