Modelo de computação

Em teoria da computabilidade, um modelo de computação é a definição de um conjunto de operações que podem ser usadas numa computação e seus respectivos custos. Somente assumindo certo modelo de computação é possível analisar os recursos computacionais requeridos, como tempo de execução e espaço de armazenamento, ou discutir as limitações de algoritmos ou computadores. Na área de análise de algoritmos, é comum especificar um modelo de computação em termos de operações primitivas, cada uma com um custo unitário associado.

Alguns exemplos de modelos de computação incluem a máquina de Turing, função recursiva, cálculo lambda e sistema de produção. Há diversos modelos, que diferem entre si no conjunto de operações e custos associados. De forma geral, eles são categorizados em máquinas abstratas, usadas em provas de computabilidade e no cálculo dos limites máximos na complexidade de algoritmos, e modelos de árvore de decisão, usados em provas dos limites mínimos de complexidade em problemas algorítmicos.