Recursive functions and the Church-Turing thesis

Aberta
  • Algo errado?
#232 4 comentários 1 reação 0 responsáveis Ver no GitHub

Ninguém assumiu esta issue ainda.

Avaliação

Dificuldade
4/5
Tempo estimado
3-5 dias
Facilidade para iniciantes
25/100
Tipo de issue
Documentação
Clareza
Precisa de esclarecimento
Status de atividade
Estagnada
Stack de tecnologia
tex
Domínio
content

Direção de pesquisa

A issue aponta para o capítulo sobre funções recursivas, especialmente as seções 2.1 e 2.14 e o resumo do capítulo. Comece comparando essas passagens com a distinção indicada entre funções totais e parciais; o trabalho estará concluído quando a terminologia tiver sido resolvida e qualquer texto que precise de correção tiver sido identificado.

Escrita pelo modelo de indexação a partir do texto da issue.

Descrição

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.

Linguagem predominante
TeX
Estrelas
1.4k
Forks
292
Nenhum PR com merge em 30d

Preparar o ambiente

Este projeto não oferece contêiner de desenvolvimento, Dockerfile nem guia de contribuição, então a configuração fica por sua conta: comece pelo README e veja nosso guia da primeira contribuição para os passos gerais.

Primeiros passos

  1. Leia a issue inteira e depois o guia de contribuição do projeto.
  2. Comente na issue dizendo que vai assumir — evita que duas pessoas façam o mesmo trabalho.
  3. Faça um fork do repositório e trabalhe em uma branch.
  4. Abra um pull request que referencie o número da issue.

Mais de OpenLogicProject/OpenLogic

Todas as issues de OpenLogicProject/OpenLogic

Issues semelhantes

Mais issues de Content

Receba novas issues na sua caixa de entrada

Um resumo curto de issues do GitHub para quem está começando.