Un concepto importante en ciencias de la computacion es el de procedimiento o metodo para realizar alguna tarea determinada. Nos interesan los procedimientos que estan definidos en forma precisa e inambigua, es decir aquellos en los cuales en cada paso a seguir, la tarea a realizar esta objetivamente descripta. Tambien 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 identicas, es decir se realizaran las mismas tareas y en el mismo orden.
Nos interesan los procedimientos \(\mathbb{P}\) que posean las siguientes caracteristicas:
Siempre supondremos que el interprete o ejecutante de \(\mathbb{P}\) es una persona que trabajara con papel y lapiz (ambos recursos disponibles en forma ilimitada).
Cada paso o tarea que \(\mathbb{P}\) encomiende a realizar debe ser simple y facil de realizar en forma efectiva por cualquier persona.
El procedimiento \(\mathbb{P}\) comienza a funcionar siempre a partir de cierto dato de entrada y una ves que haya comensado, siempre sucedera una de las dos siguientes posibilidades
\(\mathbb{P}\) luego de cierta cantidad de pasos realizados, se detiene y da cierto dato de salida
\(\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 cuestion y en el caso (b) diremos que \(\mathbb{P}\) no se detiene partiendo de dicho dato
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 detendra y para ciertas otras no lo hara.
Llamaremos procedimientos efectivos a aquellos procedimientos que posean las caracteristicas arriba mencionadas.
El conjunto de datos de salida de \(\mathbb{P}\) es el conjunto de todos los datos que el procedimiento \(\mathbb{P}\) dara 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 sera de la forma \(\omega^{n}\times\Sigma^{\ast m}\), puede ser muy dificil o imposible, en general, conocer con precision 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 lapiz y papel, supondremos que los elementos de \(\omega\) que intervienen en los datos de entrada y de salida estaran representados por palabras de \(Num\) usando la notacion decimal clasica (i.e. con 0).
Quisas el procedimiento efectivo mas famoso de la matematica es aquel que se enseña en los colegios para sumar dos numeros naturales expresados en notacion 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 lapiz, papel y pasos extremadamente simples a seguir en cada momento de la computacion, es decir, en algun sentido, no es necesario "entender que es lo que se esta haciendo" para llegar al final y obtener la palabra que representa en notacion decimal a la suma de los numeros iniciales. Dejamos al lector repasar este procedimiento asi como el que calcula dado un numero \(x\) no nulo de \(\omega\), al numero \(x-1\), los cuales nos haran falta mas adelante en los ejemplos.