Il me semble bien que dans Les petits cailloux de Bruno Poizat, il est dit qu'un problème en calculabilité est juste un ensemble d'entiers naturels, dans une idéologie (ou est-ce une téléologie ?) qui veut que ce problème soit décidé.

C'est un peu plus subtil que cela. La plupart des problèmes de décision sont décrits non pas en termes d'entiers naturels, mais de structures finies comme des graphes, des automates, des formules, qui sont codées par des entiers naturels ; autrement dit l'ensemble d'entiers naturels dont il est question dépend du codage choisi.

Le codage est laissé implicite parce que, la plupart du temps, celui-ci n'a aucune importance du point de vue des propriétés de calculabilité et de complexité tant qu'il est raisonnable. Par exemple, un codage raisonnable d'un graphe est sa matrice d'adjacence, et pour encoder celle-ci en entiers naturels on peut utiliser un codage « raisonnable » des tableaux d'entiers, lui-même basé sur un codage « raisonnable » des couples d'entiers.

En revanche, du point de vue de la théorie de la complexité, est « déraisonnable » un codage qui occuperait une taille bien supérieure à celle d'un codage « raisonnable », par exemple un codage du graphe par la matrice d'adjacence suivi d'un nombre de zéros exponentiel en la taille du graphe. En effet, un tel codage fait artificiellement baisser la complexité des algorithmes proposés, puisque celle-ci est mesurée par rapport à la taille de l'entrée : si cette taille est artificiellement enflée, l'algorithme apparaît moins cher (c'est un peu comme la malhonnêteté d'une entreprise qui se prétendrait peu chère car avec un coût horaire un peu plus faible que ses concurrences, mais qui gonflerait considérablement le nombre d'heures nécessaires).

J'ai employé le mot « malhonnête », et effectivement, certains peuvent jouer sur les définitions pour présenter leurs travaux sous un jour meilleur (et notamment planquer des exponentielles sous le tapis, ce qui m'inciterait presque à raconter la blague sur l'exponentielle qui va dans un bar). Un grand classique : écrire les entiers en unaire et non en binaire (c'est-à-dire écrire IIIIIIIIIIIIIIII, soit 15 caractères, au lieu de 15, soit 2 caractères), ou, dans le même genre, formuler la complexité en fonction du nombre d'états et non du nombre de bits qui les encodent.

On peut également proposer des codages malhonnêtes où l'entrée devrait, sous peine d'être refusée comme mal formée, contenir tout ou partie de la solution du problème.

Certains codages, en revanche, rendent plus dur la tâche de l'algorithme de décision, par exemple les codages implicites ou succincts de graphes où la matrice d'adjacence est représentée par une formule logique prenant en entrée les numéros (en binaire) des sommets concernés, et produisant en sortie un booléen indiquant si oui ou non l'arête est présente. De tels codages, le plus souvent, font passer un problème de NP-complet à NEXPTIME-complet (voir Papadimitrou & Yannakakis, 1986). Là encore, par défaut on considère n'est pas dans un tel cas et qu'on utilise un encodage « explicite ».

Nous en concluons donc que les définitions usuelles de calculabilité et complexité font appel à des notions de bon sens et d'honnêteté tant chez l'auteur que chez le lecteur ! Surprenant pour des mathématiques, que l'on imagine déconnectées des intérêts humains...