Un concepto importante en ciencias de la computación es el de procedimiento o método para realizar alguna tarea determinada. Nos interesan los procedimientos que están definidos en forma precisa e inambigua, es decir aquellos en los cuales en cada paso a seguir, la tarea a realizar esta objetivamente descripta. También deben ser repetibles, en el sentido de que si realizamos un procedimiento dos veces con el mismo dato de entrada, entonces ambas ejecuciones deben ser idénticas, es decir se realizaran las mismas tareas y en el mismo orden.
Nos interesan los procedimientos \(\mathbb{P}\) que posean las siguientes características:
adhocprefix(1)adhocsufix El interprete o ejecutante de \(\mathbb{P}\) es una persona que trabajara con papel y lápiz (ambos recursos disponibles en forma ilimitada).
adhocprefix(2)adhocsufix Cada paso o tarea que \(\mathbb{P}\) encomiende a realizar debe ser simple y fácil de realizar en forma efectiva por cualquier persona.
adhocprefix(3)adhocsufix El procedimiento \(\mathbb{P}\) comienza a funcionar siempre a partir de cierto dato de entrada y una ves que haya comenzado, siempre sucederá una de las dos siguientes posibilidades
adhocprefix(a)adhocsufix \(\mathbb{P}\) luego de cierta cantidad de pasos realizados, se detiene y da cierto dato de salida
adhocprefix(b)adhocsufix \(\mathbb{P}\) nunca se detiene, es decir a medida que se van realizando las instrucciones o tareas, \(\mathbb{P}\) siempre direcciona a realizar nuevas tareas y lo hace sucesiva e indefinidamente.
En el caso (a) diremos que \(\mathbb{P}\) se detiene partiendo del dato de entrada en cuestión y en el caso (b) diremos que \(\mathbb{P}\) no se detiene partiendo de dicho dato
adhocprefix(4)adhocsufix Hay \(n,m\in\omega\) y un alfabeto \(\Sigma\) tales que el conjunto de datos de entrada de \(\mathbb{P}\) es \(\omega^{n}\times\Sigma^{\ast m}\). Cabe aclarar que para ciertas \((n+m)\)-uplas de \(\omega^{n}\times\Sigma^{\ast m}\) el procedimiento \(\mathbb{P}\) se detendrá y para ciertas otras no lo hará.
Llamaremos procedimientos efectivos a aquellos procedimientos que posean las características arriba mencionadas.
El conjunto de datos de salida de \(\mathbb{P}\) es el conjunto de todos los datos que el procedimiento \(\mathbb{P}\) dará como salida en alguna de las posibles ejecuciones al variar todos los datos de entrada posibles. Si bien siempre el conjunto de datos de entrada será de la forma \(\omega^{n}\times\Sigma^{\ast m}\), puede ser muy difícil o imposible, en general, conocer con precisión el conjunto de datos de salida de un procedimiento (esto lo justificaremos mas adelante).
Ya que el interprete de \(\mathbb{P}\) es una persona dotada de lápiz y papel, supondremos que los elementos de \(\omega\) que intervienen en los datos de entrada y de salida estarán representados por palabras de \(Num\) usando la notación decimal clásica (i.e. con 0).
Quizás el procedimiento efectivo mas famoso de la matemática es aquel que se enseña en los colegios para sumar dos números naturales expresados en notación decimal. Notar que el conjunto de datos de entrada de dicho procedimiento es \(\omega^{2}\) y el conjunto de datos de salida es el conjunto formado por todas las sumas posibles de pares de elementos de \(\omega\), es decir \(\omega\). Por supuesto este procedimiento solo usa lápiz, papel y pasos extremadamente simples a seguir en cada momento de la computación, es decir, en algún sentido, no es necesario "entender que es lo que se esta haciendo" para llegar al final y obtener la palabra que representa en notación decimal a la suma de los números iniciales. Dejamos al lector repasar este procedimiento así como el que calcula dado un número \(x\) no nulo de \(\omega\), al número \(x-1\), los cuales nos harán falta mas adelante en los ejemplos.