Todos os formalismos propostos acima são equivalentes em termos de poder computacional—ou seja, qualquer computação que possa ser realizada com um modelo pode ser realizada com qualquer um dos outros modelos. Ainda em termos teóricos, os modelos propostos são equivalentes aos computadores eletrônicos, desde que não haja restrições de memória envolvidas. Na verdade, acredita-se que todas as formalizações teoricamente possíveis para o conceito de algoritmo são equivalentes em poder a uma máquina de Turing; esta é a tese de Church-Turing. As questões relativas à possibilidade de realizar certos tipos de computação em determinados tipos de máquina (ou formalismo teórico) são investigadas pela teoria da computabilidade.