Hacktoberfest 2026：维护者为十月标记出来的 issue，仍然开放、适合新手。 浏览 Hacktoberfest issue

Recursive functions and the Church-Turing thesis

未关闭
  • 哪里不对？
#232 4 条评论 1 个 reaction 已指派 0 人 在 GitHub 查看

还没有人认领这个 Issue。

评估

难度
4/5
预计耗时
3-5 天
新手友好度
25/100
Issue 类型
文档
描述清晰度
需要澄清
活跃度
停滞
技术栈
tex
领域
content

调研方向

该 issue 指向递归函数一章，尤其是第 2.1 节、第 2.14 节和章节摘要。首先将这些段落与所述的全函数和部分函数之间的区别进行比较；完成的标准是解决术语问题，并确定所有需要更正的文本。

由索引模型根据 Issue 内容生成。

描述

This issue is about the chapter on recursive functions. I'm using the Incompleteness and Computability book, so I'll refer to various parts of it as sections 2.x.

Here's what I've gathered so far, just so I don't get the terms mixed up:

  • Primitive recursive functions are zero, succ, and projection, closed under composition and recursion.
  • Partial recursive functions are the same as primitive recursive ones but additionally closed under unbounded search.
  • Recursive functions are partial recursive functions that are total.
  • General recursive functions are the same as primitive recursive ones but additionally closed under unbounded search over regular functions.
  • General recursive functions are the same as recursive functions.
  • Primitive r.f. ⊂ general r.f. ⊂ partial r.f.

In the Introduction (section 2.1), it states that by the Church-Turing thesis, recursive functions (so, general recursive functions) can simulate other models of computation, which means that general recursive functions are the same as Turing-computable functions. This is restated in section 2.14 on Non-Primitive Recursive Functions, as well as the summary at the end of the chapter.

But shouldn't Turing-computable functions correspond to partial recursive functions? It doesn't seem like general recursive functions could simulate Turing machines that don't halt on some inputs, since these functions are total. Turing machines could also compute partial recursive functions, and not halt on inputs where the function is undefined.

This was slightly difficult to look up, since other sources (e.g. Wikipedia) use the term "(general) recursive function" to mean what we would call partial recursive functions, while others use "total recursive function" to mean what we would call general recursive functions. But in any case, it seems that the functions involved in computability should at least be partial.

主要语言
TeX
星标
1.4k
派生
289
30 天内没有已合并 PR

环境准备

这个项目没有提供开发容器、Dockerfile 或贡献指南，环境需要你自己搭建：先看它的 README，通用步骤见我们的新手贡献指南。

从这里开始

  1. 先读完整个 Issue，再读项目的贡献指南。
  2. 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
  3. Fork 仓库，在一个分支上完成修改。
  4. 提交 Pull Request，并在描述里引用这个 Issue 编号。

OpenLogicProject/OpenLogic 的其他 Issue

查看 OpenLogicProject/OpenLogic 的全部 Issue

相似的 Issue

更多 Content Issue

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。