Il me semble que la machine de Turing est aussi "numérique" qu'on peut l'être, et elle a un ruban infini. Chaque position du ruban a une valeur prise dans un ensemble fini, et il y a un ensemble fini de positions du ruban qui ont été modifiées à tout moment, mais l'ensemble des états mémoires possibles (les état de ruban possibles) a un cardinal infini; même la position sur le ruban par rapport au point de départ n'appartient pas à un ensemble fini.
D'un autre coté N est infini. Ton argument sur R devrait donc s'appliquer aussi bien à N.
Une machine de Turing peut effectuer des calculs utilisant des valeurs quelconques dans N. C'est ce qui rend le problème de l'arrêt indécidable.
Au contraire sur une machine avec ensemble d'état fini le problème de l'arrêt est décidable! (Après tous les problèmes décidables ne sont pas pratiquement calculables.)
Peut-être voulais-tu utiliser un argument diagonal, ou plus directement de cardinalité?