recursos

1

Influencias de la Lógica Matemática en las Ciencias de la Computación
Martin DAVIS
Courant Institute of Mathematical Sciences
New York University
______________________________________________________________________
El siguiente texto es una traducción parcial de la conferencia que David ofreció con el
título “Influences of Mathematical Logic on Computer Science” en ocasión de los 50años del célebre artículo de Alan Turing sobre teoría de la computabilidad, “On
Computable Numbers, with an Application to the Entscheidungssproblem”, en 1987.
La traducción castellana es de Facundo García Valverde
______________________________________________________________________

Cuando yo era estudiante, hasta los topólogos consideraban que los lógicos
matemáticos vivían en elespacio exterior. Hoy en día, las conexiones entre la lógica y
la computación son un asunto de práctica ingenieril en cada nivel de la organización
computacional: abundan compañías con nombres como Logical Devices o Logicsoft;
uno puede ingresar en un negocio y pedir “una prueba lógica”. De ninguna manera esto
es sólo una cuestión de términos. Los temas y conceptos que surgieron por primera vez
enlas investigaciones técnicas llevadas a cabo por los lógicos están estrechamente
vinculados con muchos aspectos de la Ciencia de la Computación.
¿Hasta qué punto el trabajo previo de los lógicos influyó en los científicos e
ingenieros en computación? ¿Usaron lo ya hecho o simplemente “inventaron la
pólvora” como algo necesario? Lamentablemente, es mucho más sencillo señalar las
confluenciasde ideas que trazar rigurosamente un camino desde el trabajo original hasta
sus aplicaciones. Cuando las ideas en cuestión son verdaderamente fundamentales y,
por lo tanto, finalmente simples (del mismo modo en que tantos conceptos
fundamentales resultan serlo) la gente olvida fácilmente lo sorprendente que fueron esas
ideas cuando se enunciaron por primera vez. Tales ideas pueden transformarsede algo
absurdo a una trivialidad en pocos años. En Davis (1987) se discuten extensamente
algunos de estos temas y se relacionan con el rol que jugó el descubrimiento de la
máquina universal de calcular, realizado por Alan Türing, en el desarrollo actual de las
modernas computadoras electrónicas. En este ensayo, seguiremos el camino de un
conjunto de conceptos que surgieron en el trabajo delos lógicos y que encontraron su
lugar en la teoría y práctica computacional.
Sintaxis formal
Una de las primeras cosas que un usuario principiante debe aprender es que la
computadores tienden a ser totalmente implacables con errores “menores” en la
notación. ¿Quién no se ha sentido frustrado al verse obligado a reingresar una larga
línea de texto únicamente porque una coma debía ser unpunto? Podríamos afirmar que
los lenguajes de computadoras (lenguajes de programación, sistemas operativos,
sistemas para bases de datos, etc.) tienen una sintaxis formal totalmente prescripta. La
noción de que un lenguaje creado artificialmente podría ser útil para extender el ámbito

2

de lo que podía ser logrado por el cálculo se retrotrae a Leibniz1. Sin embargo, el primer
ejemploefectivo de un lenguaje formal fue presentado por Gottlob Frege, en su
Begriffsschrift.2
Frege puede ser considerado el fundador del movimiento logicista en la
justificación teórica de la matemática. El logicismo es la tesis según la cual la
matemática y la lógica son literalmente el mismo asunto: todas las entidades que
aparecen en matemática pueden ser tomadas legítimamente como construccionespuramente lógicas y la prueba matemática es simplemente una deducción lógica. De tal
modo, un logicismo minucioso debería estar preparado para brindar una rigurosa
formulación de la lógica deductiva. Frege contó con los descubrimientos previos de
George Boole acerca de la posibilidad de tratar la deducción lógica como una rama de
las matemáticas. Pero, ¿no es esto caer en un círculo vicioso?...