Ya que el concepto de procedimiento efectivo es un concepto intuitivo, impresiso y a priori no expresado en el formalismo matematico, los conceptos de
adhocprefix-adhocsufix Funcion \(\Sigma\)-efectivamente computable
adhocprefix-adhocsufix Conjunto \(\Sigma\)-efectivamente computable
adhocprefix-adhocsufix Conjunto \(\Sigma\)-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 \(\Sigma\)-efectivamente computable, resuelve el problema de modelizar en forma matematica estos a tres conceptos.
En esta seccion daremos las tres formalizaciones matematicas mas clasicas del concepto de funcion \(\Sigma\)-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. La segunda, es la dada por Godel en su estudio de sistemas formales de la logica de primer orden. 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 imperativo de Von Neumann.