Hilbert, Turing y la noción de procedimiento efectivo

Francisco Hernández-Quiroz, Raymundo Morado

Resumen


Hilbert, Turing and the idea of effective procedure.

Hilbert put forward the properties that an effective procedure should possess, without a formal characterization. Nevertheless, he formulated four desiderata: (1) a calculus is a set of instructions to be executed to solve a problem; 2) it must boil down to rules for the manipulation of formulae of a suitable formal language; 3) it must guarantee the solution of the problem in a finite number of steps; 4) it should be possible to set in advance an upper bound to the number of steps it will take to find the solution. Turing proposed his famous machines to define rigorously the meaning of effective procedure and, paradoxically, showed there is no mathematical characterization of it that satisfies Hilbert’s expectations. In particular, Turing’s model goes beyond desiderata third and fourth.

 

Key words: Effective Procedure, Entscheidungsproblem, Halting Problem, Turing machines.


Texto completo:

PDF

Referencias


Börger, E., E. Grädel, Y. Gurevich (2001), The Classical Decision Problem, Berlín, Springer, Universitext,.

Church, A. (1936),“An unsolvable problem of elementary number theory,” The American Journal of Mathematics 58: 345–363.

Davis, M. (1994), “Mathematical logic and the origin of modern computing”, Herken, R. (ed.) The Universal Turing Machine—A Half-Century Survey, Viena, Springer, pp. 135–158.

Gandy, R. (1994), “The confluence of ideas in 1936,” Herken, R. (ed.), The Universal Turing Machine—A Half-Century Survey, Viena, Springer, pp. 51-102.

Hernández-Quiroz, F., R. Morado (2005), “Some assumptions about problem solving method in Turing’s model of intelligence”, Hamza, M. H. (ed.), Computational Intelligence (CI 2005), Calgary, Acta Press, pp. 354-358.

Hernández-Quiroz, F., R. Morado (2006), “Presupuestos del modelo clásico de la inteligencia mecánica”, Actas del XIII Congreso de Filosofía de la Asociación Filosófica de México.

Hilbert, D., W. Ackermann (1928), Grundzüge der Theoretischen Logik. Traducción inglesa como Principles of Mathematical Logic, Nueva York, Chelsea Publishing Company, 1950.

Hilbert, D. (1918), “Axiomatisches Denken”, Mathematische Annalen, 78: 405-415. Traducido como “El pensamiento axiomático”, Hilbert, D., Fundamentos de las Matemáticas, 1993, pp. 23-35, México, UNAM, Mathema. Citamos de esta última edición.

Hilbert, D. (1922), “Neubegründung der Mathematik: Erste Mitteilung", Abhandlungen aus dem Seminar der Hamburgischen Universität, 1: 157-77. Traducido como “Nueva fundamentación de las matemáticas”, Hilbert, D., Fundamentos de las Matemáticas, 1993, 37-62, México, UNAM, Mathema. Citamos de esta última edición.

Hilbert, D., P. Bernays (1934), Grundlagen der Mathematik, Berlin, Springer.

Morado, R., F. Hernández-Quiroz (2006), “Some assumptions about problem solving representation in Turing’s model of intelligence”. Aceptado para publicación en TripleC: Cognition, Computation, Co-operation.

Rice, H. G. (1953), “Classes of recursively enumerable sets and their decision problems,” Transactions of the American Mathematical Society 74: 358-366.

Turing, A. M. (1936–7), “On computable numbers, with an application to the Entscheidungsproblem”, Proceedings of the London Mathematical Society 42: 230–265.


Enlaces refback

  • No hay ningún enlace refback.


Revista semestral editada por el Centro de Estudios Filosóficos, Políticos
y Sociales Vicente Lombardo Toledano de la Secretaría de Educación Pública,
la Universidad Autónoma Metropolitana-Iztapalapa y Edicions UIB de la Universitat de les Illes Balears.

Lombardo Toledano 51, Col. Ex-Hda. Guadalupe Chimalistac,
Del. Alvaro Obregón, C.P. 01050, México, D.F.
Tels. (5255) 5661-4679 y 5661-4987
Fax: (5255) 5661-1787