Digitalia Inc
Buscador Avanzado
Introducción a la teoría de la computabilidad

Introducción a la teoría de la computabilidad

(2.ª edición)

Esta obra, dirigida fundamentalmente a estudiantes de ingenierías informáticas, presenta los conceptos fundamentales de la teoría de la computabilidad. Abarca los temas de computabilidad, máquinas de Turing, funciones recursivas, computación universal y decibilidad e indecibilidad, junto con un tema de preliminares matemáticos necesarios para la comprensión del texto. En todo momento se utiliza un enfoque práctico relacionando todos estos conceptos con la experiencia de los estudiantes en lenguajes de programación. Se proponen más de cien problemas, de los que se incluye la solución en un apéndice. Desde su aparición, este libro se ha revelado como un manual de extraordinaria utilidad para quien desee iniciarse en los conceptos básicos de la Teoría de la Computabilidad. Resultado de la amplia experiencia docente de sus autores, todos ellos profesores de la Universidad de Alicante, está orientado fundamentalmente a los alumnos de las titulaciones de Informática. Trás el éxito obtenido en su primera edición, presentamos hoy una segunda que ha sido cuidadosamente revisada y puesta al día, y en la que se ha aumentado, de manera significativa, el número de ejercicios de la mayoría de los capítulos.

  • Cover
  • Índice general
  • 1. Preliminares
    • 1.1. Conjuntos
    • 1.2. Tuplas
    • 1.3. Funciones
    • 1.4. Predicados
    • 1.5. Alfabetos, cadenas y lenguajes
    • 1.6. Métodos de demostración
      • 1.6.1. Reducción al absurdo
      • 1.6.2. Demostración por inducción
    • 1.7. Codificación
      • 1.7.1. Codificación de pares de números
    • 1.8. Numerabilidad
    • 1.9. Diagonalización
    • 1.10. Problemas
  • 2. Máquinas de Turing
    • 2.1. Introducción
    • 2.2. El problema de definir un lenguaje
      • 2.2.1. Expresiones regulares
    • 2.3. El modelo conceptual de Máquina de Turing
      • 2.3.1. Funcionamiento de una MT
      • 2.3.2. Representación de una MT
      • 2.3.3. Definición formal de una MT
    • 2.4. Equivalencia de modelos de MT
      • 2.4.1. Máquina de Turing multipista
      • 2.4.2. Máquina de Turing con registro acotado de memoria
      • 2.4.3. Máquina de Turing multicinta
      • 2.4.4. Máquina de Turing no determinista
    • 2.5. Lenguajes computables y funciones
      • 2.5.1. Lenguajes recursivamente enumerables y recursivos
      • 2.5.2. Las MT como computadores de funciones de naturales
    • 2.6. Caracterización de lenguajes con MT generadoras
      • 2.6.1. Caracterización de los lenguajes recursivos
      • 2.6.2. Caracterización de los lenguajes r.e.
    • 2.7. Problemas
  • 3. Funciones L-computables
    • 3.1. Introducción de un lenguaje programación
      • 3.1.1. El lenguaje L
      • 3.1.2. Algunos ejemplos de programas
    • 3.2. Definiciones formales
      • 3.2.1. Notación BNF
      • 3.2.2. Definición de L usando la notación BNF
      • 3.2.3. Semántica de L
    • 3.3. Definición de macros
    • 3.4. Ejemplos de programas
    • 3.5. Funciones L-computables
    • 3.6. Macros genéricas
      • 3.6.1. Asignación
      • 3.6.2. Comparación
    • 3.7. Tesis de Church aplicada al lenguaje L
    • 3.8. Problemas
  • 4. Funciones recursivas primitivas
    • 4.1. Definición de las funciones recursivas primitivas mediante la notación matemática
    • 4.2. Introducción al lenguaje R
    • 4.3. Definición formal de R
      • 4.3.1. Sintaxis del lenguaje R
      • 4.3.2. Semántica del lenguaje R
      • 4.3.3. Funciones recursivas primitivas
    • 4.4. Constructores avanzados
      • 4.4.1. Predicados
      • 4.4.2. Iteradores acotados
      • 4.4.3. Cuantificadores acotados
      • 4.4.4. Minimización acotada
    • 4.5. Una función L-computable total no recursiva primitiva
      • 4.5.1. Minimización no acotada
      • 4.5.2. Funciones recursivas-μ
    • 4.6. Problemas
  • 5. Un programa universal
    • 5.1. Numeración de Gödel
      • 5.1.1. Función de codificación
      • 5.1.2. Función de descodificación
    • 5.2. Codificación de programas L
      • 5.2.1. Codificación de instrucciones
      • 5.2.2. Codificación y descodificación de programas
    • 5.3. Codificación de ejecuciones de programas
      • 5.3.1. Codificación de instantáneas
      • 5.3.2. La función Inst
    • 5.4. El programa universal
      • 5.4.1. El predicado PASOS
      • 5.4.2. El programa universal
    • 5.5. Problemas
  • 6. Decidibilidad e indecidibilidad
    • 6.1. El problema de la parada
    • 6.2. El castor afanoso
    • 6.3. Conjuntos decidibles e indecidibles
      • 6.3.1. Conjuntos recursivos
      • 6.3.2. Conjuntos recursivamente enumerables
      • 6.3.3. Conjuntos recursivos y recursivamente enumerables
      • 6.3.4. Conjuntos recursivamente enumerables y funciones
    • 6.4. Conjuntos no recursivos
      • 6.4.1. El conjunto K
    • 6.5. Conjuntos no recursivamente enumerables
      • 6.5.1. El conjunto K
      • 6.5.2. El conjunto TOT
    • 6.6. Reducción
      • 6.6.1. El conjunto K[sub(0)] no es recursivo
      • 6.6.2. El conjunto NO_VACíO no es recursivo
      • 6.6.3. El conjunto VACíO no es r.e.
      • 6.6.4. El conjunto FINITO no es r.e.
    • 6.7. Teorema de Rice
    • 6.8. Problemas
  • A. Soluciones
    • A.1. Preliminares
    • A.2. Máquinas de Turing
    • A.3. Funciones L–computables
    • A.4. Funciones recursivas primitivas
    • A.5. Un programa universal
    • A.6. Indecidibilidad
  • Índice alfabético
    • A
    • B
    • C
    • D
    • E
    • F
    • G
    • H
    • I
    • K
    • L
    • M
    • N
    • O
    • P
    • R
    • S
    • T
    • V
    • W

Materias

Volver
Ingrese a su cuenta

Visores online

  • Texto
  • ReadSpeaker Audio

Opciones de descarga

  • Adobe DRM Adobe DRM
  • Tiempo préstamo: 21 días
  • Formato: PDF

SUSCRÍBASE A NUESTRO BOLETÍN

Al suscribirse, acepta nuestra Politica de Privacidad

©2010 - 2024 Digitalia - Todos los derechos reservados