Teoria da computação

Teoria da Computação
João Carlos Veiga Salles
Marcos Meguro Marreiro
Ramon Vallente Cancer
Resumo. Este trabalho tem por objetivo apresentar os mais relevantes assuntos da Teoria da Computação. A Teoria da Computação é a ciência-chave na investigação de novos modelos de computação. O paradigma de Von Newman encontrará em breve seu limite de capacidade de processamento, limite esse imposto pelas leis da física. Dentro de pouco tempo, não haverá mais possibilidade de miniaturização nas pastilhas de semicondutores, base para a construção de computadores digitais nesse paradigma. Surge aí a necessidade de se investigar e desenvolver novos meios de computar, utilizando diferentes matérias e teorias para esse fim.

Introdução
A Teoria da Computação é uma área de estudo em constante desenvolvimento e crescimento, que desempenha um papel fundamental nas ciências que envolvem a computação. O formalismo desenvolvido nos primórdios da computação, na época anterior à criação da tecnologia que atualmente dá suporte a construção de computadores digitais, foi fundamental para que estes pudessem ser efetivamente construídos. Neste trabalho apresentam-se os conhecimentos básicos a respeito da Teoria da Computação, como conjuntos, funções, alfabetos, autômatos, problemas P e NP e decidibilidade.
Conjuntos, Relações e Linguagens
Conjuntos
Um conjunto é uma coleção de objetos. Por exemplo, a coleção das quatro letras a, b, c, d é um conjunto, que podemos chamar de L; escrevemos L = {a, b, c, d}. Os objetos pertencentes ao conjunto são chamados de elementos ou membros. No exemplo acima, b é um elemento de L, e podemos escrever b E L.
Em um conjunto, não distinguimos repetições de elementos. Portanto, o conjunto L = {a, b, a} é o mesmo que o conjunto M = {a, b}. Da mesma maneira, a ordem dos elementos em um conjunto não importa, sendo iguais os conjuntos A = {a, b, c} e B = {c, b, a}. Resumindo, dois conjuntos são iguais se e somente se eles têm os mesmos elementos.
Chamamos