La machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, comme un ordinateur. Ce modèle a été imaginé par Alan Turing en 1936, en vue de donner une définition précise du concept d’algorithme ou de « procédure mécanique ». Il est toujours largement utilisé en informatique théorique, en particulier dans les domaines de la complexité algorithmique et de la calculabilité.

À l'origine, la machine de Turing a été inventé avant l'ordinateur et est censé représenter une personne virtuelle exécutant une procédure bien définie, en changeant le contenu des cases d'un ruban infini, en choisissant ce contenu parmi un ensemble fini de symboles. D'autre part, à chaque étape de la procédure, la personne doit se placer dans un état particulier parmi un ensemble fini d'états.