Teoria da Computação
Por: alennm • 15/11/2016 • Relatório de pesquisa • 2.997 Palavras (12 Páginas) • 334 Visualizações
UNIVERISIDADE ANHANGUERA - UNIAN
SANTO ANDRÉ UNIDADE 3
NOMES
ALEXANDRE DA SILVA – RA 1299254935
LUÍS FELIPE TAVARES CRESPO – RA 8638279241
THIAGO DE LIMA SANTOS – RA 9017437324
TEORIA DA COMPUTAÇÃO
SANTO ANDRÉ
2016
UNIVERISIDADE ANHANGUERA - UNIAN
SANTO ANDRÉ UNIDADE 3
TRABALHO TEORIA DA COMPUTAÇÃO
NOMES
ALEXANDRE DA SILVA – RA 1299254935
LUÍS FELIPE TAVARES CRESPO – RA 8638279241
THIAGO DE LIMA SANTOS – RA 9017437324
Calculo lambida e Funções recursivas
Trabalho de complemento da matéria apresentada no 6º semestre
Orientador: Adilson Masiero
SANTO ANDRÉ
2016
RESUMO
O conteúdo que será apresentado nesse trabalho, trata sobre o cálculo lambda e funções recursivas, bem como suas funcionalidades e suas aplicações na computação.
Sumário
1 – INTRODUÇÃO
Lambda cálculo
Termos lambda
Funções que operam em funções
Alfa-equivalência
Variáveis livres
Funções recursivas
Funções recursivas de Kleene (ou funções recursivas parciais)
Definição por indução de funções recursivas
Definição das funções recursivas primitivas
Operações básicas
Função recursiva total
Operações limitadas
Predicado recursivo primitivo
CONCLUSÃO
BIBLIOGRAFIA:
1 – INTRODUÇÃO
A matemática está sempre presente quando falamos de computação, elas estão diretamente ligadas as principais senão todas as funções de sistemas computáveis, dentre as inúmeras funções matemáticas utilizadas em sistemas computacionais, estão o cálculo lambda e as funções recursivas.
O cálculo lambda é um sistema formal que estuda funções recursivas computáveis, no que se refere a teoria da computabilidade, e fenômenos relacionados, como variáveis ligadas e substituição. Sua principal característica são as entidades que podem ser utilizadas como argumentos e retornadas como valores de outras funções.
Em lógica matemática e ciência computacional, as funções recursivas são uma classe de funções parciais de números naturais para números naturais que são “computáveis” num sentido intuitivo. De fato, na teoria da computação é mostrado que as funções recursivas são precisamente as que podem ser computadas por máquinas de Turing. As funções recursivas são intimamente relacionadas às funções recursivas primitivas, e sua definição indutiva se baseia nestas funções recursivas primitivas. No entanto, nem toda função recursiva é uma função primitiva recursiva – o mais famoso exemplo é a função de Ackermann.
Lambda cálculo
O lambda cálculo consiste de uma linguagem de termos lambda junto com uma teoria equacional (que pode também ser entendida operacionalmente).
Como os nomes de funções são uma mera conveniência, o lambda cálculo não tem interesse em nomear uma função. Já que todas as funções esperando mais de um argumento podem ser transformadas em funções equivalentes recebendo uma única entrada, o lambda cálculo não tem interesse em criar funções que aceitam mais de um argumento. E como os nomes dos argumentos são irrelevantes, a noção nativa de igualdade entre termos lambda se chama equivalência-alpha e que demonstra este princípio.
Na lógica matemática e na ciência da computação, lambda cálculo, também escrito como cálculo-λ é um sistema formal que estuda funções recursivas computáveis, no que se refere a teoria da computabilidade, e fenômenos relacionados, como variáveis ligadas e substituição. Sua principal característica são as entidades que podem ser utilizadas como argumentos e retornadas como valores de outras funções.
A parte relevante de lambda cálculo para computação ficou conhecida como lambda cálculo não-tipado. O lambda cálculo tipado e o não-tipado tem suas ideias aplicadas nos campos da lógica, teoria da recursão (computabilidade) e linguística, e tem tido um grande papel no desenvolvimento da teoria de linguagens de programação (com a versão não-tipada sendo a inspiração original para programação funcional, em particular LISP, e a versão tipada contribuindo para fundamentar modernos sistemas de tipos e linguagens de programação)
O cálculo lambda é uma coleção de diversos sistemas formais baseados em uma notação para funções inventada por Alonzo Chochem 1936 com o intuito de capturar os aspectos mais básicos da maneira pela qual operadores ou funções podem ser combinados para formar outros operadores.
O cálculo lambda serve como uma ponte entre linguagens funcionais de alto nível e suas implementáveis de baixo nível. Raízes para a apresentação do cálculo lambda como uma linguagem intermediária: uma linguagem extremamente simples, consistindo de somente algumas poucas construções sintáticas e de uma semântica simples.
...