Universidade Federal de Pernambuco (UFPE) Centro de Informática (CIn) Graduação em Ciência da Computação
IF689 - Informática Teórica
Descrição:
Você sabe o que é:
computabilidade?
problema de `decisão'?
decidibilidade?
linguagem decidida por autômato?
problema da parada?
máquina de Turing?
tese de Church-Turing?
sistema de Post?
função computável?
função factivelmente computável?
problema intratável?
De que trata o curso?
A noção de procedimento efetivo, que deu origem às
primeiras "máquinas abstratas de computação efetiva"
(como, por exemplo, a chamada
Máquina de Turing,
o primeiro modelo de computador programável por software, e que deu
origem à chamada
Tese de Church que afirma que qualquer função
efetivamente computável pode ser computável por uma
Máquina de Turing apropriadamente definida) está
intimamente ligada à noção de "dedução em
um sistema formal (simbólico)", como concebido por
Gottlob Frege,
o mentor da Lógica Moderna, justamente porque esta última veio
como a implementação do sonho do filósofo
Leibniz
(século XVII) de criar uma máquina de verificação
da validade de argumentos.