Librop teoria
Páginas: 86 (21331 palabras)
Publicado: 9 de noviembre de 2011
HANS HERMES
INTRODUCCIÓN A LA TEORÍA DE LA COMPUTABILIDAD
ALGORITMOS Y MÁQUINAS
INTRODUCCIÓN A LA TEORÍA DE LA COMPUTABILIDAD
ALGORITMOS Y MÁQUINAS
Los derechos para la versión castellana de la obra Aufzahlbarkeit, Entscheidbarkeit, Berechenbarkeit, publicada originalmente en alemán por Springer-Verlag KG, Berlín Occidental, © SpringerVerlag, Berlin-Heidelberg, 1961 y 1971, sonpropiedad de Editorial Tecnos, S. A. Traducido del alemán por Manuel Garrido y Aránzazu Martín Santos.
N. de los T.: En esta traducción se ha tenido generalmente en cuenta el texto original alemán en su 2.a edición de 1971. Pero en algunos ejemplos y en el diseño de la máquina universal de Turing se ha dado preferencia a la versión inglesa con modificaciones publicadas por el autor en 1969 con eltítulo Enumerability, Decidability, Computability (Springer, Berlín). A esa misma edición aludirá, para mayor comodidad del lector castellano, la sigla EDC.
Diseño de cubierta: J. M. Domínguez y J. Sánchez Cuenca La paginación se corresponde con la edición impresa.
© EDITORIAL TECNOS, S.A., 1984 O'Donnell, 27 - Madrid-9 Depósito legal: M-330-1984 I.S.B.N.: 84-309-1026-3 Printed in Spain. Impresopor GAR. Villablino, 54. Fuenlabrada. (Madrid).
ÍNDICE
PRESENTACIÓN ............................................................... Pág. PREFACIO A LA PRIMERA EDICIÓN....................................... PREFACIO A LA SEGUNDA EDICIÓN ..................................... REFLEXIONES PRELIMINARES SOBREALGORITMOS............................................................................................ § 1. El concepto de algoritmo ................................................. 1. Algoritmos como procedimientos generales ........ 2. Realización de algoritmos ..................................... 3. Gödelización ......................................................... 4. Observaciones sobre la palabra vacía .................... 5. Idealización dealgoritmos..................................... 6. Derivaciones ....................................................... Referencias ..................................................................... § 2. Los conceptos fundamentales de la teoría de la constructividad ...................................................................... 1. 2. 3. 4. 5. § 3 Funciones computables..........................................Conjuntos y relaciones enumerables ..................... Conjuntos y relaciones decidibles ......................... Conjuntos y relaciones generables ........................ La invarianza de los conceptos constructivos bajo la gödelización ............................................... 11 13 17
19 19 19 22 24 25 26 27 32 32 32 35 36 41 45 46 47 49 49 51 53 57 61
El concepto de máquina de Turingcomo sustituto matemático exacto del concepto de algoritmo ............... Observaciones preliminares................................... Algoritmos y máquinas.......................................... El material de computación ................................... Los pasos de computación ..................................... La influencia de la cinta de cálculo sobre un paso decálculo....................................................... 6. La instrucción de cálculo....................................... Referencias ..................................................................... 1. 2. 3. 4. 5.
7
§ 4.
Observaciones históricas................................................. 1. Ars Magna ............................................................. 2. La lógica moderna................................................. 3. Demostraciones de imposibilidad.......................... Referencias ....................................................................
62 62 65 66 69 71 71 71 73 73 75 76 77 78 78
MÁQUINAS DE TURING ............................................................ § 5. Definición de máquinas de Turing......................................
INTRODUCCIÓN A LA TEORÍA DE LA COMPUTABILIDAD
ALGORITMOS Y MÁQUINAS
INTRODUCCIÓN A LA TEORÍA DE LA COMPUTABILIDAD
ALGORITMOS Y MÁQUINAS
Los derechos para la versión castellana de la obra Aufzahlbarkeit, Entscheidbarkeit, Berechenbarkeit, publicada originalmente en alemán por Springer-Verlag KG, Berlín Occidental, © SpringerVerlag, Berlin-Heidelberg, 1961 y 1971, sonpropiedad de Editorial Tecnos, S. A. Traducido del alemán por Manuel Garrido y Aránzazu Martín Santos.
N. de los T.: En esta traducción se ha tenido generalmente en cuenta el texto original alemán en su 2.a edición de 1971. Pero en algunos ejemplos y en el diseño de la máquina universal de Turing se ha dado preferencia a la versión inglesa con modificaciones publicadas por el autor en 1969 con eltítulo Enumerability, Decidability, Computability (Springer, Berlín). A esa misma edición aludirá, para mayor comodidad del lector castellano, la sigla EDC.
Diseño de cubierta: J. M. Domínguez y J. Sánchez Cuenca La paginación se corresponde con la edición impresa.
© EDITORIAL TECNOS, S.A., 1984 O'Donnell, 27 - Madrid-9 Depósito legal: M-330-1984 I.S.B.N.: 84-309-1026-3 Printed in Spain. Impresopor GAR. Villablino, 54. Fuenlabrada. (Madrid).
ÍNDICE
PRESENTACIÓN ............................................................... Pág. PREFACIO A LA PRIMERA EDICIÓN....................................... PREFACIO A LA SEGUNDA EDICIÓN ..................................... REFLEXIONES PRELIMINARES SOBREALGORITMOS............................................................................................ § 1. El concepto de algoritmo ................................................. 1. Algoritmos como procedimientos generales ........ 2. Realización de algoritmos ..................................... 3. Gödelización ......................................................... 4. Observaciones sobre la palabra vacía .................... 5. Idealización dealgoritmos..................................... 6. Derivaciones ....................................................... Referencias ..................................................................... § 2. Los conceptos fundamentales de la teoría de la constructividad ...................................................................... 1. 2. 3. 4. 5. § 3 Funciones computables..........................................Conjuntos y relaciones enumerables ..................... Conjuntos y relaciones decidibles ......................... Conjuntos y relaciones generables ........................ La invarianza de los conceptos constructivos bajo la gödelización ............................................... 11 13 17
19 19 19 22 24 25 26 27 32 32 32 35 36 41 45 46 47 49 49 51 53 57 61
El concepto de máquina de Turingcomo sustituto matemático exacto del concepto de algoritmo ............... Observaciones preliminares................................... Algoritmos y máquinas.......................................... El material de computación ................................... Los pasos de computación ..................................... La influencia de la cinta de cálculo sobre un paso decálculo....................................................... 6. La instrucción de cálculo....................................... Referencias ..................................................................... 1. 2. 3. 4. 5.
7
§ 4.
Observaciones históricas................................................. 1. Ars Magna ............................................................. 2. La lógica moderna................................................. 3. Demostraciones de imposibilidad.......................... Referencias ....................................................................
62 62 65 66 69 71 71 71 73 73 75 76 77 78 78
MÁQUINAS DE TURING ............................................................ § 5. Definición de máquinas de Turing......................................
Leer documento completo
Regístrate para leer el documento completo.