Las Funciones Recursivas de Lista (FRL), en el contexto de la teoría de la computabilidad, son un modelo de cálculo que toma a la lista finita de números naturales como tipo de dato nativo del cálculo y utiliza una pequeña cantidad base de herramientas constructivas que permite representar las funciones computables.

A partir de las funciones recursivas de lista pueden ser construídos todos los conceptos base de la fundamentación del cálculo y tienen una capacidad de modelizar el cálculo equivalente a las Funciones recursivas y a las Máquinas de Turing.

Este modelo de cálculo fue creado por el matemático e informático teórico italiano Giuseppe Jacopini para los cursos de lógica matemática que dictara en la Universidad de Roma La Sapienza a finales de la década de 1970 y posteriormente fue adoptado por Raúl Kantor para el dictado en la materia Lenguajes Formales y Computabilidad de la licenciatura en ciencias de la computación de la Facultad de Ciencias Exactas, Ingeniería y Agrimensura en la Universidad Nacional de Rosario.

Definiciones formales

Listas finitas Se nota al conjunto de todas las listas finitas de elementos de los números naturales (incluyendo el 0). Se incluye en ese conjunto la lista vacía . Se representan tales listas con la notación con .

La longitud de una lista es el número de elementos que posee. Para cada se nota con el conjunto de las listas que poseen exactamente elementos. Similarmente, se nota con al conjunto de las listas que poseen al menos elementos y con al conjunto de las listas que poseen como máximo elementos.

Concatenación de listas

La operación fundamental en es la concatenación. Dadas dos listas e se denomina concatenación de X e Y a la lista .

Se puede notar o para indicar la lista obtenida de concatenar la lista X con la lista Y. También se pueden usar notaciones como o para distinguir particularmente algunos elementos y para notar la concatenación de múltiples listas simultáneamente.

Funciones de lista

Se llaman funciones de lista a las funciones que tienen como dominio a y como codominio también a . Las notaremos con letras mayúsculas como F y G. Dada una función de lista F se indica el dominio de la función como . También se nota la operación de una función F sobre una lista dada con .

Referencias

Enlaces externos

Giuseppe Jacopini (Wikipedia en italiano)

Categoría:Computación Categoría:Computabilidad Categoría:Ciencias de la computación Categoría:Lógica Categoría:Lenguajes formales