Demonstração da coerência do programa com os objectivos

Exploram-se três modelos computacionais: autómatos finitos, autómatos de pilha, máquinas de Turing, de modo a que seja possível a sua aplicação na representação formal de problemas reais. A escolha adequada de um modelo computacional para a representação de um problema é feita tendo em conta as capacidades e limites de cada modelo, determinadas por inspeção do método de computação empregue em cada modelo. Para determinar que uma linguagem é indecidível, exploram-se técnicas de redução e o problema de paragem. Determinam-se as classes de complexidade para diversos problemas, culminando na distinção entre problemas tratáveis e intratáveis, sendo um problema intratável aquele para o qual não conseguimos uma respsta em tempo útil, problemas não computáveis, problemas para os quais não se conhece uma solução.