Les machines de Turing
Une bande de papier divisée en cases, infinie, sur laquelle sera stockée le programme
Un pointeur, qui indique la case active
Un indicateur d ’états, qui garde en mémoire l ’état de la machine
Un programme sous la forme d ’un tableau à deux entrées: le symbole inscrit sur la case, et l ’état de la machine