A presente página foi criada para organizar o conteúdo da apresentação feita para a disciplina de Teoria da Computação da UDESC. O grupo é formado pelos alunos: Diogo Bortolini, Felipe Gallois, Luiz Fernando de Freitas e Rodrigo Luís dos Santos. O trabalho foi apresentado ao professor Adolfo Neto no primeiro semestre de 2008. Os seguintes temas são abordados.
As Máquinas de Post são construções teóricas, tais como as Máquinas de Turing que permitem simular um modelo computacional. Apesar de essencialmente equivalentes, Post estava mais preocupado em mostrar a solucionabilidade dos problemas do que sua computabilidade, como era o caso de Turing.
O artigo original de Post era entitulado "Formulation 1", sendo o termo Máquina de Post inventado um tempo depois, principalmente pela popularidade da Máquina de Turing.
Abaixo alguns materiais que foram usados como referência.
O artigo original Formulation 1 de Emil Post. (em inglês, pdf)
Uspensky publicou um livro em 1983, entitulado Post's Machine, que propunha ensinar a Máquina de Post no ensino médio e fundamental. É, possivelmente, a referência mais extensa sobre o assunto. Ao final também apresenta o artigo original de Post. (em inglês, djvu)
Artigo do grupo COCA(Computação Cognitiva Aplicada) da UDESC(Universidade do Estado de Santa Catarina), fala sobre Máquinas de Post e Markov. (em português, pdf), (tantos parênteses quanto LISP ;))
Artigo sobre Máquinas de Post de Liesbeth De Mol, do Centro de Lógica e Filosofia da Ciência de Blandijnberg, Bélgica. (em inglês, pdf)
Finalmente, a nossa apresentação. (em português, pdf)
Para quem quiser, o fonte da apresentação. (LaTeX)
As funções Recursivas foram originalmente apresentadas por Kleene que era um matemático americano que tinha PhD na Universidade de Princeton, e foi um dos alunos de Church, que tinha por objetivo a busca de um "procedimento mecânico" que justificasse as transformações funcionais dos números. No qual, um problema pode ser resolvido usando o computador se e somente se puder ser traduzido na forma de uma função de números naturais pertencentes a esta classe de funções.
As funções recursivas foram criadas a partir de elementos primitivos de recursão. Estas podem ser obtidas através de minimização de uma representação funcional de uma busca sequencial. As funções recursivas mostra-se como um método efetivo para encontrar valores de uma função
Aula apresentada pelo professor Adolfo no dia 18/06/2008. (em poruguês, pdf)
Apresentação de slides sobre teoria da computação, inclui funções recursivas. (em português, pdf)
Apresentação sobre abordagens da computabilidade. (em português, pdf)
Apresentação sobre funções recursivas dos alunos: Marco Seruffo, Rômulo Magalhães, Amanda Sizo, Inácio Gorayeb e Mariana Lima. (em português, ppt)
Artigo do grupo COCA(Computação Cognitiva Aplicada) da UDESC(Universidade do Estado de Santa Catarina), fala sobre funções recursivas. (em português, pdf), (tantos parênteses quanto LISP ;))
Nossa apresentação sobre funções recursivas. (em português, odp)
Um resumão sobre funções recursivas, preparado pelo nosso grupo. (em português, odt)
Abaixo, uma sequência de links de referência
wikipedia