Hacktoberfest 2026: los issues que los mantenedores marcaron para octubre, abiertos y aptos para principiantes. Explorar issues de Hacktoberfest

Recursive functions and the Church-Turing thesis

Abierto
  • ¿Algo no está bien?
#232 4 comentarios 1 reacción 0 asignados Ver en GitHub

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
4/5
Tiempo estimado
3-5 días
Aptitud para principiantes
25/100
Tipo de issue
Documentación
Claridad
Necesita aclaración
Estado de actividad
Estancado
Stack tecnológico
tex
Área
content

Línea de trabajo

El issue apunta al capítulo sobre funciones recursivas, especialmente a las secciones 2.1 y 2.14 y al resumen del capítulo. Empieza comparando esos pasajes con la distinción indicada entre funciones totales y parciales; el trabajo estará terminado cuando se haya resuelto la terminología y se haya identificado cualquier texto que necesite corrección.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

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.

Lenguaje dominante
TeX
Estrellas
1.4k
Forks
289
Sin PR fusionados en 30 d

Preparar el entorno

Este proyecto no incluye contenedor de desarrollo, Dockerfile ni guía de contribución, así que la configuración corre por tu cuenta: empieza por su README y consulta nuestra guía para la primera contribución para los pasos generales.

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de OpenLogicProject/OpenLogic

Todos los issues de OpenLogicProject/OpenLogic

Issues similares

Más issues de Content

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.