Modelos Abstratos e Computabilidade Flashcards
Conceito de programa
Conjunto estruturado de instruções, capacita uma máquina a aplicar sucessivamente operações básicas e testes.
Conceito de máquina
Dá significado aos identificadores das operações e testes.
O que é computação?
Histórico das instruções de um programa executados em uma máquina.
O que é função computada?
Computação de um programa associada a uma entrada e uma saída.
Defina algoritmo.
Não possui definição, soluciona problemas, descrito de forma ambígua, consiste de passos discretos, executável em tempo finito e usa recursos tão grandes quanto necessário.
Hilbert, David
Procedimento para demonstrar se uma dada fórmula no calculo de predicados de primeira ordem era válida ou não. Encontrar um conjunto completo e consistente de axiomas para toda a matemática.
Godel, Kurt
Teorema da não completude. Demonstrou que o processo de provas não tem solução. Uso de números naturais para codificar símbolos, formulas e sequencias de formulas.
Church, Alonzo
Calculo lambda f(x)=x²+4. Mostrou que o problema de Hilbert não tem solução.
Turing, Alan
Maquina de turing, modelo elementar que imita o comportamento de um pc, fica com alfabeto infinito, leitura, escrita e movimentos laterais, numero de estados finitos.
Post, Emil
Máquina de post, uso de uma fita para armazenar dados, alfabeto finito, regras de produção.
Markov, Andrey Jr
Algoritmo de Markov, regras de substituição aplicadas em ordem, para quando não houver regra.
Máquinas Universais
Calculo lambda, funções recursivas, máquina de turing, sistema canômico de Post e algoritmo de markov.
