Introduction

On peut représenter les calculs qu’un ordinateur est capable de faire par ce qu’on appelle une machine de Turing ou le lambda-calcul.

Ces deux modèles (qui sont équivalents dans une certaine mesure) permettent notamment de définir quel problème est décidable et calculable par un programme informatique, ou plus largement par un algorithme.

Alan Turing est un mathématicien Anglais et Alonzo Church, un mathématicien Américain à l’origine notamment du lambda-calcul.

A l’origine le problème de décision (Entscheidungsproblem à l'origine en allemand ) qui consistait à savoir si pour tout énoncé mathématique, il existe un algorithme capable de décider s’il est Vrai ou Faux, a été défini par le mathématicien Hilbert en 1900.

En fait, on peut même remonter à Leibniz (au 17ème siècle) qui supposait que l’on pouvait construire une machine qui répondrait automatiquement à cette question.

A présent, nous allons définir les termes “Calculables” et “Décidables”, ensuite nous allons présenter le problème de l’arrêt et expliquer pourquoi celui-ci est indécidable.

1) Définitions

1.1) Décidabilité

Intuitivement, on peut dire qu’un problème P est décidable, si, pour chaque donnée x (qui peut être une certaine équation par exemple) passée à P on peut répondre par OUI ou NON à la question : “est ce que P(x) est vrai ?”

On s’intéresse ici plutôt à la définition algorithmique de la décidabilité (qui est quasiment la même que la définition mathématique).

Dans ce cadre, un problème de décision est dit décidable s'il existe un algorithme, une procédure mécanique qui termine en un nombre fini d'étapes, qui le décide, c'est-à-dire qui réponde par oui ou par non à la question posée par le problème.

S'il n'existe pas de tels algorithmes, le problème est dit indécidable.

Exemple de problème décidable :

• Le problème qui consiste à décider si un entier naturel est pair ou impair est décidable

Exemple de problèmes indécidables :

• Le problème de l’arrêt (que nous allons étudier) qui consiste à déterminer s’il existe un algorithme H capable de déterminer si à partir d’une entrée x et d’ un algorithme quelconque P, l'algorithme s’arrêtera (pas de boucle infinie dans le cas d’un programme).

• Déterminer s'il existe un algorithme capable de résoudre une équation diophantienne quelconque

1.2) Calculabilité

Une fonction (au sens mathématique), ou un algorithme est dit calculable si il peut être calculé par un ordinateur. En fait, pour être plus précis on devrait dire si il est calculable par une machine de Turing.

2) Le problème de l’arrêt

Nous allons simplifier la présentation de ce problème et parlerons par exemple de programme informatique plutôt que d’algorithme.

Le problème de l’arrêt consiste à déterminer s’il existe un programme H (comme halting, puisque le problème s’appelle à l’origine “halting problem” en anglais) capable de déterminer si à partir d’un programme P quelconque et de données d utilisées par le programme P est capable de déterminer si ce programme va s’arrêter à un moment, ou s’il “entrera dans une boucle infinie”.

Nous allons montrer que ce problème est indécidable, c'est-à-dire qu’il n’existe pas de programme H qui résout ce problème.

3) Le problème de l’arrêt est indécidable

Supposons qu’un tel programme existe et supposons qu’il existe une machine H_INVERSE qui fonctionne comme H mais qui ne se termine pas lorsque le programme renvoie OUI et qui se termine si le programme renvoie NON. Supposons que le programme H_INVERSE prenne en entrée son propre programme en données H_INVERSE. Ensuite, ce programme fait appel à la fonction H qui va utiliser H_INVERSE comme programme et comme données.

Ainsi on peut voir le programme H_INVERSE comme une donnée utilisée par le programme H_INVERSE. En fait, avoir un programme qui utilise des programmes comme des données, c’est quelque chose qui arrive quasiment tout le temps. Par exemple, l’interpréteur Python est un programme qui utilise votre programme Python comme une donnée pour fournir ensuite du ByteCode qu’il va exécuter. Votre système d’exploitation utilise également plusieurs programmes comme des données dont il va notamment devoir gérer l’ordre d’exécution.

Alors, lorsque H_INVERSE est exécuté avec le programme H_INVERSE, le programme H_INVERSE décide que le programme H_INVERSE se termine et renvoie OUI. Par contre, dans ce cas, le programme H_INVERSE décide que le programme H_INVERSE ne s’arrête pas. Il y a contradiction.

De même, lorsque H(H_INVERSE, H_INVERSE) renvoie NON et décide que le programme H_INVERSE se termine, alors H_INVERSE ne se termine pas. Il y a à nouveau contradiction.

On dit que le problème de l’arrêt est indécidable car il n’existe pas d’algorithme capable de répondre par OUI dans le cas où un programme s’arrête ou NON dans le cas où le programme ne s’arrête pas.

La version Python de ce problème (la fonction h ne peut pas exister):

def h(programme, donnees):
    """
    On suppose que ce programme existe
    """
    pass

def h_inverse(code_h_inverse):
    if not h(code_h_inverse, code_h_inverse):
        return
    else:
        # Boucle infinie
        while h(code_h_inverse, code_h_inverse):
            pass

code_h_inverse="""
def h_inverse(code_h_inverse):
    if not h(code_h_inverse, code_h_inverse):
        return
    else:
        # Boucle infinie
        while h(code_h_inverse, code_h_inverse):
            pass
"""
# Que se passe-t-il ici ?
h_inverse(code_h_inverse)

Conclusion

Nous avons vu que le problème de l'arrêt est indécidable. Pour définir rigoureusement l'indécidabilité, il aurait fallu introduire les machines de Turing, si vous voulez en savoir plus, surtout n'hésitez pas à regarder cette vidéo :