# What machines can and cannot do.

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

RACSAM (2007)

- Volume: 101, Issue: 2, page 133-159
- ISSN: 1578-7303

## Access Full Article

top## Abstract

top## How to cite

topLaita, 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 -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.