OpenLogicProject / OpenLogicProject/OpenLogic

Recursive functions and the Church-Turing thesis

Open
#232 4 comments 1 reaction 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
TeX
Stars
1.4k
Forks
288
PR merge metrics
No merged PRs in 30d

Description

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.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

The issue points to the chapter on recursive functions, especially sections 2.1 and 2.14 and the chapter summary. Start by comparing those passages with the stated distinction between total and partial functions; done means resolving the terminology and identifying any text that needs correction.

Written by the indexing model from the issue text.

Assessment

Tech stack
tex
Domain
content
Issue type
Documentation
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.