Lambda-Cálculo e Lógica Combinatória

2018.2

Ementa e Programa

Instrutores: Ruy de Queiroz e Anjolina de Oliveira

Horário e Sala de Aula
2^a 10-12h, Sala E-122
4^a 08-10h, Sala E-122

Forum: lambda-l @ cin.ufpe.br

Ementa: O lambda-cálculo. Estrutura de termos e substituição. Redução. Lógica Combinatória. Redução fraca. O Poder Expressivo de Lambda e dos Combinadores. O teorema do ponto-fixo. Representando as funções recursivas. O teorema da indecidibilidade. Lambda-cálculo com tipos. Isomorfismo de Curry-Howard.

Livro-Texto:

Lambda-Calculus and Combinators: An Introduction, J. Roger Hindley & Jonathan P. Seldin, Cambridge University Press, 2nd edition (August 11, 2008), ISBN-10: 0521898854. (Primeira edição: Introduction to Combinators and Lambda-Calculus, London Mathematical Society Student Texts 1, CUP, 1986.)

Outros recursos bibliográficos:

1. Lambda Calculi with Types, Henk Barendregt

2. Lambda-Calculus, Types and Models, by J.L. Krivine, Masson, Paris, 1993 (English xlation) ISBN 0-13-062407-1.

3. Introduction to Lambda Calculus, Henk Barendregt and Erik Barendsen

4. An introduction to lambda calculi and arithmetic, Harold Simmons.

5. http://www.safalra.com/science/lambdacalculus/index.html

6. On-line books, aulaure notes, etc (Lambda Calculus)

7. Alonzo Church Papers

8. Church, Alonzo, The calculi of lambda-conversion. Imprint: Princeton, Princeton University Press, 1941 [i.e. 1963]. (Series: Annals of mathematical studies, no. 6)

Leitura adicional:

1. `Funktion und Begriff', Vortrag, gehalten in der Sitzung vom 9. Januar 1891 der Jenaischen Gesellschaft für Medizin und Naturwissenschaft, Jena: Hermann Pohle. Translated as `Function and Concept' by P. Geach in Translations from the Philosophical Writings of Gottlob Frege, P. Geach and M. Black (eds. and trans.), Oxford: Blackwell, third edition, 1980.

2. Grundgesetze der Arithmetik, Jena: Verlag Hermann Pohle, Band I, 1893. Partial translation as The Basic Laws of Arithmetic by M. Furth, Berkeley: U. of California Press, 1964. Full translation as Gottlob Frege: Basic Laws of Arithmetic, 1st Edition, translated by Philip A. Ebert & Marcus Rossberg. Oxford University Press. December 2013. 680 pages. ISBN-13: 978-0199281749.