Imaginons qu'un ordinateur révolutionnaire ait été inventé : un ordinateur dont chaque opération élémentaire s'exécute en un temps nul ; donc tout programme set termine après une durée nulle. De plus, tous les périphériques exécutent les opérations qui leur sont commandées instantanément, y-compris la mémoire qui de plus est d'une capacité illimitée. Sur cet ordinateur utopique, un programme d'échecs par example sera à même d'explorer l'arbre entier des coups possibles et trouvera donc infailliblement la meilleure suite de coups à jouer.
Mais, dans le cas d'un programme qui teste si un élément appartient à un ensemble, et si cet ensemble est tel que le meilleur test réalisable est un test qui ne s'arrête que si l'élément appartient à l'ensemble, que se passera-t-il ? Si l'élément appartient à l'ensemble, le programme stoppera instantanément ; mais si l'élément n'appartient pas à cet ensemble, le programme tournera indéfiniment, mais comme chaque opération élémentaire se fait en un temps nul, le programme tournera indéfiniment en un temps nul.
C'est à ce point que mon esprit s'embrouille, que je n'arrive plus à avancer.
La seule solution que je trouve est de faire stopper le temps.
Note : ce paradoxe est une réflection naive sur la nature des ensembles récursivement énumérables mais non récursifs. On peut le comparer à la confusion que chacun ressent la première fois qu'il (ou elle) tente de diviser zéro par zéro.