Funciones recursivas primitivas para programadores de trabajo real

Funciones recursivas primitivas: una guía para programadores en la práctica

Los programadores suelen usar el término "completitud de Turing". En ciertos dominios, no ser Turing-completo a veces se considera una virtud o un requisito. Sin embargo, la mayoría de las discusiones se basan en información errónea. Lo que realmente significa no ser Turing-completo es otra cosa. La completitud de Turing es un término matemático con un significado muy específico. No está permitido reinterpretarlo para otros usos.

Parte I: resumen

• Si un programa escrito en un lenguaje Turing-completo se ejecuta más rápido que O(22N), entonces también puede implementarse en un lenguaje no Turing-completo.
• La mayoría de los problemas prácticos son más rápidos que "dos de dos de dos".
• Un lenguaje no Turing-completo no impone restricciones prácticas.
• Un programa que no termina y uno que tarda una cantidad enorme de tiempo en terminar se tratan de la misma manera.

Parte II: cómo funcionan las máquinas

Máquinas de estado finito (Finite State Machines)

• Una máquina de estado finito recibe una cadena como entrada y devuelve "sí" o "no".
• Tiene un número finito de estados.
• La función de transición de estado toma el estado actual y el siguiente símbolo de entrada, y devuelve un nuevo estado.
• Una máquina de estado finito no puede entrar en un bucle infinito.
• Una máquina de estado finito tiene el mismo poder expresivo que una expresión regular.

Máquinas de Turing (Turing Machines)

• Una máquina de Turing es un poco más compleja que una máquina de estado finito.
• Una máquina de Turing funciona usando una cinta variable.
• La función de transición de estado toma el estado actual y el símbolo actual de la cinta, y devuelve un nuevo estado, símbolo y dirección de movimiento.
• Una máquina de Turing funciona como una función y puede entrar en un bucle infinito.
• Una máquina de Turing puede simular una máquina de estado finito.

Programación de máquinas de Turing

• Una máquina de Turing tiene una cinta infinita.
• Una máquina de Turing no ejecuta un programa proporcionado por el usuario. El programa está codificado de forma fija en la máquina.
• Una máquina de Turing universal puede simular otras máquinas de Turing.
• Una máquina de Turing tiene la misma capacidad de cómputo que lenguajes como Python.

Límites de las máquinas de Turing

• Existen funciones que no pueden implementarse con una máquina de Turing.
• Se pueden enumerar todas las máquinas de Turing, pero no todas las funciones.
• Ciertos problemas (por ejemplo, el problema de la detención) no pueden resolverse con una máquina de Turing.
• La potencia de las máquinas de Turing hace imposible determinar si un programa terminará o no.

Parte III: volver a los problemas prácticos

Funciones recursivas primitivas (Primitive Recursive Functions)

• Las funciones recursivas primitivas reciben como entrada una tupla de números naturales y devuelven un número natural.
• Se construyen a partir de las funciones zero y succ.
• La recursión general no está permitida, pero sí se permiten formas restringidas de bucles.
• Se pueden definir operaciones como suma, multiplicación y exponenciación.
• Se pueden definir operadores lógicos y condicionales.
• Se usan números para representar estructuras de datos.

Resumen de GN⁺

• Este artículo fue escrito para ayudar a comprender la completitud de Turing y las funciones recursivas primitivas.
• Explica qué significa en la práctica no ser Turing-completo.
• Explica las diferencias entre las máquinas de estado finito y las máquinas de Turing, y analiza los límites de las máquinas de Turing.
• Explica la definición y el uso de las funciones recursivas primitivas.
• Este artículo ayudará a los programadores a mejorar su comprensión de la completitud de Turing y de las funciones recursivas primitivas.
• Entre los proyectos con funciones similares están las "expresiones regulares" y las "máquinas de estado finito".