Ya que el concepto de procedimiento efectivo es un concepto intuitivo, impreciso y a priori no expresado en el formalismo matemático, los conceptos de
adhocprefix-adhocsufix Función \(\Sigma\)-efectivamente computable
adhocprefix-adhocsufix Conjunto \(\Sigma\)-efectivamente computable
adhocprefix-adhocsufix Conjunto \(\Sigma\)-efectivamente enumerable
también son imprecisos y están fuera del formalismo matemático, debido a que los tres se definen en términos de la existencia de procedimientos efectivos. Por supuesto, los tres conceptos son fundamentales en el estudio teórico de la computabilidad por lo que es muy importante poder dar un modelo o formalización matemática de estos conceptos. Pero nótese que los dos últimos se definen en función del primero por lo que una formalización matemática precisa del concepto de función \(\Sigma\)-efectivamente computable, resuelve el problema de modelizar en forma matemática estos tres conceptos.
En este capítulo daremos las tres modelizaciones matemáticas mas clásicas del concepto de función \(\Sigma\)-efectivamente computable. La primera y la mas apegada a la idea intuitiva de procedimiento efectivo es la dada por Alan Turing vía la matematización del concepto de máquina. Llamaremos a esta modelización el paradigma de Turing. La segunda, es la dada por Godel en su estudio de sistemas formales de la lógica de primer orden. Llamaremos a esta modelización el paradigma de Godel o el paradigma funcional o el paradigma recursivo. Por último veremos una formalización vía un lenguaje de programación imperativo. En honor a la influencia que tuvo Von Neumann en el diseño de la primer computadora de carácter universal (i.e. programable de propósito general), llamaremos a este paradigma el paradigma de Neumann o el paradigma imperativo. Dada la naturaleza filosófica e imprecisa del concepto de procedimiento efectivo y de sus conceptos derivados (i.e. función \(\Sigma\)-efectivamente computable, etc) a este conjunto de conceptos fundamentales para las ciencias de la computación lo llamaremos el paradigma filosófico. En honor al filosofo y matemático Gottfried Leibniz llamaremos también al paradigma filosófico, el paradigma de Leibniz. Cabe destacar que Leibniz creo la primera máquina de calcular, llamada la Stepped Reckoner.
Con esta manera de hablar nótese que los paradigmas matemáticos de Turing, Godel y Neumann intentan modelizar al paradigma de Leibniz. Para darle un toque de humor expresaremos esto diciendo que Turing, Godel y Neumann intentan vencer a Leibniz.