Dissertação

Kolmogorov Generic Bases EVALUATED

Começamos por estudar a complexidade algorítmica de números e de strings (o tamanho da menor descrição do objecto em questão). Provamos que existe uma correspondência entre estas duas complexidades e seguimos para estudar complexidade de prefixo (uma restrição da complexidade algorítmica simples). Também definimos e estudamos uma forma de complexidade de demonstrações lógicas baseada no número mínimo de linhas necessário para provar uma fórmula. Aqui, adaptamos resultados conhecidos e apresentamos alguns novos. Seguidamente, usamos as semelhanças entre estes quatro tipos de complexidade para definir uma nova estrutura: a base genérica de Kolmogorov. Verificamos que instâncias desta estrutura coincidem com as complexidades previamente mencionadas. Por fim, apresentamos alguns resultados novos, nomeadamente que existem classes de bases genéricas de Kolmogorov que induzem funções não computáveis (algumas das quais podem ser aproximadas por uma função computável), funções computáveis e funções ilimitadas.
complexidade de Kolmogorov, complexidade de Kolmogorov de prefixo, complexidade de demonstrações lógicas, base genérica de Kolmogorov

Dezembro 16, 2011, 10:0

Publicação

Obra sujeita a Direitos de Autor

Orientação

ORIENTADOR

João Filipe Quintas dos Santos Rasga

Departamento de Matemática (DM)

Professor Auxiliar