Introduction au modèle de turing et à la machine de Turing Universelle

L'expression informatique a aujourd'hui un sens très large. Cependant, dans ce cours, nous définissons l'expression comme « problèmes liés à l'ordinateur ». Ce chapitre essaie d'abord de découvrir ce qu'est un ordinateur, puis examine d'autres problèmes directement liés aux ordinateurs. Nous regardons d'abord le modèle de Turing comme une définition mathématique et philosophique du calcul. Nous montrons ensuite comment les ordinateurs d'aujourd'hui sont basés sur le modèle de von Neumann.

L'idée d'un dispositif de calcul universel a été décrite pour la première fois par Alan Turing en 1936. Il a proposé que tous les calculs puissent être effectués par un type spécial de machine, maintenant appelé machine de Turing. Bien que Turing ait présenté une description mathématique d'une telle machine, il était plus intéressé par la définition philosophique du calcul que par la construction de la machine réelle. Il a basé son modèle sur les actions que les gens effectuent lorsqu'ils sont impliqués dans le calcul. Il a résumé ces actions dans un modèle pour une machine informatique qui a vraiment changé le monde.

Processeurs de données

Avant d'aborder le modèle de Turing, nous définissons un ordinateur comme un processeur de données. En utilisant cette définition, un ordinateur agit comme une boîte noire qui accepte les données d'entrée, traite les données et crée les données de sortie. Bien que ce modèle puisse définir les fonctionnalités d'un ordinateur aujourd'hui, il est trop général. Dans ce modèle, une calculatrice de poche est aussi un ordinateur (ce qu'elle est, au sens littéral).

Un autre problème avec ce modèle est qu'il ne spécifie pas le type de traitement ou si plusieurs types de traitement sont possibles. En d'autres termes, il n'est pas clair combien de types ou d'ensembles d'opérations une machine basée sur ce modèle peut effectuer. S'agit-il d'une machine à usage spécifique ou d'une machine à usage général ?

Ce modèle pourrait représenter un ordinateur (ou un processeur) à usage spécifique, conçu pour effectuer une seule tâche, comme le contrôle de la température d'un bâtiment ou le contrôle de la consommation de carburant d'une voiture. Cependant, les ordinateurs, tels que le terme est utilisé aujourd'hui, sont des machines polyvalentes. Ils peuvent effectuer de nombreux types de tâches différentes. Cela implique que nous devons changer ce modèle en modèle de Turing pour pouvoir refléter les ordinateurs réels d'aujourd'hui.

Processeurs de données programmables

Le modèle de Turing est un meilleur modèle pour un ordinateur à usage général. Ce modèle ajoute un élément supplémentaire à la machine informatique spécifique : le programme. Un programme est un ensemble d'instructions qui indique à l'ordinateur ce qu'il doit faire avec les données. La figure ci-dessous montre le modèle de Turing.

Dans le modèle de Turing, les données de sortie dépendent de la combinaison de deux facteurs : les données d'entrée et le programme. Avec les mêmes données d'entrée, nous pouvons générer différentes sorties si nous modifions le programme. De même, avec le même programme, nous pouvons générer différentes sorties si nous modifions les données d'entrée. Enfin, si les données d'entrée et le programme restent les mêmes, la sortie doit être la même. Voyons trois cas.

Même programme, données d'entrée différentes

La figure ci-dessous montre le même programme de tri avec des données d'entrée différentes. Bien que le programme soit le même, les sorties sont différentes, car différentes données d'entrée sont traitées.

Mêmes données d'entrée, programmes différents

La figure ci-dessous montre les mêmes données d'entrée avec différents programmes. Chaque programme oblige l'ordinateur à effectuer différentes opérations sur les données d'entrée. Le premier programme trie les données, le second ajoute les données et le troisième trouve le plus petit nombre.

Mêmes données d'entrée, même programme

Nous attendons le même résultat à chaque fois si les données d'entrée et le programme sont les mêmes, bien sûr. En d'autres termes, lorsque le même programme est exécuté avec les mêmes données d'entrée, nous attendons la même sortie.

La machine de Turing Universelle

Une machine de Turing universelle, est une machine qui peut faire n'importe quel calcul si le programme approprié est fourni, était la première description d'un ordinateur moderne. On peut prouver qu'un ordinateur très puissant et une machine de Turing universelle peuvent calculer la même chose. Nous n'avons qu'à fournir les données et le programme - la description de la façon de faire le calcul - à l'une ou l'autre machine. En fait, une machine de Turing universelle est capable de calculer tout ce qui est calculable.