Teoria da computação

A teoria da computação é um subcampo da ciência da computação e matemática que busca determinar quais problemas podem ser computados em um dado modelo de computação. A computação pode ser definida como a solução de um problema ou, formalmente, o cálculo de uma função por meio de um algoritmo. Apesar de intuitivo na história humana, o conceito de execução de uma tarefa com passos finitos a fim de se obter um resultado, ou seja, um algoritmo, não possuía uma definição formal até a conceituação do modelo de Máquina Universal de Turing.^[1]

A teoria da computação teve início nos primeiros anos do século XX, antes da invenção dos modernos computadores eletrônicos. Naquele período, após a famosa palestra do matemático alemão David Hilbert em que ele listou os maiores desafios no campo da matemática para o século vindouro, os matemáticos se debruçavam sobre o décimo problema de Hilbert tentando descobrir quais problemas matemáticos poderiam ser resolvidos por um método efetivo, e quais não poderiam. O primeiro passo estava em definir o significado de um "método efetivo" 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 fosse 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 solução impraticável? (Ver: Aritmética de Presburger.)
Em que situações pode 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, ou pushdown 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, conectados por um 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)

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)

Ver também

Problemas em aberto da Ciência da computação

Referências

↑ Michael Sipser (2013). Introduction to the Theory of Computation 3rd. [S.l.]: Cengage Learning. ISBN 978-1-133-18779-0. central areas of the theory of computation: automata, computability, and complexity. (Page 1)