Langage de programmation impératif
  1. Langage impératif minimaliste (Brainfuck)
  2. Opération de comptage et de somme
  3. Le calcul parallèle doit être possible
  4. La taille des données et des programmes ne doivent pas être limitée
  5. Les programmes primitifs récurcifs

La machine de Turing universelle, tel un fidel interpréteur, exécute n'importe quel programme sur n'importe quelles données. Ces programmes sont écrits dans un langage. Le langage de programmation décrit les possibilités expressive de la machine. Nous laissons donc la machine de coté pour ne s'intéresser qu'à son langage de programmation. Chaque langage de programmation a un domaine de fonctions calculables, constitué par l'ensemble des fonctions mathématiques programmable par ce langage, et a un domaine d'algorithmes, plus fin, constitué par l'ensemble des algorithmes avec leur différentes complexités permettant de calculer ces fonctions.

On sépare les langages de programmation en deux types de langage, les langages impératifs et les langages fonctionnels. Les langages impératifs sont des suites d'instructions qui agissent par effet de bord. C'est à dire qu'une instruction va modifier des données extérieures à l'instruction, modifiant la mémoire de la machine et son état. Les langages fonctionnels sont au contraire sans effet de bord, ou plus exactement, à effet de bord réduit au minimum c'est à dire au seul compteur d'instruction et à la mémoire tampon résultat de la fonction. Ils se présentent comme une combinaison d'opérateurs, et sont identiques aux langages associés à une structure mathématique.

1) Langage impératifs minimaliste (Brainfuck).

Nous proposons un langage minimaliste similaire au Brainfuck de Urban Muller. Il est d'ailleurs regrettable que M. Muller ait donné un nom aussi vulgaire à son langage qui traite d'une question aussi fondamentale qu'est la source de l'algorithmique. Ce langage est composé de 7 instructions, mises sous forme d'avantage mathématique, reprenant de façon analogue le fonctionnement d'une machine de Turing, mais utilisant des entiers de taille illimitée à la place des caractères sur la bande. L'état de la machine est donné par :

  1. Une suite d'entier modifiable (U0,U1,U2,...Uk,...) appelée mémoire périphérique de taille illimitée, jouant le rôle du ruban.
  2. Un entier P appelé pointeur, jouant le rôle du curseur désignant une case du ruban.
  3. Une suite d'instruction fixées (V0,V1,V2,...,Vn,...) appelée programme, jouant le rôle de l'automate.
  4. Un entier C appelé compteur d'instruction, jouant un rôle miroir du curseur mais pour désigner l'état de l'automate.

Au début C = P = 0, et le programme est (V0,V1,V2,...,Vn,0,0,0...), et les données initiales sont (U0,U1,U2,...,Uk,0,0,0....). A chaque étape, la machine exécute l'instruction VC et incrémente C. La machine s'arrête sur l'instruction fin (L'instruction fin est représenté par le code 0). Le résultat est alors égale à la valeur de U0. Notre langage de programmation minimaliste comporte 7 instructions : L = {>, <, +, -, [, ],.}:

>
P = P + 1
Incrémentation du pointeur
<
P = max(0, P - 1)
Décrémentation du pointeur
+
Up = Up + 1
Incrémentation avec adressage indirecte
-
Up = max(0, Up - 1)
Décrémentation avec adressage indirecte
[
Si Up = 0 sauter les instructions jusqu'au "]" correspondant.
Boucle While et condition avec adressage indirecte
]
Retourner à l'instruction "[" correspondante.
Retour de boucle
.
Fin Fin

Les fonctions ayant comme résultat plusieurs valeurs se décomposent en autant de fonction ayant comme résultat une seule valeur. C'est pourquoi on ne s'intéresse qu'aux seules fonctions d'arité k de la forme N^k-->N{}. La fonction f est calculable ssi il existe un programme écrit dans le langage L = {>, <, +, -, [, ],.} tel que quel que soit x N^k, la machine donne un résultat égal à f(x), et ne s'arrête jamais lorsque f(x) = , l'infini de Turing. Et elle est totalement calculable lorsque de plus elle n'est jamais égale à l'infini de Turing.

Par exemple, le programme correspondant à l'addition (x,y) --> x+y est le suivant : [->+<]>[-<+>]. Il est scindé en deux parties, l'une ajoutant U0 dans U1, [->+<], et l'autre recopiant U1 dans U0, >[-<+>].

2) Opération de comptage et de somme.

Compter avec des batons ||||.... est l'algorithme le plus trivial que l'on peut concevoir. Mais précisons en quoi consiste exactement cette action : Cela consiste à transformer un signale composé de 0 et de 1, où chaque 1 correspond à un batton, et chaque 0 à une absence de batton, en la mémorisation du nombre de 1, c'est à dire qu'il faut mémoriser la somme. Il existe un moyen encore plus trivial de compter qui consiste simplement a enregistrer le signal sans l'altérer. La complexité est alors égale à la duré du signal, qui est est égale au nombre de 1 augmenté du nombre de 0. C'est la mémorisation des zéro qui s'avère ici gaspilleuse de complexité. Le comptage consiste à ne mémoriser que les 1. La somme de x battons effectuée par comptage a une complexité égale à x. Et la somme effectué chiffre à chiffre sur un entier x dans une base b, a une complexité égale au nombre de chiffre, c'est à dire égale à log(x)/log(b), elle consiste seulement à mémoriser chaque chiffre et il s'agit bien d'une somme puisque nous prenons connaissance du chiffre des unités, puis nous prenons connaissance du chiffre des dizaines (cas où b=10), et conceptuellement nous les sommons même si dans les fait nous ne faisons que mémoriser ces deux chiffres, et ainsi de suite...

Le calcul de la sommes de deux entiers en base b utilise une retenue qui est transmise au chiffre de poid juste au dessus. La sommation de deux chiffres consiste à reconnaître b*b cas possibles. Le processeur d'un ordinateur d'architecture 32 bits, somme 2 mots de 32 bits (des entiers inferieurs à 2^32) en une seul opération de base par le biais d'une opération cablée, et non d'une table d'addition de chiffres car cette table serait trop grande, 2^64 lignes. L'opération cablée est en faite une suite de 32 opérations d'addition de chiffre binaires avec retenue effectué en parallèle ce qui permet de réduire la complexité. La complexité de la somme chiffre à chiffre en base b, est égale au nombres de chiffre (log(x)/log(b)), à condition que le moyen de calculer la somme de deux chiffres soit aussi rapide que pour effectuer une opération élémentaire.

Si nous voulons construire des algorithmes de complexité moindre, nous devrons utiliser une représentation des entiers en base b, rendant superflux la définition des entiers illimités du langage précédent. On se raproche donc du Brainfuck. Et il est nécessaire d'ajouter des opérations supplémentaires qui manquent pour redonner au langage de programmation son domaine d'algorithme. Les opérations ajoutées ne sont pas nouvelle mais regroupe un grand nombre d'opération de base, à l'image des opérations cablées qui sont exécutées en parallèles.

3) Le calcul parallèle doit être possible

Pour permettre la programmation de calcules parallèles, Il est nécessaire d'ajouter une opération d'un nouveau type, qu'est la création d'un processus fils, à l'image des système informatique UNIX multiprocesseur. L'algorithme peut ainsi se dédoubler et créer autant d'acteurs supplémentaires qu'il le souhaite effectuant des calcules en paralèlles et réduisant ainsi la complexité d'un ordre majeur (passage d'une complexité en x en une complexité en log(x)).

4) La taille des données et des programmes ne doivent pas être limitée

Les briques élémentaires étant limitées (à 2^32 par exemple correspondant au mots de 32 bits, ou à un caractère tel que le définie dans le Brainfuck), seul le ruban illimité permet l'entrée d'une données non bornées en taille.

Et pour permettre d'entrée une liste de données de tailles non bornées, on simmule autant de rubans que nécessaire. On simule n rubans comme suit : le déplacement d'une case sur la droite d'un ruban spécifique correspond au déplacement de n cases sur le ruban global.

Il est alors nécessaire d'ajouter au programme, des méta données, que sont le debut du programme non borné en taille, l'endroit où se situe la donnée d'entrée non bornée en taille et l'endroit ou se situe le résultat non borné en taille.

5) Les programmes primitifs récurcifs

Les instructions de boucles sont emboités comme un jeux de parenthèse. Il ne peut y avoir de boucle croisée. Le sense de l'instruction "]" est le suivant :

Retourner à l'instruction "[" correspondante de même niveau, et s'il n'y en à pas, faite fin.

Si on modifie l'instruction "[" qui correspond à :

Si Up = 0 sauter les instructions jusqu'au "]" correspondant, et s'il n'y en à pas, faite fin.

par :

Répéter les instructions comprises entre les deux crochets [...] de même niveau, autant de fois qu'indiqué par la valeur initialement lue Up lors de l'entré dans la boucle répétitive, et s'il n'y a pas d'instruction fermante "]" et si Up = 0 alors faite fin.

Cela revient en programmation à n'utiliser que les boucles for, sans diminuer l'indexe ni angmenter la borne au cours de la boucle for, et à ne pas utiliser les boucles while ou repeat until. Un tel programme est dit primmitif récurcif.

Alors le langage de programmation est diminué, et ne permet de programmer que les fonctions primitives récursives. Ces fonctions à l'évidence se terminent toujours en un temps fini et forment un sous-ensemble stricte de l'ensemble des fonctions totalement calculables.

6) Les données

L'approche intuitionniste remplace les ensembles énumérables par des structures constructibles, et n'utilise pas la théorie des ensembles qu'elle peut même réfuter en partie. Cette approche met en exergue les trois pans du langage que sont ; le langage programmatif pour l'énumérateur, le langage de propriété pour la théorie, et le langage de donné pour l'élément.

La structure énumérante ainsi que le mécanisme d'unification des termes, qui sont tous deux de complexité linéaire, constituent la clef de voûte liant les trois pans du langage.

Notre euristique préconise de rester au barycentre des 3 pans du langage que constitue la donné, le programme et la théorie, chacun de ces pans dévoilant un mystère inexplicable sans la présence des deux autres.

La représentation binaire des entiers compris entre 0 et 2n-1 constitue une représentation totalement dense, c'est à dire une représentation qui occupe la pus petite mémoire possible constituée ici de n bits. Considérons la structure <a, f(.)>. Cette structure représente les entiers positifs ou nuls. On peut définir les éléments suivants :

0 = a
1 = f(a)
2 = f(f(a))
3 = f(f(f(a)))
4 = f(f(f(f(a))))

Cette structure est appelée la représentation des entiers sous forme de bâtons. On cherche à définir deux fonctions f0 et f1 intuitivement comme suit :

f0 : x --> 2*x
f1 : x --> 2*x + 1

où les entiers x, 2*x, 2*x+1 correspondent au nombre de bâtons, c'est à dire à des compositions de n fonctions f à la suite, le tout appliqué à a. Mais la définition exacte de la fonctions f0 doit être un programme. La difficulté réside dans le fait que l'on n'a pas définie précisément le langage de programmation avec lequel on doit fair le programmme. Mais déjà on peut définire la fonction f1 à partir de f0 comme suit :

f1 : x--> f(f0(x))

La fonction f0 appliquée aux premier éléments donnent quelques indications :

a --> a
f(a) --> f(f(a))
f(f(a)) --> f(f(f(f(a))))

Le programme utilise une pile. A chaque fois qu'il compte un batôn sur l'entré, il ajoute deux batons sur la sortie. Comment pouvons-nous programmer cela ?. Qu'elles sont les opérations de bases qui doivent être implémentées ?.

....