Estuda o que é possível e impossível de ser computado por sistemas computacionais

A máquina de Turing é um modelo abstrato de um sistema computacional que consiste em uma fita infinita e um cabeçote que lê e escreve na fita

A teoria de computabilidade ajuda a identificar problemas que não podem ser resolvidos por nenhum sistema computacional

A classe NP é o conjunto de problemas que podem ser verificados em tempo polinomial

A classe P é o conjunto de problemas que podem ser resolvidos em tempo polinomial

Estuda a dificuldade computacional dos problemas

A teoria de complexidade ajuda a identificar problemas que são computacionalmente difíceis ou impossíveis de serem resolvidos em tempo polinomial.

A complexidade de um problema é medida pelo tempo e/ou espaço necessários para resolvê-lo em um determinado modelo computacional

Estuda máquinas abstratas que recebem uma entrada e produzem uma saída

Autômatos são usados para modelar sistemas como softwares, circuitos eletrônicos, sistemas de controle etc

Um tipo de autômato é a máquina de estados finitos, que é uma representação matemática de um sistema com um número finito de estados

A teoria de autômatos ajuda a entender a capacidade dos sistemas para processar informações