El concepto de "computabilidad" es uno de los pilares fundamentales de la matemática moderna. Se han elaborado diferentes teorías, todas ellas equivalentes, para precisar el concepto de computabilidad pero me interesa resaltar por su simplicidad y accesibilidad la teoría que Alan Turing elaboró en los años 30.
El proceso de elaboración de la teoría de lo computable arranca y completa otra teoría matemática más antigua y fundamental: la teoría de los algoritmos. Inicialmente un algoritmo era una secuencia ordenada de operaciones que resolvían determinados problemas matemáticos de un mismo tipo. Por ejemplo, utilizamos frecuentemente en matemáticas básicas el algoritmo (el procedimiento) para multiplicar dos números dados, o también el que permite extraer la raiz cuadrada o el algoritmo que resuelve ecuaciones de segundo grado.
Cualquier algoritmo se define en términos matemáticos empleando simbolos de un conjunto dado y aplicando determinadas reglas de combinación entre los mismos. Con ello obtenemos un "mensaje" compuesto por una cadena de símbolos que tiene un determinado significado. LA cadena de símbolos puede a su vez traducirse a una cadena meramente numérica aplicando un sistema dado de codificación. De esta forma entonces cualquier algoritmo escrito en cualquier sistema de símbolos puede ser transformado en un mensaje puramente numérico. Por ejemplo: "el cuadrado de la suma de dos números es la suma de los cuadrados de cada uno de ellos mas el doble del producto del primero por el segundo". O también podemos codificarlo como:
(a + b)2 = a2 + b2 + 2*a*b.
Pero también aplicando una codificación estrictamente numérica puede resultar como: 00012202000022110100222202002222233013302
Uno de los algoritmos más populares y antiguos es el algoritmo de Euclides que determina el máximo número que es a la vez divisor de dos dados. Los árabes tomaron el relevo de la matemática griega desarrollando la geometría y la aritmética. En concreto generalizaron la expresión de "2+3" mediante la expresión "a+b", es decir pasaron de la aritmética de los números a la aritmética de los símbolos inventando el "algebra". El posterior desarrollo del álgebra incluye la teoría de algoritmos. De hecho la palabra algebra viene del título del libro xxxxxxxxxxxx que significa xxxxxx. La palabra algoritmo procede del nombre de su autor xxxxxxxx, matemático árabe.
Los matemáticos pretendían encontrar cada vez algoritmos más generales que resolvieren problemas de clases cada vez más amplias también. Por ejemplo, si tenemos algoritmos para determinar las raices de ecuaciones de segundo grado porqué no buscar un algoritmo que determine las raices de una ecuación de grado n. De esta forma se intentaba dar respuesta a la pregunta de si existía un superalgoritmo que diese respuesta a cualquier problema matemático. Pero los matemáticos se toparon con la evidencia de que ni siquiera para determinados problemas parecía existir algoritmo. Además del lado de la lógica matemática vino una aportación también desalentadora de la mano de K. Gödel, ya que demostró que existen sismemas de códigos y reglas los cuales no eran capaces de demostrar si una sentencia o mensaje generado dentro del propio sistema era verdadera o falsa (o dicho de otro modo, con estos conjuntos de reglas y símbolos se podía construir un mensaje que a priori dentro del propio sistema no podía decirse si era verdadero o falso, como por ejemplo la frase: "esta frase es falsa"; lo que en matemática se denominaban sistemas incompletos).
En esta búsqueda infructuosa de superalgoritmos los matemáticos se dieron cuenta de que para responder a la pregunta de si existía ese tal superalgoritmo debía precisarse conpletamente qué era un algoritmo. En este punto entra la definición que de algoritmo elaboraron Alan Turing y Emile Post mediantes sendas máquinas teóricas: la máquina de Turing y la máquina de Post.
Turing y POst en realidad buscaban una definición de computabilidad, es decir una definición de qué y cómo algp puede ser computable o calculable. Para ello centraron sus argumentaciónes en torno a unas máquinas de computar teóricas que se denominaron popularmente como máquinas de Turing y Post respectivamente. Así hablamos de números "turingcomputables", funciones "turingcomputables" etc, cuando pueden calcularse por medio de una máquina de turing y de forma similar también en una máquina de Post.
