PrlogoEl objetivo fundamental de la Teora de la Computabilidad es formalizar yestudiar el concepto de computacin. Esta teora surge en los aos treinta, muchoantes de que se construyeran los primeros computadores elctricos. En esas fechasya exista un tipo de computadores que se utilizaban en laboratorios y universidades,pero no eran mquinas, sino personas que llenaban una sala y que sededicaban a realizar durante das tediosas operaciones y a pasarse los resultadosunos a otros hasta concluir clculos que hoy en da se realizaran en dcimas desegundo1.Para evitar equvocos y malentendidos, querernos dejar claro desde el comienzoque vamos a formalizar en concreto la computacin desde el punto de vista delclculo de funciones matemticas sobre nmeros naturales mediante ejecucin deun algoritmo secuencial. Entendemos un algoritmo (despus lo definiremos conms precisin) como un clculo realizado sobre un conjunto de datos de entraday que produce un dato de salida. Sin embargo, no trataremos el problema de lacomputacin concurrente, en la que diferentes procesos computan funciones enparalelo, se comunican datos, y los resultados finales dependen del momento enel que los procesos se comunican. La formalizacin de este tipo de computacines materia de investigacin en la actualidad.Este texto tiene su origen en las notas y apuntes que hemos elaborado parala asignatura Modelos Abstractos de Clculo, una asignatura cuatrimestral decuatro crditos y medio de segundo curso de las titulaciones de Informtica de laUniversidad de Alicante. En los aos en que la hemos venido impartiendo hemosconfigurado un temario y un estilo de explicar los contenidos que consideramosplenamente adecuado para las titulaciones informticas.El texto est por ello principalmente orientado a alumnos de estas titulaciones,hacindose especial nfasis en relacionar la mayora de conceptos de la Teora dela Computabilidad con la experiencia en lenguajes de programacin que tienenestos alumnos. Sin embargo, no es necesario en absoluto dominar ninguno para1Para dar una idea del enorme salto que se ha dado en poder de computacin presentamosla siguiente ancdota. El problema de calcular los movimientos de tres planetas sometidos aatraccin gravitatioria fue resuelto en 1929, despus de que 56 cientficos calcularan las solucionesa las ecuaciones durante 15 (!) aos. Hoy en da, esos mismos clculos apenas ocuparan unashoras de procesamiento de un potente PC.PrlogoEl objetivo fundamental de la Teora de la Computabilidad es formalizar yestudiar el concepto de computacin. Esta teora surge en los aos treinta, muchoantes de que se construyeran los primeros computadores elctricos. En esas fechasya exista un tipo de computadores que se utilizaban en laboratorios y universidades,pero no eran mquinas, sino personas que llenaban una sala y que sededicaban a realizar durante das tediosas operaciones y a pasarse los resultadosunos a otros hasta concluir clculos que hoy en da se realizaran en dcimas desegundo1.Para evitar equvocos y malentendidos, querernos dejar claro desde el comienzoque vamos a formalizar en concreto la computacin desde el punto de vista delclculo de funciones matemticas sobre nmeros naturales mediante ejecucin deun algoritmo secuencial. Entendemos un algoritmo (despus lo definiremos conms precisin) como un clculo realizado sobre un conjunto de datos de entraday que produce un dato de salida. Sin embargo, no trataremos el problema de lacomputacin concurrente, en la que diferentes procesos computan funciones enparalelo, se comunican datos, y los resultados finales dependen del momento enel que los procesos se comunican. La formalizacin de este tipo de computacines materia de investigacin en la actualidad.Este texto tiene su origen en las notas y apuntes que hemos elaborado parala asignatura Modelos Abstractos de Clculo, una asignatura cuatrimestral decuatro crditos y medio de segundo curso de las titulaciones de Informtica de laUniversidad de Alicante. En los aos en que la hemos venido impartiendo hemosconfigurado un temario y un estilo de explicar los contenidos que consideramosplenamente adecuado para las titulaciones informticas.El texto est por ello principalmente orientado a alumnos de estas titulaciones,hacindose especial nfasis en relacionar la mayora de conceptos de la Teora dela Computabilidad con la experiencia en lenguajes de programacin que tienenestos alumnos. Sin embargo, no es necesario en absoluto dominar ninguno para1Para dar una idea del enorme salto que se ha dado en poder de computacin presentamosla siguiente ancdota. El problema de calcular los movimientos de tres planetas sometidos aatraccin gravitatioria fue resuelto en 1929, despus de que 56 cientficos calcularan las solucionesa las ecuaciones durante 15 (!) aos. Hoy en da, esos mismos clculos apenas ocuparan unashoras de procesamiento de un potente PC.PrlogoEl objetivo fundamental de la Teora de la Computabilidad es formalizar yestudiar el concepto de computacin. Esta teora surge en los aos treinta, muchoantes de que se construyeran los primeros computadores elctricos. En esas fechasya exista un tipo de computadores que se utilizaban en laboratorios y universidades,pero no eran mquinas, sino personas que llenaban una sala y que sededicaban a realizar durante das tediosas operaciones y a pasarse los resultadosunos a otros hasta concluir clculos que hoy en da se realizaran en dcimas desegundo1.Para evitar equvocos y malentendidos, querernos dejar claro desde el comienzoque vamos a formalizar en concreto la computacin desde el punto de vista delclculo de funciones matemticas sobre nmeros naturales mediante ejecucin deun algoritmo secuencial. Entendemos un algoritmo (despus lo definiremos conms precisin) como un clculo realizado sobre un conjunto de datos de entraday que produce un dato de salida. Sin embargo, no trataremos el problema de lacomputacin concurrente, en la que diferentes procesos computan funciones enparalelo, se comunican datos, y los resultados finales dependen del momento enel que los procesos se comunican. La formalizacin de este tipo de computacines materia de investigacin en la actualidad.Este texto tiene su origen en las notas y apuntes que hemos elaborado parala asignatura Modelos Abstractos de Clculo, una asignatura cuatrimestral decuatro crditos y medio de segundo curso de las titulaciones de Informtica de laUniversidad de Alicante. En los aos en que la hemos venido impartiendo hemosconfigurado un temario y un estilo de explicar los contenidos que consideramosplenamente adecuado para las titulaciones informticas.El texto est por ello principalmente orientado a alumnos de estas titulaciones,hacindose especial nfasis en relacionar la mayora de conceptos de la Teora dela Computabilidad con la experiencia en lenguajes de programacin que tienenestos alumnos. Sin embargo, no es necesario en absoluto dominar ninguno para1Para dar una idea del enorme salto que se ha dado en poder de computacin presentamosla siguiente ancdota. El problema de calcular los movimientos de tres planetas sometidos aatraccin gravitatioria fue resuelto en 1929, despus de que 56 cientficos calcularan las solucionesa las ecuaciones durante 15 (!) aos. Hoy en da, esos mismos clculos apenas ocuparan unashoras de procesamiento de un potente PC.