Informatique au lycée Faustin Fleret

Programme en tant que donnée

Un programme informatique est un ensemble d'instructions écrites dans un langage de programmation spécifique, qui est exécuté par un ordinateur pour réaliser une tâche. Ces programmes sont créés par des programmeurs, qui utilisent des langages de programmation pour écrire des algorithmes qui résolvent des problèmes spécifiques.

Cependant, il est important de comprendre que tout programme informatique est également une donnée. Les programmes sont stockés sous forme de fichiers sur un disque dur, et peuvent être copiés, déplacés, supprimés et manipulés comme n'importe quelle autre donnée.

Il est important de comprendre cette propriété des programmes informatiques, car cela permet de les considérer comme des objets manipulables et manipulés par d'autres programmes. Par exemple, certains programmes peuvent prendre en entrée d'autres programmes, les exécuter et utiliser leur sortie pour réaliser d'autres tâches. Cette flexibilité dans la manipulation des programmes est essentielle pour le développement de nombreux types de logiciels, tels que les systèmes d'exploitation, les applications de bureau et les applications web.

Cette propriété est essentielle pour comprendre certains concepts clés en informatique, tels que la calculabilité et la décidabilité.

Rappels

Programme :
Au sens informatique, un programme est une implémentation d'un algorithme de traitement de données.

Donnée :
Une donnée est une information ou un ensemble d'informations pouvant être fournies à un programme ou traitées par un programme.

Mais en fait, tout n'est pas si simple, car un programme est aussi une donnée et c'est le fondement de la théorie de la calculabilité.

Calculabilité

La calculabilité fait référence à la possibilité de résoudre un problème à l'aide d'un algorithme. Un problème est calculable si un algorithme peut être écrit pour résoudre le problème de manière efficace. En revanche, un problème est considéré comme non calculable s'il n'y a pas d'algorithme qui peut le résoudre de manière générale pour toutes les instances du problème.

La calculabilité est une branche de l'informatique théorique qui s'intéresse à la question de savoir quelles tâches peuvent être réalisées par un ordinateur. Autrement dit, elle étudie les limites du calcul. Les premières recherches sur la calculabilité remontent aux années 1930, avec des travaux de mathématiciens tels que Kurt Gödel, Alan Turing et Alonzo Church.

La notion fondamentale de la calculabilité est celle de la fonction calculable. Une fonction est dite calculable si elle peut être réalisée par un ordinateur en suivant un algorithme fini. En d'autres termes, si pour chaque entrée donnée à la fonction, l'ordinateur peut renvoyer la réponse correcte en un temps fini.

En revanche, certaines fonctions ne sont pas calculables. Par exemple, il n'existe pas d'algorithme qui permette de déterminer si un programme donné va s'arrêter ou non (problème de l'arrêt). Cela signifie que certaines tâches sont fondamentalement impossibles à réaliser par un ordinateur, quel que soit le langage de programmation utilisé.

La thèse de Church

Une fonction est calculable si elle peut être programmée dans l’un ou l’autre des langages de programmation usuels.

Pour rappel, nous savons qu’il existe beaucoup de langages de programmation, comme JavaScript, C, Perl, Java, Fortran, Python, etc.

En résumé, la calculabilité est une discipline qui étudie les limites du calcul, c'est-à-dire les tâches qui peuvent ou ne peuvent pas être effectuées par un ordinateur en suivant un algorithme fini. Cette notion est étroitement liée à celle de décidabilité, qui permet de distinguer les problèmes pour lesquels il est possible ou non de trouver une solution en temps fini.

Décidabilité

La décidabilité est la branche de l'algorithmique qui s'intéresse à la question suivante :

• Peut-on déterminer, en un nombre fini d'étapes, si un problème est vrai ou faux quel que soit le contexte de départ ?

Exemples de problèmes décidables :

• Un nombre est premier : La réponse est soit 'vrai', soit 'faux' et un algorithme simple est de diviser ce nombre par les entiers inférieurs à lui même (nombre fini d'étapes).
• Un nombre est pair : La réponse est soit 'vrai', soit 'faux' et un algorithme simple est de regarde le reste de la division Euclidienne par 2 (nombre fini d'étapes).

La décidabilité est une notion fondamentale de l'informatique théorique, car elle permet de distinguer les problèmes pour lesquels il est possible ou non de trouver une solution en temps fini. Elle a des applications dans de nombreux domaines de l'informatique, tels que la vérification de programmes, la théorie de la complexité, la cryptographie, etc.

Théorème de la décidabilité

Il existe des problèmes non décidables

La problématique de la décidabilité est équivalente à celle de la calculabilité.

Pour déterminer si tout est ou non calculable, Church et Turing ont chacun recherché et trouvé l'existence d'un problème qu'il ne serait pas possible de résoudre par un algorithme : il s'agit du problème de l’arrêt.

Le problème de l'arrêt

Le problème de l'arrêt est une question fondamentale de la théorie de la calculabilité, qui montre les limites de ce qui est possible à calculer avec un ordinateur.

Le problème de l’arrêt décrit par Turing en 1936 s'énonce ainsi :
étant donné un algorithme A et une prenant en paramètre m, existe t-il un algorithme permettant de décider si A(m) s'arrête ou pas.

Il est important de comprendre que ce problème est indécidable, c'est-à-dire qu'il n'existe pas d'algorithme qui puisse répondre à cette question pour tous les programmes et toutes les entrées possibles. En d'autres termes, il est impossible de prédire avec certitude si un programme donné va s'arrêter ou non.

Pour comprendre pourquoi le problème de l'arrêt est indécidable, il faut se rappeler que les programmes informatiques sont des données, et que les ordinateurs sont des machines qui manipulent ces données en suivant des règles prédéfinies. Or, il est possible de construire des programmes qui s'exécutent en boucle infinie, sans jamais s'arrêter. Dans ce cas, il est impossible de prédire si le programme va s'arrêter ou non.

Voici un exemple concret pour illustrer le problème de l'arrêt :

Considérons le programme suivant en Python :

def countdown(n):
    if n == 0:
        return
    print(n)
    countdown(n-1)

Ce programme prend en entrée un entier n et affiche les nombres de n à 1 en ordre décroissant. Par exemple, si n vaut 5, le programme affichera les nombres 5, 4, 3, 2, 1.

Nous pouvons facilement prédire que le programme s'arrêtera pour toutes les entrées possibles, car il contient une condition de sortie qui permet à l'exécution de se terminer lorsqu'elle atteint 0.

Cependant, si nous modifions légèrement le programme comme suit :

def countdown(n):
    if n == 0:
        while True:
            pass
    print(n)
    countdown(n-1)

Maintenant, si n vaut 5, le programme affichera les nombres 5, 4, 3, 2, 1, mais ne s'arrêtera jamais. Cela est dû au fait que la condition de sortie a été remplacée par une boucle infinie.

Ainsi, pour ce programme modifié, il est impossible de prédire de manière générale si l'exécution va s'arrêter ou non, car il est possible que le programme soit coincé dans une boucle infinie, et donc il est impossible de déterminer si le programme s'arrêtera ou continuera indéfiniment. C'est pour cette raison que le problème de l'arrêt est indécidable pour ce type de programme.