Listas y funciones de listas

Abstract

Sobre una idea desarrollada por G. Jacopini (Universidad de Roma), se introduce un modelo adicional a los clásicos de funciones recursivas y máquinas de Turing. Este modelo, no común en la literatura, es de una enorme potencia didáctica. En su aparente sencillez permite familiarizarse rápidamente con conceptos de gran profundidad. El presente es la base estructural de un apunte de cátedra más completo. Los alumnos llegan a esta parte de la materia con un manejo del concepto clásico de funciones recursivas. El resultado principal que se ofrece es que este nuevo modelo “al menos” incluye al de las funciones recursivas. El tema que sigue (que se esboza brevemente al final de este trabajo) es la presentación de las máquinas de Turing y la demostración de la capacidad de estas de “contemplar” entre sus posibilidades las funciones recursivas de listas. La clásica demostración de que las máquinas de Turing pueden ser “representadas” por las funciones recursivas, cierra en belleza la presentación de estos tres modelos de cálculo, mostrando su equivalencia profunda.