Teoria da Computação - Introducao

Prévia do material em texto

Teoria da Computação
Introdução e roteiro histórico
Prof. Walace de Almeida Rodrigues
Instituto Federal de Minas Gerais - Campus Formiga
22 de outubro de 2015
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 1 / 49
Sumário
1 Introdução
Importância
Motivação
Método de estudo
Roteiro
2 Os precursores
Leibniz
Boole
Hilbert
3 Kurt Gödel
Teorema da Incompletude
4 Alan Turing
Máquina de Turing
Tese de Church-Turing
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 2 / 49
1. Introdução
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 3 / 49
1.1. Importância
Conhecer as idéias que conduziram o avanço da computação
— O entendimento da teoria passa pelo conhecimento das idéias
— Conhecer a história da computação é remédio contra o dogmatismo
— Aumento da consciência da importância do trabalho de pesquisa
Um cientista da computação conhece a história da computação
— O trabalho do cientista exige o conhecimento da ciência
— O conhecimento da ciência exige o conhecimento da história
— Não se entende o desenvolvimento da computação sem sua história
Criar condições para avaliar o que esperar no futuro
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 4 / 49
1.2. Motivação
1 Necessidade de discernir os fundamentos
— O horizonte da computação tornou-se extenso e complexo
— Hoje existe a dificuldade de se ter uma visão global da área
— Risco de falta de profundidade e visão utilitarista da computação
— Risco de incompreensão dos conceitos fundamentais da área
Importante: evitar a tentação de se imaginar um curso
de ciência da computação com pouca fundamentação
teórica e/ou baseado em produtos e tecnologias
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 5 / 49
1.2. Motivação
2 Incentivo à educação para qualidade de software
— Importância da especificação formal na automatização
— Necessidade de treinamento formal para cientistas da computação
— Desenvolvimento da área da lógica matemática
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 6 / 49
1.2. Motivação
3 Tornar claros e ligar os fatos conceituais
— Conhecer como nasceram as idéias na ciência da computação
— Avaliar a qualidade do progresso atual
— Acompanhar novas tendências
4 Revalorizar o fator humano
— Não se deixar iludir pelo destaque das demandas imediatas
— Perceber que o avanço atual resultou do esforço de várias áreas
— Compreender a conexão entre computação e matemática
— Entender melhor o papel social da computação
— Entender melhor para onde aponta o futuro da computação
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 7 / 49
1.3. Método de estudo
Não está no nosso escopo discutir filosofia da história
Abraçamos um paradigma que destaca dois eixos principais:
Eixo morfológico: o que é um fato histórico? (quais são?)
Eixo teleológico: como se conectam e para onde apontam?
Queremos conhecer o passado para:
Decorar nomes e datas (não)
Conhecer as idéias e fundamentos (sim) X
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 8 / 49
1.4. Roteiro
Fiz um recorte destacando alguns personagens e fatos conceituais
Precursores:
G.W.Leibniz (1716 d)
⇒ Tentativa de formalizar as discussões filosóficas
⇒ Busca da linguagem universal para calcular raciocínios
G.Boole (1864 d)
⇒ Criação do primeiro sistema formal para o raciocínio lógico
⇒ Fundador da lógica simbólica
Hilbert (1943 d)
⇒ Esforço para unificar formalmente a matemática e a lógica
⇒ Busca por um sistema formal completo e consistente
Gödel (1978 d) — Teorema da Incompletude
Turing (1954 d) — Máquina de Turing
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 9 / 49
2. Os precursores
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 10 / 49
2.1. Leibniz
Gottfried Wilhelm Leibniz (1646 – 1716), filósofo e matemático alemão
Queria estabelecer as bases para formalizar as discussões filosóficas
Imaginava substituir o “diálogo filosófico” por um “cálculo filosófico”
Projeto de criação de uma linguagem universal para mapear o raciocínio
Plano apoiado em dois pilares:
1 Simbolismo
2 Cálculo formal
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 11 / 49
2.1. Leibniz – uma linguagem para o raciocínio
1 Simbolismo
⇒ Idéia chave: estabelecer um “alfabeto do pensamento”
⇒ Representar as noções e princípios com símbolos
⇒ Representar os movimentos do raciocínio com operadores
⇒ Criou a lógica moderna (embrião)
2 Cálculo formal:
⇒ Idéia chave: todo raciocínio é um tipo de cálculo
“Quando surge a controvérsia, não é mais necessário
disputarem dois filósofos, mas dois computistas”
⇒ Possibilidade de calcular raciocínios: idéia para um computador
⇒ Leibniz tentou construir um computador mecânico
⇒ Criou o cálculo infinitesimal (em paralelo com Isaac Newton)
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 12 / 49
2.1. Leibniz – algumas de suas contribuições
Sua notação para o cálculo integral era melhor que a de Newton
Sua notação para a lógica se aproximou da lógica simbólica atual
Pensou o sistema binário para uso na aritmética
Demonstrou a vantagem do sistema binário para as máquinas
Em 1673, desenvolveu uma calculadora com engrenagens dentadas
capaz de computar as 4 operações básicas e raiz quadrada
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 13 / 49
2.2. Boole
George Boole (1815 – 1864), matemático autodidata inglês
Desenvolveu o primeiro sistema lógico formal para o raciocínio lógico
Seu formalismo não exigia noções primitivas anteriores
– a validade de um cálculo não dependia do significado dos símbolos
– ela dependia somente da exclusiva combinação entre os símbolos
Baseou seu sistema em duas quantidades: “universo” ou “nada”
Acreditava que sua álgebra sistematizava todo raciocínio humano
Acreditava ter demonstrado a unidade entre matemática e lógica
Boole é considerado por muitos o pai da lógica simbólica
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 14 / 49
2.2. Boole – dificuldades e avanços posteriores
Problema: a lógica booleana estava limitada ao raciocínio proposicional
Charles Sanders Peirce (1914 d):
— filósofo americano, fundador do Pragmatismo e da Semiótica
— introduziu os quantificadores existenciais
Edmund Gustav Albrecht Husserl (1938 d):
— filósofo alemão, pai da Fenomenologia
— demonstrou que a razão humana é mais complicada e ambígua,
difícil de ser conceituada e poderosa que a lógica formal
Friedrich Ludwig Gottlob Frege (1925 d):
— filósofo alemão que reavivou o projeto de Leibniz
— avançou o estudo e a formalização da semântica
— tentou demostrar que toda a matemática é pura lógica
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 15 / 49
2.3. Hilbert
David Hilbert (1862 – 1943), matemático alemão
Procurou avançar e colocar em prática as idéias de Frege
Sua obra marca uma guinada no conceito de lógica: os objetos da
investigação lógica já não são mais as fórmulas, são as regras de
operação pelas quais elas se formam e deduzem −→ algorimos
Fermenta o idéia de demonstrar/formalizar toda a matemática
Surgem as três grandes escolas da lógica:
1 Logicista
2 Intuicionista
3 Formalista
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 16 / 49
2.3. Hilbert – as três escolas da lógica
1 Escola logicista:
— existem relações que o matemático deve descobrir, não inventar
— essa escola recebeu muitas críticas por “platonismo”
2 Escola intuicionista:— aceita provar uma teoria recorrendo a verdades evidentes de outras
— essa escola foi muito criticada por ser “demasiado subjetiva”
3 Formalista:
— foi a escola que mais progrediu, desenvolvendo novos métodos
— redefiniu axioma de “verdade evidente” para “ponto de partida”
— Hilbert e John von Newmann, seu aluno, eram formalistas
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 17 / 49
2.3. Hilbert – a escola formalista
Como formalista, Hilbert acreditava que:
— toda matemática poderia ser provada a partir de uns axiomas básicos
— a matemática seria capaz de responder qualquer pergunta
— a matemática devia ser totalmente livre de inconsistências
Com Hilbert se inicia o tempo da Metamatemática e da Metalógica
Florece a filosofia da lógica:
— as discussões sobre o valor e os limites da axiomatização
— o nexo entre lógica e matemática
— o problema da verdade (Hilbert, Gödel, Tarski)
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 18 / 49
2.3. Hilbert – formalismo e semântica
O problema da verdade:
— verdade significa correspondência com a realidade:
“o céu é azul” é verdade se e somente se o céu for azul
— qual o significado de verdade para axiomas “ponto de partida”?
Alfred Tarski (1983 d), filósofo e matemático polonês:
Paradoxo do mentiroso:
“a proposição S não é verdadeira” (V ou F?)
— verdade é satisfazer uma série de condições pré-estabelecidas
— Tarski estabeleceu as condições chamadas de “Esquema T”
— formalmente, verdade é satisfazer o “Esquema T”
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 19 / 49
2.3. Hilbert – o tempo dos algoritmos
Em 1900, Hilbert apresentou no Congresso de Matemática de Paris
os famosos 23 problemas não-resolvidos da matemática que ele
considerava de imediata importância
Procurou unir os esforços de toda comunidade matemática para
ajudá-lo no projeto de formalizar toda a matemática, estabelecer
suas bases e eliminar as inconsistências
Exemplo de problema proposto por Hilbert
Problema 10: problema de decisão
Descreva um algoritmo que determine se uma dada
equação diofantina do tipo P(u1,u2, ...,un) = 0, onde P
é um polinômio com coeficientes inteiros, tem ou não
tem solução dentro do conjunto dos inteiros
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 20 / 49
2.3. Hilbert – algoritmos e computadores
Em 1928, Hilbert lançou novo desafio no Congresso Internacional de
Bologna:
É possível construir uma “máquina de gerar enunciados
matemáticos verdadeiros” que, uma vez alimentada com
um enunciado matemático, poderia dizer se esse enun-
ciado é falso ou verdadeiro?
O contexto científico da época agora está preparado para Gödel
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 21 / 49
3. Kurt Gödel
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 22 / 49
3.1. Contexto histórico
Kurt Friedrish Gödel (1906 – 1978), matemático tcheco, nat. americano
Em 1929, tese de doutorado: “Sobre a completude do cálculo lógico”
Demonstra que se uma teoria admite um modelo não-contraditório,
então ela é não-contraditória
As questões de Hilbert estavam na moda...
Gödel era um formalista, mas desconfiava que a
formalização completa desejada por Hilbert seria
impossível
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 23 / 49
3.2. Definições de Completude
Existem duas definições de completude:
Completude semântica — um sistema de axiomas é completo
quando todos os teoremas verdadeiros da teoria podem ser
deduzidos a partir dele
Completude sintática — um sistema de axiomas é completo
quando toda tentativa de lhe adicionar um novo axioma
(independente dos anteriores) resulta em contradição
Gödel se interessou pela completude semântica
Estratégia de Gödel para checar a completude de um sistema:
passo 1 construir um modelo para o sistema
passo 2 provar que esse modelo não é contraditório
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 24 / 49
Kurt Gödel
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 25 / 49
3.3. Teorema da Incompletude
Questão:
É possível formalizar toda a matemática até torná-la um
sistema com completude semântica?
Suspeita: Esse objetivo é impossível
Problema: É possível provar isso?
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 26 / 49
3.3.1. Roteiro para Demonstração [TeoInc]
1 Reduzir o problema inicial
Sistema consistente × Sistema inconsistente
O sistema abaixo é consistente ou inconsistente?
x +2y = 13
3x −y = −11
É consistente se tem pelo menos uma solução.
É inconsistente se não tem solução.
Se o modelo formal para a matemática admitir proposições
inconsistentes então ele não terá completude semântica
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 27 / 49
3.3.1. Roteiro para Demonstração [TeoInc]
1 Reduzir o problema inicial
Metamatemática
— Conceito formulado por Jacques Herbrand em 1930
— Estuda a linguagem e os métodos formais de prova
— Para Hilbert era a prova matemática através da lógica
Proposição Campo
“5 = 2+3” matemática
“a equação “5 = 2+3” é verdadeira” metamatemática
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 28 / 49
3.3.1. Roteiro para Demonstração [TeoInc]
1 Reduzir o problema inicial
Aritmética
— Ramo da matemática que estuda os números e
as operações básicas realizadas com eles
— Hilbert mostrou que a aritmética é a base para
toda a matemática
— Toda proposição matematica pode ser mapeada
para a aritmética
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 29 / 49
3.3.1. Roteiro para Demonstração [TeoInc]
1 Reduzir o problema inicial
Plano de trabalho:
Passo 1: construir um modelo formal completo
mapear a matemática para a aritmética (Hilbert)
mapear a metamatemática para a aritmética
criar uma linguagem para proposições aritméticas
Passo 2: mostrar nele a existência de indecidíveis
construir uma proposição indecidível
O sistema matemático deve ser fechado =⇒ A linguagem deve ser aritmética
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 30 / 49
3.3.1. Roteiro para Demonstração [TeoInc]
2 Construção de uma linguagem formal com as características:
ser capaz de descrever proposições matemáticas
ser capaz de descrever proposições metamatemáticas
ser ela mesma explicada através da aritmética
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 31 / 49
3.3.2. Os números de Gödel [TeoInc]
Criação da linguagem:
1 associar um número natural para cada símbolo da linguagem
Sinal Número de Gödel Significado
∼ 1 não
∨ 2 ou
r 3 se...então
$ 4 existe
= 5 igual
0 6 zero
s 7 sucessor
( 8 pontuação
) 9 pontuação
, 10 pontuação
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 32 / 49
3.3.2. Os números de Gödel [TeoInc]
Criação da linguagem:
2 associar um primo > 10 para cada variável independente
Sinal Número de Gödel Significado
x 11 variável independente
y 13 variável independente
z 17 variável independente
...
...
...
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 33 / 49
3.3.2. Os números de Gödel [TeoInc]
Criação da linguagem:
3 numerar as fórmulas com os quadrados dos primos > 10
Sinal Número de Gödel Significado
p 112 fórmula matemática
q 132 fórmula matemática
r 172 fórmula matemática
...
...
...
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 34 / 49
3.3.2. Os números de Gödel [TeoInc]
Criaçãoda linguagem:
4 outras noções também podem ser numeradas:
– numerar propriedades com os cubos dos primos > 10
– etc
5 Utilizando números de Gödel é possível associar de
maneira única um número a uma sentença matemática
Como?
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 35 / 49
3.3.2. Os números de Gödel [TeoInc]
Mapeamento das sentenças:
Exemplo:
“Existe um x que é o sucessor de y”
⇓
($x)(x = sy)
⇓
( $ x ) ( x = x y )
8 4 11 9 8 11 5 7 13 9
⇓
28∗34∗511∗79∗118∗1311∗175∗197∗2313∗299
⇓
Número de Gödel
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 36 / 49
3.3.2. Os números de Gödel [TeoInc]
Mapeamento das sentenças:
Sentença para número:
— representa cada símbolo por seu número equivalente
— usa cada número como expoente dos primos em sequência
— obtém o Número de Gödel como resultado da soma
Número para sentença:
— fatorar o número
— verificar se a fatoração obtém todos os primos em sequência
— obtém a sentença como resultado da fatoração
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 37 / 49
3.3.3. A existência de indecidíveis [TeoInc]
Construção de um indecidível:
Sentenças do tipo pr p representam provas matemáticas com
significado “a fórmula p é uma demonstração da fórmula q”
Seja Dem(x,y) uma sentença com significado “o conjunto de
fórmulas cujo número de Gödel é x é uma prova da fórmula
cujo número de Gödel é y”
A sentença ($y)(x)∼Dem(x,y) representa um paradoxo, ela diz:
— existe uma sentença cujo número de Gödel é y
— para qualquer fórmula x, vale ∼Dem(x,y)
— logo, não existe nenhuma fórmula x que demonstre y
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 38 / 49
3.3.3. A existência de indecidíveis [TeoInc]
Demonstração da existência de um indecidível:
Seja G(y) o número de Gödel referente à fórmula (x)∼Dem(x,y)
Observe que para cada número y vai existir um novo número G(y)
Gödel demonstrou que a função G(y) tem um ponto fixo:
— Ele mostrou que a equação G(y)=y tem solução
— Essa é a parte mais delicada da prova de Gödel
— Ela não será apresentada aqui
Significado da equação G(y)=y:
“a fórmula com número de Gödel y (que sou eu mesma)
não pode ser demonstrada”
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 39 / 49
3.4. Avaliação prática do teorema da incompletude
Se a matemática é consistente:
1 Sua consistência não pode ser provada dentro da própria matemática
2 A matemática é incompleta (existem indecidíveis)
Conclusão prática:
1 O preço da consistência é a incompletude:
— para a matemática ser útil, ela deve ser consistente
— mas as inconsistências sempre vão existir
— precisamos identificá-las e separá-las fora do sistema
— é impossível eliminar todas as inconsistências
2 Essa conclusão vale para qualquer sistema
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 40 / 49
4. Alan Turing
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 41 / 49
4.1. Contexto histórico
Alan Mathison Turing (1912 – 1954), matemático britânico
Era estudante em Cambridge em 1935 quando, numa aula de
Newmann, tomou conhecimento dos problemas de Hilbert
Em 1936 demonstrou que era possível executar operações sobre a
teoria dos números numa máquina equipada com as regras de um
sistema formal:
— definiu a máquina teórica conhecida como Máquina de Turing
— formalizou a noção intuitiva de algoritmo
É considerado por muitos o pai da ciência da computação e da IA
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 42 / 49
Alan Turing
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 43 / 49
4.2. Máquina de Turing
“Computar é normalmente escrever símbolos em um
papel. Suponha que o papel é quadriculado, podendo
ser ignorada a bidimensionalidade, que não é essencial.
Suponha que o número de símbolos é finito. O compor-
tamento do computador é determinado pelos símbolos
que ele observa num dado momento, e seu estado men-
tal nesse momento.
Admitamos um número finito de estados mentais. Va-
mos imaginar que as ações feitas pelo computador se-
rão divididas em operações tão elementares que são
indivisíveis. . . .” (Alan Turing)
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 44 / 49
Implementação da Máquina de Turing
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 45 / 49
4.3. Tese de Church-Turing
Em 1936, Turing estava interessado na lógica e no raciocínio humano:
— definiu um computador teórico e formalizou a noção de algorimo
— sua máquina prefigurou o aparecimento dos computadores
Em 1936, Alonzo Church (1995 d), lógico americano, estava interessado
nos fundamentos da matemática:
— desenvolveu uma teoria de funções para mecanização da lógica
— do refinamento dessa teoria resultou a cálculo λ
— o cálculo λ prefigura o aparecimento das ling. de programação
Em 1936, Stephen Kleene (1994 d), matemático americano, aluno de
Church, estava interessado na lógica matemática:
— desenvolveu a teoria das funções recursivas
— demonstrou que essa teoria tem expressividade equivalente ao
cálculo λ e às máquinas de Turing
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 46 / 49
4.3. Tese de Church-Turing
Alan Turing:
“Toda função que seria naturalmente considerada
computável pode ser computada por uma Máquina
de Turing.”
Alonzo Church:
“Toda função efetivamente calculável é uma função com-
putável.”
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 47 / 49
4.3. Tese de Church-Turing
Versão estendida:
“O que informalmente entendemos por algoritmo pode
ser expresso em termos de uma Máquina de Turing, ou
em Cálculo λ, ou em Funções Parciais Recursivas.”
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 48 / 49
Referências
“Uma viagem informal ao teorema de Gödel”, Ricardo Kubrusly
http://im.ufrj.br/~risk/diversos/godel.html
“História da Computação”, Cléuzio Fonseca Filho
http://www.pucrs.br/edipucrs/online/
historiadacomputacao.pdf
walace.rodrigues@ifmg.edu.br (IFMG) Teoria da Computação 22 de outubro de 2015 49 / 49
	Introdução
	Importância
	Motivação
	Método de estudo
	Roteiro
	Os precursores
	Leibniz
	Boole
	Hilbert
	Kurt Gödel
	Teorema da Incompletude
	Alan Turing
	Máquina de Turing
	Tese de Church-Turing