Além dos modelos genéricos de computação, alguns modelos computacionais mais simples são úteis para aplicações mais restritas. Expressões regulares, são por exemplo utilizadas para especificar padrões de cadeias de caracteres, sendo populares em aplicações UNIX e em algumas linguagens de programação, como Perl e Python. Outro formalismo matematicamente equivalente às expressões regulares são os autômatos finitos, que são utilizados em desenho de circuitos e em alguns sistemas de resolução de problemas. As gramáticas livres de contexto são utilizadas para especificar a sintaxe das linguagens de programação; um formalismo equivalente, são os autômatos com pilha, ou pushdown automata. As funções recursivas primitivas formam uma subclasse das funções recursivas.