A teoria da computação é uma área de intersecção entre matemática e computação que busca determinar quais problemas podem ser computados em um dado modelo de computação. Para tal, são necessárias definições formais de modelos de computação e seus componentes.