Turing complete ça veut dire qu'on peut faire les même chose dedans, mais pas forcément avec la même efficacité.
Brainfuck est Turing complete (me semble-t-il), et pourtant il sera moins efficace algorithmiquement (par exemple mettre un nombre N dans une case mémoire a une complexité plus grande que O(1), ce qui n'est pas le cas avec des nombres pas trop grands dans la plupart des autres langages).
Le papier qui indique une borne inférieure de complexité moins intéressante avec un algo fonctionnel pur qu'un algo impératif tient donc toujours.
Évidemment, ça ne concerne pas Haskell, qui n'est pas un langage fonctionnel pur, comme tu dis :p
(par contre je suis pas sûr que le hack de l'UnsafePerformIO suffise pour échapper à la preuve de l'autre, mais on sait jamais ce qu'on peut faire avec ces trucs tordus...)
[^] # Re: Beurk, un langage impératif
Posté par gasche . En réponse à la dépêche OCaml 3.10.0 est sorti. Évalué à 1.
Brainfuck est Turing complete (me semble-t-il), et pourtant il sera moins efficace algorithmiquement (par exemple mettre un nombre N dans une case mémoire a une complexité plus grande que O(1), ce qui n'est pas le cas avec des nombres pas trop grands dans la plupart des autres langages).
Le papier qui indique une borne inférieure de complexité moins intéressante avec un algo fonctionnel pur qu'un algo impératif tient donc toujours.
Évidemment, ça ne concerne pas Haskell, qui n'est pas un langage fonctionnel pur, comme tu dis :p
(par contre je suis pas sûr que le hack de l'UnsafePerformIO suffise pour échapper à la preuve de l'autre, mais on sait jamais ce qu'on peut faire avec ces trucs tordus...)