Church y Turing, Las bases del cómputo

El cómputo actual ha surgido debido al planteamiento de diversas hipótesis o tesis que, pese a que no son del todo comprobables, han sentado las bases de la computación como la conocemos. Acontinuación se analizarán dos de estas teorías y se explicará porque una de ellas ha sido más trascendental que la otra.
Entscheidungsproblem… ¿Qué significa esto?
Su traducción literal es ‘problema dedecisión’. Pospuesto por David Hilbert, fue uno de los problemas más estudiados en la década de los 30’s, el cuál formulaba la pregunta: “Dada la proposición de un sistema formal, ¿existe algún algoritmoque pueda decidir si la proposición es cierta o falsa?” Fueron Alonzo Church y Alan Turing, de manera independiente, quienes se encargaron, de probar la imposibilidad de la existencia de talalgoritmo, utilizando el cálculo de lambda, en el caso de Church y la llamada máquina de Turing en el caso de Turing.
El cálculo de lambda, ideado por Alonzo Church, consiste en una regla de sustitución devariables, además de un esquema simple de definición de funciones. Church desarrolló originalmente este cálculo para fundamentar las matemáticas, sin embargo, al ser susceptible a la paradoja deRussell no se lo pudo aplicar como tal.
Por otra parte, Alan Turing, en su trabajo, “On computable numbers, with an application to the Entscheidungsproblem”, ideó una máquina hipotética, conocida comomáquina de Turing, la cual es un dispositivo de reconocimiento de lenguaje. Dicha máquina presenta el problema de parada (también conocido como problema de detención). Sin embargo, en su trabajo,estableció que dicho problema era indecible (como lo describen los teoremas de incompletitud de Gödel) en el sentido de que ninguna máquina de Turing lo podía resolver.
La principal diferencia entre ambasteorías es que, en el caso de Turing, plantea un dispositivo real, con aplicación más específica, mientras la teoría de Church se estanca en la generalidad. Si bien es cierto, que ambas teorías en...