What machines can and cannot do.

Laita, Luis M. ; Roanes-Lozano ; De Ledesma Otamendi, Luis

RACSAM, Tome 101 (2007), p. 133-159 / Harvested from Biblioteca Digital de Matemáticas

Abstract

In this paper, the questions of what machines cannot do and what they can do will be treated by examining the ideas and results of eminent mathematicians. Regarding the question of what machines cannot do, we will rely on the results obtained by the mathematicians Alan Turing and Kurt G¨odel. Turing machines, their purpose of defining an exact definition of computation and the relevance of Church-Turing thesis in the theory of computability will be treated in detail. The undecidability of the “Entscheidungsproblem” (German for “decision problem”) is shown to be a consequence of the computations that Turing machines can or cannot do. Beginning with Peano’s arithmetic, a variant of it, “theory S”, is presented and discussed. By studying representability and expressibility in S, the notion of recursive functions will be reached. G¨odel arithmetization of logic and of first order theories and his completeness and incompleteness theorems, together with Church’s incompleteness theorem, provide both the important possibility of codifying mathematics and the reasons for existence of other undecidable problems Regarding the question of what machines can do, we mainly rely on the ideas of the Nobel Laureate Herbert A. Simon. Nevertheless, a few facts about modern computing machines and about the so called “expert systems” will be described, because they suggest the existence of important capabilities of machines. The paper ends with a few considerations about the question: who is more intelligent, the man or the machine?

Résumé

En el presente artículo, la cuestión de lo que las máquinas pueden y no pueden hacer será considerada basando la argumentación en ideas y resultados de eminentes matemáticos e informáticos. En la cuestión ¿qué no pueden hacer las máquinas?, nos basamos en resultados obtenidos por Alan Turing y Kurt Gödel. Las máquinas de Turing, su propósito de mostrar una definición exacta de lo que significa “computación” y/o “algoritmo”, conjuntamente con la importancia que tuvo y sigue teniendo en la teoría de la computabilidad la tesis de Church-Turing, serán tratadas detalladamente. Se muestra que la indecidibilidad del problema de la decisión (“Entscheidungsproblem”) es una de las consecuencias de lo que las máquinas de Turing pueden o, mejor, no pueden hacer. Se presenta y discute una variante de la aritmética de Peano, denominada “Teoría S”, de forma que definiendo en S las nociones de “representabilidad” y “expresabilidad”, llegaremos a la noción de “función recursiva”. La aritmetización de Gödel de la lógica y de las teorías de primer orden, y sus dos teoremas de incompletud, conjuntamente con el teorema de incompletud de Church, hacen posible, por un lado, la codificación en matemáticas, y, por otro, mostrar la existencia de problemas indecidibles adicionales. Con respecto a la cuestión de ¿qué pueden hacer las máquinas? nos basamos fundamentalmente en las ideas sobre inteligencia artificial del Premio Nobel Herbert A. Simon. Sin embargo, debido a que revelan importantes capacidades de las máquinas, describiremos algunos hechos acerca de algunas máquinas computadoras actuales, y otros hechos acerca de los denominados “sistemas expertos”. El artículo termina con algunas consideraciones acerca de la pregunta: ¿quién es más inteligente, el hombre o la máquina?.

Détail

Publié le : 2007-01-01

Zbl 1146.68368

DMLE-ID : 4483