Artigo de pesquisa sobre a teoria das funções recursivas?

8

Você poderia recomendar um artigo de pesquisa ou capítulo de livro que introduz a teoria das funções recursivas? obrigado

reference-request computability Pessoa tímida
fonte

Respostas:

9

Uma boa referência é a "Parte C" do Manual de Lógica Matemática, editado por Barwise. A parte C inclui os seguintes capítulos:

  • Herbert B. Enderton , Elementos da teoria da recursão
  • Martin Davis , problemas insolúveis
  • Michael O. Rabin , Teorias Decidable
  • Stephen G. Simpson , Degress of insolvability: a survey of results
  • Richard A. Shore , teoria da recursão α
  • Alexander Kechris e Yiannis N. Moschovakis , Recursão em tipos superiores
  • Peter Aczel , uma introdução às definições indutivas
  • Donald A. Martin , Teoria descritiva dos conjuntos

Os capítulos são de altíssima qualidade e escritos pelos principais lógicos. Este manual o levará muito longe no mundo da lógica matemática.

Dai Le
fonte
9

A maioria dos livros de teoria da lógica / complexidade tem um capítulo sobre computabilidade.

Livro didático:

Dexter Kozen, " Teoria da Computação ", Springer, 2006

Douglas S. Bridges, " Computabilidade: um caderno de desenho matemático ", Springer, 1994

Nigel Cutland, " Computabilidade, uma Introdução à Teoria da Função Recursiva ", Cambridge University Press, 1980

Barry S. Cooper, " Teoria da Computabilidade ", Chapman & Hall / CRC, 2004

Livro mais avançado:

Robert I. Soare, " Conjuntos e graus recursivamente enumeráveis ", Springer-Verlag, 1987

Robert I. Soare, "Teoria da Computabilidade e Aplicações: A Arte da Computabilidade Clássica"

Piergiorgio Odifreddi, " Teoria Clássica da Recursão ", vol I (1989) e II (1999)

Edward R. Griffor, " Manual da Teoria da Computabilidade ", Elsevier, 1999

Kaveh
fonte
Na lista de livros didáticos, o primeiro "Conjuntos e graus computáveis ​​enumeráveis" possui um título diferente ao que você vinculou ("Conjuntos e graus recursivamente enumeráveis").
MS Dousti
@Sadeq Dousti: Você está certo, acho que copiei o título da página do autor.
Kaveh
Então, editei para refletir o título publicado. PS: O livro "Teoria da Computabilidade e Aplicações: A Arte da Computabilidade Clássica" ainda está para ser publicado, certo?
MS Dousti
@Sadeq: Eu acho que ele prefere evitar usar a palavra recursiva para computável recentemente. ps: Eu acho que sim, mas você provavelmente pode pedir a ele para obter a versão preliminar, nós a usamos em um curso há alguns anos atrás.
Kaveh
6

Gosto do programa que Sebastiaan Terwijn escreveu em 2004 (acessível em http://www.math.ru.nl/~terwijn/teaching.html ). Ele abrange funções e conjuntos recursivos, reconfigurações, hierarquia aritmética, graus de Turing, método prioritário e algumas aplicações, incluindo teoremas da incompletude.

Michaël Cadilhac
fonte
5

Encontrei esses livros à minha disposição. Verifiquei para não incluir os livros citados por Kaveh , mas meus olhos podem ter cometido um erro.

MS Dousti
fonte
@ Kaveh: Obrigado. Parece que eu estou precisando de um par de óculos :)
MS Dousti