Today at 2 p.m., I will talk at Fudan Logic Seminar about natural reducts of set theory models.
Tag: logic
为什么能行可计算的就是图灵可计算的（递归的）
这是对知乎问题为什么能行可计算的就是图灵可计算的 的回答。
如果我没理解错的话，题主想要问的实际上就是丘奇-图灵论题（Church-Turing Thesis）为什么成立。丘奇-图灵论题简单地说就是：
一个自然数上的函数\(f:\mathbb{N}^n\to\mathbb{N}\)是能行可计算的（effectively computable），当且仅当它是图灵可计算的（Turing computable）。
Continue reading “为什么能行可计算的就是图灵可计算的（递归的）”
集合论和一阶逻辑的关系？
有朋友在知乎上问：
http://logic.fudan.edu.cn/doc/Course/2014/MathLogic/Lecture01.pdf 最后一段：
- 集合论可以被看作是一种一阶逻辑理论
- 一阶逻辑的语法、语义概念都可以在集合论中定义， 关于一阶逻辑的定理可以被看作是集合论的定理
建立一阶逻辑时貌似很多定义都用了集合论描述。而集合论本身又可以被看作是一种一阶逻辑理论。不是有循环定义的嫌疑吗？
我在知乎的回答如下： Continue reading “集合论和一阶逻辑的关系？”