Funciones recursivas y máquinas de registros

La teoría de funciones recursivas construye las funciones computables a partir de un puñado de operaciones básicas, mientras que las máquinas de registros computan con números enteros almacenados en registros, dos modelos que enmarcan la máquina de Turing y confirman la robustez de la computabilidad.

Definition

Las funciones recursivas generales son aquellas construidas a partir de constantes, sucesor y proyecciones mediante composición, recursión primitiva y minimización no acotada; las máquinas de registros son dispositivos abstractos que computan incrementando, decrementando y probando el contenido de un conjunto finito de registros que contienen números naturales.

Scope

Este tema abarca las funciones recursivas primitivas, la adición de minimización no acotada para obtener las funciones recursivas generales, la función de Ackermann como una función computable que no es recursiva primitiva, las máquinas de registros y contadores y su universalidad, y la equivalencia de todos estos modelos con la computabilidad de Turing.

Core questions

• ¿Cómo se pueden definir las funciones computables aritméticamente sin ninguna máquina?
• ¿Por qué se necesita la minimización no acotada más allá de la recursión primitiva?
• ¿Cómo logran las máquinas de registros simples todo el poder de la computación?
• ¿Por qué estos modelos aritméticos y de máquinas coinciden con las máquinas de Turing?

Key theories

Equivalencia con la computabilidad de Turing

Las funciones recursivas generales y las funciones computadas por máquinas de registros son exactamente las funciones computables por Turing, lo que refuerza la tesis de Church-Turing a través de modelos definidos en términos puramente aritméticos y de máquinas elementales.

Más allá de la recursión primitiva

La función de Ackermann es total y computable, pero crece demasiado rápido para ser recursiva primitiva, lo que demuestra que la búsqueda no acotada es esencial y que las funciones recursivas primitivas son una subclase propia de las computables.

Universalidad de las máquinas de registros

Minsky demostró que una máquina con solo dos contadores y las operaciones de incremento, decremento y prueba de cero ya es Turing-completa, una demostración extrema de lo poco que requiere la computación completa.

Clinical relevance

Las máquinas de registros modelan la aritmética de enteros de los procesadores reales de forma más directa que las cintas, la recursión primitiva corresponde a programas que siempre terminan y subyace a los lenguajes funcionales totales y al análisis de terminación, y la visión de la función recursiva conecta la computación con los fundamentos de las matemáticas.

History

Gödel y Herbrand definieron las funciones recursivas generales a principios de la década de 1930, y Kleene desarrolló la teoría, incluyendo el papel de la minimización. Ackermann había exhibido anteriormente su función de crecimiento rápido, y Minsky introdujo las máquinas de registros y contadores en la década de 1960, demostrando la universalidad incluso de las máquinas de dos contadores.

Key figures

• Kurt Gödel
• Stephen Kleene
• Wilhelm Ackermann
• Marvin Minsky

Seminal works

• cutland1980
• minsky1967

Frequently asked questions

¿Cuál es la diferencia entre funciones recursivas primitivas y funciones recursivas generales?

Las funciones recursivas primitivas se construyen utilizando bucles acotados y siempre terminan, pero no capturan todas las funciones computables. La adición de la minimización no acotada, una búsqueda que puede ejecutarse indefinidamente, produce las funciones recursivas generales, que coinciden exactamente con las funciones computables por Turing.

¿Cómo puede una máquina con solo dos contadores ser tan potente como una computadora?

Minsky demostró que dos registros que contienen números naturales, con solo incremento, decremento y prueba de cero, pueden simular una máquina de Turing codificando su cinta en los registros. La construcción es muy ineficiente, pero demuestra que un hardware mínimo ya alcanza todo el poder de la computación.