Autres modèles de création d'algorithme
Nous ne rentrerons pas dans les détails ici, nous voulons juste montrer que l'on peut très bien écrire des algorithmes en utilisant autre chose que du pseudo-code. En revanche tous les modèles que nous verrons ne peuvent pas coder plus de choses, ils permettent juste d'écrire différemment les mêmes algorithmes.
Les algorithmes écrit sous la forme de pseudo-code sont équivalents (on le verra) aux algorithmes écrits grâce à une machine de Turing. Les modèles équivalents sont alors dit Turing complet :
définition
Un système est dit Turing complet s'il permet de faire tout ce qu'un pseudo-code peut faire.
Avoir un modèle Turing Complet nous assure, en suivant la thèse de Church-Turing, que ce modèle peut calculer tous les algorithmes.
Lambda calcul
Le lambda calcul est une autre forme d'écriture équivalent au pseudo-code. On doit ce modèle à Church, qui était le directeur de thèse de Turing. C'est une version bien plus matheuse de l'algorithmie puisqu'elle ne s'intéresse qu'aux fonctions et ne parle jamais d'algorithme.
On peut cependant coder en lambda calcul, c'est ce qu'on appelle la programmation fonctionnelle et elle est possible avec des langages comme le Haskell (il en existe d'autres, comme le Ocaml par exemple (n')utilisé (qu')en prépa).
Pour apprendre Haskell et les langages fonctionnels :
Cette façon de programmer est très liée aux types et a permis quelques avancées dans la vérification automatique des types.
Automates cellulaires
La plupart des automates cellulaires sont Turing-complet. C'est le cas du célèbre jeu de la vie, mais aussi d'automates bien plus simple :
L'exemple de système Turing complet le plus simple que je connaisse est l'automate uni-dimensionnel respectant la règle 110.
Jetez-y un coup d'œil, c'est assez bluffant.
Langages exotiques
Si la plupart des langages informatiques sont clairement Turing complet, il existe des langages bizarres, nommé langages de programmation exotiques, qui sont aussi Turing complet. Ces langages tendent à être minimalistes et cherchent à posséder soit le nombre minimal d'instruction, comme le célèbre brainfuck, ou à être marrant, comme le Piet dont le but est de créer des programmes sous la forme d'un tableau de Piet Mondrian.
Autres trucs
Ne nombreuses applications ou jeux sont Turing-complet par inadvertence. Par exemple :