What machines can and cannot do.

Laita, Luis M., Roanes-Lozano, and De Ledesma Otamendi, Luis. "What machines can and cannot do.." RACSAM 101.2 (2007): 133-159. <http://eudml.org/doc/42015>.

@article{Laita2007,
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?},
author = {Laita, Luis M., Roanes-Lozano, De Ledesma Otamendi, Luis},
journal = {RACSAM},
keywords = {Turing machines; theory of computability},
language = {eng},
number = {2},
pages = {133-159},
title = {What machines can and cannot do.},
url = {http://eudml.org/doc/42015},
volume = {101},
year = {2007},
}

TY - JOUR
AU - Laita, Luis M.
AU - Roanes-Lozano
AU - De Ledesma Otamendi, Luis
TI - What machines can and cannot do.
JO - RACSAM
PY - 2007
VL - 101
IS - 2
SP - 133
EP - 159
AB - 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?
LA - eng
KW - Turing machines; theory of computability
UR - http://eudml.org/doc/42015
ER -