Thèse de Turing-Church

def (nouvelle) Une procédure effective est une solution à un problème qui a la forme d’un programme pouvant être exécuté sur un ordinateur en un temps fini pour toutes les entrées.

Thèse de Turing-Church : Les langages reconnus par une procédure effective sont exactement ceux décidés par une machine de Turing.

lem.: Tout langage décidé par une machine de Turing est reconnu par une procédure effective.

Conjecture : Pour tout langage reconnu par une procédure effective, il existe une machine de Turing qui le décide.

Extensions des Machines de Turing

- Ruban infini dans les deux sens,

- Rubans multiples,

- Machines à mémoire à accès direct.

Toutes ces machines peuvent être simulées par une machine de Turing.

- Machines de Turing non-déterministes (une relation de transition remplace la fonction de transition).

Th.: Tout langage accepté par une machine de Turing non-déterministe est aussi accepté par une machine de Turing déterministe.