Complétude de Turing

Propriété d'un système computationnel indiquant qu'il peut simuler n'importe quelle machine programmable générale et donc réaliser tout calcul qu'une telle machine idéale peut effectuer, à condition de disposer de temps et de mémoire non bornés.