Teoria Da Computação

Teoria da computação

Computação pode ser definida como a solução de um problema ou, formalmente, o cálculo de uma função, através de um algoritmo. A teoria da computação, um subcampo da ciência da computação e matemática, busca determinar quais problemas podem ser computados em um dado modelo de computação. Por milhares de anos, a computação foi feita com lápis e papel, ou giz e quadro, ou mentalmente, às vezes com a ajuda de tabelas.

A teoria da computação teve início nos primeiros anos do século XX, antes da invenção dos modernos computadores eletrônicos. Naquela época, os matemáticos estavam tentando descobrir quais problemas matemáticos poderiam ser resolvidos por um método simples, e quais não poderiam. O primeiro passo estava em definir o significado de um "método simples" para resolver o problema. Em outras palavras, eles precisavam de um modelo formal da computação.

Diversos modelos diferentes da computação foram propostos pelos primeiros pesquisadores. Um modelo, conhecido como Máquina de Turing, propunha a construção de uma máquina universal, capaz de operar com uma sequência de instruções e dados entremeados em uma fita de comprimento infinito; a máquina poderia operar em um ponto da fita de cada vez utilizando um cabeçote de leitura e escrita, executando assim a programação que lhe for passada. Outro modelo se baseia em funções recursivas compostas para operar diretamente sobre os números. Uma abordagem similar é o cálculo lambda. Outra classe de abordagens trabalha com regras gramaticais operando sobre cadeias de caracteres, como é o caso dos cadeias de Markov e dos sistemas de Post.

Todos os formalismos propostos acima são equivalentes em termos de poder computacional—ou seja, qualquer computação que possa ser realizada com um modelo pode ser realizada com qualquer um dos outros modelos. Ainda em termos teóricos, os modelos propostos são equivalentes aos computadores eletrônicos, desde que não haja restrições de memória envolvidas. Na verdade, acredita-se que todas as formalizações teoricamente possíveis para o conceito de algoritmo são equivalentes em poder a uma máquina de Turing; esta é a tese de Church-Turing. As questões relativas à possibilidade de realizar certos tipos de computação em determinados tipos de máquina (ou formalismo teórico) são investigadas pela teoria da computabilidade.

A teoria da computação estuda os modelos de computação genéricos, assim como os limites da computação:

• Quais problemas jamais poderão ser resolvidos por um computador, independente da sua velocidade ou memória? (Ver: Problema da parada, Problema da Correspondência de Post.)

• Quais problemas podem ser resolvidos por um computador, mas requerem um período tão extenso de tempo para completar a ponto de tornar a solucão impraticável? (Ver:Aritmética de Presburger.)

• Em que situações podem ser mais difícil resolver um problema do que verificar cada uma das soluções manualmente? (Ver Classes P e NP).

Em geral, as questões relativas aos requerimentos de tempo ou espaço (memória, em particular) de problemas específicos são investigadas pela teoria da complexidade computacional.

Além dos modelos genéricos de computação, alguns modelos computacionais mais simples são úteis para aplicações mais restritas. Expressões regulares, são por exemplo utilizadas para especificar padrões de cadeias de caracteres, sendo populares em aplicações UNIX e em algumas linguagens de programação, como Perl e Python. Outro formalismo matematicamente equivalente às expressões regulares são os autômatos finitos, que são utilizados em desenho de circuitos e em alguns sistemas de resolução de problemas. As gramáticas livres de contexto são utilizadas para especificar a sintaxe das linguagens de programação; um formalismo equivalente, são os autômatos com pilha, oupushdown automata. As funções recursivas primitivas formam uma subclasse das funções recursivas.

Modelos de computação diferentes podem realizar tarefas distintas. Uma forma de estudar o poder de um modelo computacional é estudar a classe das linguagens formais que o modelo pode gerar; o resultado é a hierarquia de Chomsky das linguagens.

As tabelas abaixo mostram algumas das classes de problemas (ou linguagens, ou gramáticas) que são consideradas em teoria da computabilidade (azul) e em teoria da complexidade (vermelho). Se a classe X é um subconjunto propriamente contido em Y, então X é mostrado abaixo de Y, conectado por uma linha escura. Se X é um subconjunto, mas não é sabido se os conjuntos são iguais ou não, então a linha que os conecta será mais clara e pontilhada.

Problema de decisão

Tipo 0 (Recursivamente enumerável)

Indecidível

Decidível

EXPSPACE

EXPTIME

PSPACE

Tipo 1 (Sensível ao contexto)

PSPACE-Completo

Co-NP

NP

BPP

BQP

NP-Completo

P

NC

P-Completo

Tipo 2 (Livre de contexto)

Tipo 3 (Regular)

Teoria