4 Tres modelos matematicos de la computabilidad efectiva

Ya que el concepto de procedimiento efectivo es un concepto intuitivo, impresiso y a priori no expresado en el formalismo matematico, los conceptos de

  1. - Funcion Σ-efectivamente computable

  2. - Conjunto Σ-efectivamente computable

  3. - Conjunto Σ-efectivamente enumerable

tambien son impresisos y estan fuera del formalismo matematico, debido a que los tres se definen en terminos de la existencia de procedimientos efectivos. Por supuesto, los tres conceptos son fundamentales en el estudio teorico de la computabilidad por lo que es muy importante poder dar un modelo o formalizacion matematica de estos conceptos. Pero notese que los dos ultimos se definen en funcion del primero por lo que una formalizacion matematica precisa del concepto de funcion Σ-efectivamente computable, resuelve el problema de modelizar en forma matematica estos a tres conceptos.

En este capitulo daremos las tres modelizaciones matematicas mas clasicas del concepto de funcion Σ-efectivamente computable. La primera y la mas apegada a la idea intuitiva de procedimiento efectivo es la dada por Alan Turing via la matematizacion del concepto de maquina. Llamaremos a esta modelizacion el paradigma de Turing. La segunda, es la dada por Godel en su estudio de sistemas formales de la logica de primer orden. Llamaremos a esta modelizacion el paradigma de Godel o el paradigma funcional o el paradigma recursivo. Por ultimo veremos una formalizacion via un lenguaje de programacion imperativo. En honor a la influencia que tuvo Von Neumann en el diseño de la primer computadora de caracter universal (i.e. programable de proposito general), llamaremos a este paradigma el paradigma de Neumann o el paradigma imperativo. Dada la naturaleza filosofica e imprecisa del concepto de procedimiento efectivo y de sus conceptos derivados (i.e. funcion Σ-efectivamente computable, etc ) a este conjunto de conceptos fundamentales para las ciencias de la computacion lo llamaremos el paradigma filosofico. En honor al filosofo y matematico Gottfried Leibniz llamaremos tambien al paradigma filosofico el paradigma de Leibniz. Cabe destacar que Leibniz creo la primera maquina de calcular, llamada la Stepped Reckoner.

Con esta manera de hablar notese que los tres paradigmas matematicos, de Turing, Godel y Neumann intentan modelizar al paradigma de Leibniz. Para darle un toque de humor expresaremos esto diciendo que los tres intentan vencer a Leibniz.