Assunto um pouco[ OFF TOPIC] referente a IC na área de Teoria da Recursão

[Ana Paula Dos Anjos Vitorasse]

 

 

Para quem tem interesse em começar uma IC na área de Teoria da Recursão quais os conceitos que tenho bem definidos na cabeça para entender bem a referida Teoria??

                Por enquanto meu professor me recomendou ler o Capítulo 10 do livro do Prof. Walter Carnielli e Richard L. Epstein. Mas estou sem nenhuma base por onde começar. O professor que procurei para trabalhar numa Iniciação Científica disse que preciso especificar o que pretendo estudar. Para um iniciante o que seria mais adequado? Função recursiva Primitiva ou Função Computável?

 

Desde já agradeço.

 

Enviado do Email para Windows 10

 

[Rodrigo Freire]

Olá Ana,

Com mais informações sobre seu background e sobre como você se interessou por esse campo é mais fácil receber uma sugestão apropriada. Sobre sua primeira questão: É importante entrar em contato, inicialmente, com as noções de função, enumeração e indução finita. Além desse livro que seu professor indicou, você pode pegar o livro Computabilidade e Lógica, de Boolos, Burgess e Jeffrey, também traduzido para o português e publicado pela editora Unesp. 

Se me fosse pedido para elaborar um projeto de IC, eu faria um projeto articulado em torno da chamada tese de Church, portanto dando prioridade para a noção de função computável, respondendo sua outra pergunta. Claro que é uma resposta enviesada, não há resposta certa para isso, é perfeitamente cabível um outro projeto que inverte essa prioridade. 

Abraço 

Rodrigo

--
Você recebeu essa mensagem porque está inscrito no grupo "LOGICA-L" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para logica-l+u...@dimap.ufrn.br.
Para postar nesse grupo, envie um e-mail para logi...@dimap.ufrn.br.
Acesse esse grupo em https://groups.google.com/a/dimap.ufrn.br/group/logica-l/.
Para ver essa discussão na Web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/BN6PR03MB3138403D71A99F010063E61FD4BC0%40BN6PR03MB3138.namprd03.prod.outlook.com.

[Antonio Marmo]

Além dessas indicações do Rodrigo, você pode também dar uma olhada na parte histórica que é a melhor forma de penetrar as questões.

Veja, entre outros, o legado de Raimundo Lúlio e Leibniz para depois ir a Church e Turing.

Para ver essa discussão na Web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/BECF5B32-4AEA-4EA3-9F77-89E2D7BC8AA9%40gmail.com.

[Francisco Miraglia]

Car@s,

Os clássicos são, em geral, meus preferidos: Hartley Rogers. Da trabalho, mas não há tempo perdido com o trabalho necessário. 

Abraços ,

Chico Miraglia 

Para ver essa discussão na Web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/59E9D60F-7871-4937-9604-F132545F3019%40gmail.com.

[Thanos Tsouanas]

[mando novamente minha mensagem pois acho que mandei por o email errado]

Oi Ana,

Nao tenho certeza qual o nivel dum "IC" (nem sei exatamente o que eh),
nem qual eh o teu background matematico, entao pode ser que nada desse
email faz sentido para teu caso, mas um comeco razoavel para teoria de
recursao seria:

* Cutland (Computability) eh mto gentil e nao presuponha muita coisa
para estuda-lo.
* "a biblia geral": Kleene (Introduction to Metamathematics) tem uma
parte devotada em teoria de recursao, e os prerequisitos para ela
tambem pode achar no mesmo livro, nos capitulos anteriores.

Dois livros focados nisso sao:
* "a biblia focada": Rogers (Theory of Recursive Functions and
Effective Computability)
* o mais recente Soare (Recursively Enumerable Sets and Degrees)

Esse assunto eh um dos "4 pillars" da logica (teoria de conjuntos /
teoria de modelos / teoria de provas / teoria de recursao), entao ele
eh bastante tratado em livros de matematica logica geral.
Dois bons livros com bastante material em teoria de recursao sao os
* Bell & Machover (A course on Mathematical Logic)
* Cory & Lascar (Mathematical Logic: a course with exercises)

* As lecture notes de Moschovakis sao muito boas e bem no coracao do
assunto, com muitos exercicios para praticar, mas pressuponham
bastante "maduridade matematica" para acompanhar e progressam
rapidamente:
http://www.math.ucla.edu/~ynm/lectures/randc.pdf

Tudo isso supondo que estas procurando um tratamento matematico mesmo..
No lado de programacao um livro interessante seria o
* Jones (computability & complexity a programming perspective)
mas apenas pelo fato que tu chamou "Teoria de Recursao" imagino que o
outro lado eh o que voce mais quer.

Abraco

--Thanos

> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CEBFAB71-7F63-4545-9EDB-EF989801F08D%40ime.usp.br.

[Ana Paula Dos Anjos Vitorasse]

Obrigada a todos pelas dicas. 

E vou dar uma olhada na tese de Church e e estudar sobre função computável. 

> um e-mail para logica-l+unsubscribe@dimap.ufrn.br.

> Para postar nesse grupo, envie um e-mail para logi...@dimap.ufrn.br.
> Acesse esse grupo em
> https://groups.google.com/a/dimap.ufrn.br/group/logica-l/.
> Para ver essa discussão na Web, acesse
> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/BN6PR03MB3138403D71A99F010063E61FD4BC0%40BN6PR03MB3138.namprd03.prod.outlook.com.
>
> --
> Você recebeu essa mensagem porque está inscrito no grupo "LOGICA-L" dos
> Grupos do Google.
> Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie

> um e-mail para logica-l+unsubscribe@dimap.ufrn.br.

> Para postar nesse grupo, envie um e-mail para logi...@dimap.ufrn.br.
> Acesse esse grupo em
> https://groups.google.com/a/dimap.ufrn.br/group/logica-l/.
> Para ver essa discussão na Web, acesse
> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/BECF5B32-4AEA-4EA3-9F77-89E2D7BC8AA9%40gmail.com.
>
> --
> Você recebeu essa mensagem porque está inscrito no grupo "LOGICA-L" dos
> Grupos do Google.
> Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie

> um e-mail para logica-l+unsubscribe@dimap.ufrn.br.

> Para postar nesse grupo, envie um e-mail para logi...@dimap.ufrn.br.
> Acesse esse grupo em
> https://groups.google.com/a/dimap.ufrn.br/group/logica-l/.
> Para ver essa discussão na Web, acesse
> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/59E9D60F-7871-4937-9604-F132545F3019%40gmail.com.
>
> --
> Você recebeu essa mensagem porque está inscrito no grupo "LOGICA-L" dos
> Grupos do Google.
> Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie

> um e-mail para logica-l+unsubscribe@dimap.ufrn.br.

> Para postar nesse grupo, envie um e-mail para logi...@dimap.ufrn.br.
> Acesse esse grupo em
> https://groups.google.com/a/dimap.ufrn.br/group/logica-l/.
> Para ver essa discussão na Web, acesse
> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CEBFAB71-7F63-4545-9EDB-EF989801F08D%40ime.usp.br.

--
Você está recebendo esta mensagem porque se inscreveu no grupo "LOGICA-L" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para logica-l+unsubscribe@dimap.ufrn.br.
Para postar neste grupo, envie um e-mail para logi...@dimap.ufrn.br.
Visite este grupo em https://groups.google.com/a/dimap.ufrn.br/group/logica-l/.
Para ver esta discussão na web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CALVp4Y6AidryJRMW%2Bskpq0MqKr4jAYqRZGdCC9pj1uWEP2wn%3DQ%40mail.gmail.com.

[Eduardo Ochs]

Ana, nao deixa de dar uma olhada nesse artigo aqui sobre a Tese de Church...

Dershowitz/Gurevich: "A Natural Axiomatization of Computability and Proof of Church's Thesis"

https://www.jstor.org/stable/i20059984

  [[]], Eduardo

    =)

> um e-mail para logica-l+u...@dimap.ufrn.br.

> Para postar nesse grupo, envie um e-mail para logi...@dimap.ufrn.br.
> Acesse esse grupo em
> https://groups.google.com/a/dimap.ufrn.br/group/logica-l/.
> Para ver essa discussão na Web, acesse
> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/BN6PR03MB3138403D71A99F010063E61FD4BC0%40BN6PR03MB3138.namprd03.prod.outlook.com.
>
> --
> Você recebeu essa mensagem porque está inscrito no grupo "LOGICA-L" dos
> Grupos do Google.
> Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie

> um e-mail para logica-l+u...@dimap.ufrn.br.

> Para postar nesse grupo, envie um e-mail para logi...@dimap.ufrn.br.
> Acesse esse grupo em
> https://groups.google.com/a/dimap.ufrn.br/group/logica-l/.
> Para ver essa discussão na Web, acesse
> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/BECF5B32-4AEA-4EA3-9F77-89E2D7BC8AA9%40gmail.com.
>
> --
> Você recebeu essa mensagem porque está inscrito no grupo "LOGICA-L" dos
> Grupos do Google.
> Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie

> um e-mail para logica-l+u...@dimap.ufrn.br.

> Para postar nesse grupo, envie um e-mail para logi...@dimap.ufrn.br.
> Acesse esse grupo em
> https://groups.google.com/a/dimap.ufrn.br/group/logica-l/.
> Para ver essa discussão na Web, acesse
> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/59E9D60F-7871-4937-9604-F132545F3019%40gmail.com.
>
> --
> Você recebeu essa mensagem porque está inscrito no grupo "LOGICA-L" dos
> Grupos do Google.
> Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie

> um e-mail para logica-l+u...@dimap.ufrn.br.

> Para postar nesse grupo, envie um e-mail para logi...@dimap.ufrn.br.
> Acesse esse grupo em
> https://groups.google.com/a/dimap.ufrn.br/group/logica-l/.
> Para ver essa discussão na Web, acesse
> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CEBFAB71-7F63-4545-9EDB-EF989801F08D%40ime.usp.br.

--
Você está recebendo esta mensagem porque se inscreveu no grupo "LOGICA-L" dos Grupos do Google.

Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para logica-l+u...@dimap.ufrn.br.

Para postar neste grupo, envie um e-mail para logi...@dimap.ufrn.br.
Visite este grupo em https://groups.google.com/a/dimap.ufrn.br/group/logica-l/.
Para ver esta discussão na web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CALVp4Y6AidryJRMW%2Bskpq0MqKr4jAYqRZGdCC9pj1uWEP2wn%3DQ%40mail.gmail.com.

--

Você recebeu essa mensagem porque está inscrito no grupo "LOGICA-L" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para logica-l+unsubscribe@dimap.ufrn.br.
Para postar nesse grupo, envie um e-mail para logi...@dimap.ufrn.br.
Acesse esse grupo em https://groups.google.com/a/dimap.ufrn.br/group/logica-l/.

Para ver essa discussão na Web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAJupc5FQUEJMZrz-BZNK%2BjPTYOFdHe8fh6XkOSfiSAfmu4tPFg%40mail.gmail.com.

[Ana Paula Dos Anjos Vitorasse]

Obrigada Eduardo, estava a procura disso o outro dia. Me será bem útil. 

Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para logica-l+u...@dimap.ufrn.br.

Para postar nesse grupo, envie um e-mail para logi...@dimap.ufrn.br.
Acesse esse grupo em https://groups.google.com/a/dimap.ufrn.br/group/logica-l/.

Para ver essa discussão na Web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAJupc5FQUEJMZrz-BZNK%2BjPTYOFdHe8fh6XkOSfiSAfmu4tPFg%40mail.gmail.com.

--
Você recebeu essa mensagem porque está inscrito no grupo "LOGICA-L" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para logica-l+u...@dimap.ufrn.br.
Para postar nesse grupo, envie um e-mail para logi...@dimap.ufrn.br.
Acesse esse grupo em https://groups.google.com/a/dimap.ufrn.br/group/logica-l/.

Para ver essa discussão na Web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CADs%2B%2B6i7VmuV9jJa-DhRWr2_aeig%2BuxnrwAKE4HJX2pjO2uAWw%40mail.gmail.com.