¿Artículo de encuesta sobre la teoría de las funciones recursivas?

8

¿Podría recomendar un artículo de encuesta o un capítulo de libro de texto que presente la teoría de las funciones recursivas? Gracias

reference-request computability Persona tímida
fuente

Respuestas:

9

Una buena referencia es la "Parte C" del Manual de lógica matemática editado por Barwise. La Parte C incluye los siguientes capítulos:

  • Herbert B. Enderton , Elementos de la teoría de la recursividad.
  • Martin Davis , problemas irresolubles
  • Michael O. Rabin , teorías decidibles
  • Stephen G. Simpson , Degress of insolvability: una encuesta de resultados
  • Richard A. Shore , teoría de la recursión α
  • Alexander Kechris y Yiannis N. Moschovakis , Recursión en tipos superiores
  • Peter Aczel , una introducción a las definiciones inductivas
  • Donald A. Martin , teoría descriptiva de conjuntos

Los capítulos son de muy alta calidad y están escritos por los principales lógicos. Este manual lo llevará bastante lejos en el mundo de la lógica matemática.

Dai Le
fuente
9

La mayoría de los libros de teoría de lógica / complejidad tienen un capítulo sobre computabilidad.

Libro de texto:

Dexter Kozen, " Teoría de la computación ", Springer, 2006

Douglas S. Bridges, " Computabilidad: un cuaderno de dibujo matemático ", Springer, 1994

Nigel Cutland, " Computabilidad, una introducción a la teoría de la función recursiva ", Cambridge University Press, 1980

Barry S. Cooper, " Teoría de la computabilidad ", Chapman & Hall / CRC, 2004

Libro más avanzado:

Robert I. Soare, " Conjuntos y grados recursivamente enumerables ", Springer-Verlag, 1987

Robert I. Soare, "Teoría y aplicaciones de la computabilidad: el arte de la computabilidad clásica"

Piergiorgio Odifreddi, " Teoría de la recursión clásica ", vol. I (1989) y II (1999)

Edward R. Griffor, " Manual de teoría de la computabilidad ", Elsevier, 1999

Kaveh
fuente
En la lista de libros de texto, el primero "Conjuntos y grados computablemente enumerables" tiene un título diferente al que vinculó ("Conjuntos y grados recursivamente enumerables").
MS Dousti
@Sadeq Dousti: Tienes razón, creo que he copiado el título de la página web del autor.
Kaveh
Entonces, lo edité para reflejar el título tal como se publicó. PD: El libro "Teoría y aplicaciones de la computabilidad: el arte de la computabilidad clásica" aún no se ha publicado, ¿verdad?
MS Dousti
@Sadeq: Creo que prefiere evitar usar la palabra recursiva para computable recientemente. PD: Creo que sí, pero probablemente puedas pedirle que obtenga la versión borrador, la hemos usado en un curso hace unos años.
Kaveh
6

Me gusta el programa que escribió Sebastiaan Terwijn en 2004 (accesible en http://www.math.ru.nl/~terwijn/teaching.html ). Cubre funciones y conjuntos recursivos, re conjuntos, la jerarquía aritmética, grados de Turing, el método de prioridad y algunas aplicaciones, incluidos los teoremas de incompletitud.

Michaël Cadilhac
fuente
5

Encontré estos libros a mi disposición. Hice una verificación cruzada para no incluir los libros citados por Kaveh , pero mis ojos podrían haber cometido un error.

MS Dousti
fuente
@Kaveh: Gracias. Parece que necesito un par de anteojos :)
MS Dousti