Computabilidade,funções Computáveis,lógica - Carnielle Unesp

         O livro é um atualizado manual de Lógica, Computabilidade, funções computáveis e
Fundamentos da Matemática, que oferece uma sólida base filosófica para alunos de ensino
superior das três áreas, além de promover uma interação entre a Filosofia e essas
ciências. É objetivo, didático e traz grande quantidade de exercícios.

Sobre os autores

Walter Carnielli é mestre e doutor em Matemática pela Unicamp, com pós-
doutoramento nos Estados Unidos (Berkeley) e na Alemanha (Münster e Bonn) como bolsista 
da Fundação Alexander von Humboldt. Foi diretor do Centro de Lógica, Epistemologia e 
História da Ciência da Unicamp entre 1998 e 2004, e atualmente é pesquisador Nível 1 do 
CNPq e professor titular do Departamento de Filosofia do IFCH-Unicamp. Autor de dezenas 
de artigos de pesquisa em Lógica, Computabilidade, Teoria dos conjuntos e combinatória, 
é também co-autor de Modalità e Multimodalità (Ed. Franco Angeli, 2001, Milão) e 
Computability: Computable Functions, Logic and the Foundations of Mathematics, with the 
Timeline Computability and Undecidability, (Wadsworth/Thomson Learning, 2000, Belmont), 
além de The Semantic Foundations of Logic-Propositional Logics (Kluwer, 1990, Oxford 
University Press, 1995; Wadsworth, 2000); Methods and Applications of Mathematical 
Logic-Proceedings of the VII Latin-American Symposium on Mathematical Logic (American 
Mathematical Society, EUA, 1985); Advances in Contemporary Logic and Computer Science 
(American Mathematical Society, EUA, 1996) e Paraconsistency: the Logical Way to the 
Inconsistent (Marcel Dekker, EUA, 2001). Participa também do comitê editorial de 
diversas revistas científicas internacionais e é membro do Centro de Lógica e 
Computação (CLC) do Instituto Superior Técnico (IST) em Lisboa, Portugal. 

Richard L. Epstein, B.A. summa cum laude, University of Pennsylvania (1969), é Ph.D. em 
Matemática (Lógica) pela University of California, Berkeley (1973) e pós-doutorado em 
Matemática e Filosofia pela Victoria University of Wellington, Nova Zelândia (1975-
1977). Foi professor associado de Matemática na Iowa State University (1978-1982), 
professor de intercâmbio da U. S. National Academy of Sciences para a Polish Academy of 
Sciences, Varsóv

SUMÁRIO:

Prefácio à edição norte-americana
Prefácio à edição brasileira
I - PRINCÍPIOS FUNDAMENTAIS
1 Paradoxos
A. Paradoxos Auto-Referentes
B. Os Paradoxos de Zenão
Exercícios
2 O Significado dos Paradoxos
(Opcional)
A. Filosofia e Matemática
B. O Paradoxo de Aquiles e a Tartaruga Revisto
Exercícios
3 Números Inteiros e Funções
A. Enumeração (Ordinal) vs. Quantidade (Cardinal)
B. Tudo é Número: 
C. Funções
1. Caixas Pretas
2. Domínios e Imagens
3. Funções como regras e funções como conjuntos de pares ordenados
D. Terminologia e Notação
1. A notação ?
2. Funções injetoras e sobrejetoras
3. Composição de funções
Exercícios
4 Provas
A. O que é uma prova?
B. Provas por indução
C. Provas por Contradição (Reductio ad Absurdum)
D. Provas por Construção
E. Provas por Contra-exemplo
F. Provas Existenciais 
G. A Natureza da Prova: Certeza e Existência
(Opcional)
1. De "Provas matemáticas: a origem da dúvida razoável", por Gina Bari Kolata
2. Formalismo Construtivo
Exercícios
5 Coleções Infinitas?
A. Qual o Tamanho do Infinito?
B. Enumerabilidade: Os Racionais São Contáveis
C. Os Reais Não São Enumeráveis
D. Conjunto das Partes e o Conjunto de Todos os Conjuntos
Exercícios
6 Hilbert: Sobre o Infinito
(Opcional)
Exercícios
II - FUNÇÕES COMPUTÁVEIS
7 Computabilidade
A. Algoritmos
B. Critérios Gerais para Algoritmos
C. Enumeração
D. Algoritmo vs. Função Algorítmica
E. Enfoques da Computabilidade Formal
Exercícios
8 Máquinas de Turing
A. As Idéias de Turing sobre Computabilidade
(Opcional)
B. Descrições e Exemplos de Máquinas de Turing
C. Máquinas de Turing e Funções
Exercícios
9 A Tese de Church: um Fato Surpreendente
A. Um fato Surpreendente
B. Emil L. Post sobre a Computabilidade 
(Opcional)
10 Funções Primitivas Recursivas
A. Definição por Indução
B. Definição das Funções Primitivas Recursivas
1. Funções básicas (iniciais)
2. Operações Básicas
3. Uma definição indutiva da classe de funções
C. Exemplos
As constantes
Adição
3. Multiplicação
4. Exponenciação
5. Sinal e teste do zero
6. Metade
7. Predecessor e subtração limitada
Exercícios - Parte 1
D. Outras Operações Primitivas Recursivas
1. Adição e Multiplicação de Funções
2. Funções definidas de acordo com condições
3. Predicados e operações lógicas
4. Minimização limitada
5. Existência e universalidade limitadas
6. Iteração
7. Funções definidas simultaneamente
8. Indução por curso de valores ou indução forte
E. Números Primos como Códigos
F. Enumerando as Funções Primitivas Recursivas
G. Por que Primitivo Recursivo ? Computável
Exercícios - Parte 2
11 A Hierarquia de Grzegorczyk
(Opcional)
A. Hierarquias e Recursão Limitada
B. As Funções Elementares
C. Iterando a iteração: a Função de Ackermann
1. As Funções ?m e provas por indução dupla
2. Dominando as funções primitivas recursivas
3. Função de Ackermann e recursão dupla encadeada
D. A Hierarquia de Grzegorczyk
Exercícios 
12 Recursão Múltipla
(Opcional)
A. As Funções Multiplamente Recursivas
1. Recursão dupla
2. n - recursão
3. Diagonalizando as funções multiplamente recursivas
B. Recursão em Tipos de Ordem 
13 Operador de Busca Mínima
A. O Operador µ 
B. O operador "min"
C. O operador µ Produz uma Função Computável
14 Funções Recursivas Parciais 
A. As Funções Recursivas Parciais
B. Diagonalização e o Problema da Parada 
C. As Funções Recursivas Gerais
D. Gödel a Respeito das Funções Parciais
Exercícios
15 Enumerando as Funções Recursivas Parciais
A. Por quê e Como: A Idéia Inicial 
B. Índices para as Funções Recursivas Parciais
C. Classes Algorítmicas 
(Opcional) 
D. O Predicado de Computação Universal
E. O Teorema da Forma Normal
F. O Teorema s-m-n
G. O Teorema do Ponto Fixo
Exercícios
16 Listabilidade
A. Listabilidade e Conjuntos Recursivamente Enumeráveis
B. Domínios de Funções Recursivas Parciais
C. O Teorema da Projeção
Exercícios 
17 Computável por Máquina de Turing = Recursividade Parcial
(Opcional)