Decidibilidade

[pic]

Teoria da Computação

Decidibilidade

Grupo: Marcello Almeida Victor Lélis

1. Introdução

Muito antes dos computadores modernos terem sido inventados, a teoria da computação já havia sido iniciada e estava em desenvolvimento. Matemáticos de todo o mundo buscavam resolver problemas através de processos com um número finito de passos que pudessem sempre retornar resultados corretos para uma mesma questão. Apesar de não ter sido bem definido durante séculos, o conceito de algoritmo sempre foi utilizado e aperfeiçoado de forma implícita pela comunidade matemática. Durante o Segundo Congresso Internacional de Matemática, realizado em Paris no ano de 1900, David Hilbert apresentou 23 questões não resolvidas pertinentes à toda a sociedade matemática. Nesta lista o décimo problema dizia respeito aos algoritmos. Usados ainda sem um conceito concreto, Hilbert requisitou explicitamente um algoritmo para a identificação de existência de raízes inteiras para um polinômio.
Mesmo com o problema não resolvido (ou provado que não pode ser resolvido), um grande avanço permitiu uma melhor análise do mesmo: a publicação da chamada Tese de Church-Turing, em 1936. O artigo definia precisamente a noção de algoritmo que se fazia ausente até então e estava inviabilizando a continuidade do estudo na área. A Tese de Chuch-Turing afirma que, possuindo tempo e capacidade de espaço suficiente, qualquer função que pode ser computada naturalmente pode ser computada através de um algoritmo em um computador. Através disso é possível perceber que até o mais simples computador (em questão de velocidade e tamanho de memória) , possui teoricamente poder equivalente que um outro qualquer. Para a realização da tese o importante conceito de Máquina de Turing foi definido e associado com algoritmos, da forma “um algoritmo é um processo descrito por uma Máquina de Turing” (Gurevich 2000).