Teoria da computação

Sumário

Nota da edição

Prefácio 

Apresentação

1 Programas, máquinas e equivalências 

1.1 Programas 

1.2 Máquinas

1.3 Programa para uma máquina

1.4 Computação

1.5 Função computada

1.6 Equivalência forte de programas

1.7 Equivalência de programas em uma máquina 

1.8 Equivalência de máquinas

1.9 Verificação da equivalência forte de programas

1.10 Poder computacional

1.11 Exercícios

2 Máquinas universais 

2.1 Algoritmos

2.2 Máquinas universais 

2.3 Hipótese de Church-Turing 

2.4 Teorema Fundamental da Aritmética

2.5 Codificação de dados estruturados 

2.6 Máquina de Turing 

2.7 Máquina Norma

2.8 Máquina Norma é universal por evidências internas

2.9 Máquina Norma é universal por evidências externas

2.10 Máquina de Post 

2.11 Máquina de Post é universal por evidências externas

2.12 Máquina com Pilhas

2.13 Autômato com Duas Pilhas

2.14 Autômato com Duas Pilhas é universal por evidências externas

2.15 Variações da Máquina de Turing

2.16 Exercícios

3 Decidibilidade 

3.1 Introdução 

3.2 Problemas decidíveis 

3.3 Codificação de Máquinas de Turing

3.4 Método diagonal de Cantor

3.5 Linguagem Ld

3.6 Complemento de linguagens

3.7 Máquina de Turing Universal 

3.8 Linguagem Lu

3.9 Redutibilidade 

3.10 Problema da parada

3.11 Linguagens Le e Lne

3.12 Teorema de Rice

3.13 Autômato Linearmente Limitado

3.14 Histórias de computação

3.15 Problemas indecidíveis 

3.16 Problema da Correspondência de Post

3.17 Problemas relacionados com gramáticas e linguagens livres de contexto

3.18 Conclusões

3.19 Exercícios

4 Complexidade no tempo 

4.1 Motivação

4.2 Complexidade de tempo

4.3 A classe P

4.4 A classe NP

4.5 Verificadores 

4.6 Problemas CLIQUE e SOMASUBC

4.7 P × NP 

4.8 Redutibilidade em tempo polinomial

4.9 Problemas SAT e 3SAT 

4.10 Redução de 3SAT para CLIQUE 

4.11 Problemas NP-completos 

4.12 Problemas NP-difíceis

4.13 A classe NPC

4.14 A classe NPH

4.15 Conclusões 

4.16 Exercícios

5 Cálculo Lambda não tipado 

5.1 Introdução

5.2 Motivação

5.3 Linguagem lambda

5.4 Substituições 

5.5 Conversão-α 

5.6 Redução-β 

5.7 Formal normal-β 

5.8 Numerais de Church

5.9 Booleanos de Church

5.10 Igualdade-β

5.11 Interpretações

5.12 Ponto fixo

5.13 Recursão

5.14 Indecidibilidade 

5.15 Conclusões 

5.16 Exercícios

Referências 

Glossário 

Apêndice A Soluções dos exercícios 

A.1 Programas, máquinas e equivalências 

A.2 Máquinas universais 

A.3 Decidibilidade 

A.4 Complexidade no tempo 

A.5 Cálculo Lambda não tipado 

Apêndice B Alfabeto grego

Índice remissivo