Existe-t-il une définition claire de «calculable» pour les modèles de calcul qui ne sont pas complets?

Il s'agit d'une suite d'une autre question ici , et j'espère que ce n'est pas trop philosophique. Comme Raphael l'a souligné dans un commentaire sur ma question précédente, je n'ai pas vraiment la définition de "calculable", mais selon certains articles que j'ai lus, la définition n'est pas vraiment claire quand il s'agit de modèles de calcul plus faibles que Turing machines en raison de l'encodage de l'entrée et de la sortie.

La définition typique de turing calculable est la suivante:

Définition 1: Une fonction $f : \mathbb{N}^k \to \mathbb{N}$ est appelée turing calculable ssi il existe une machine de turing $M$ qui calcule utilisant un codage approprié des nombres naturels sous forme de chaînes.$f$

Les définitions diffèrent dans ce qui est exactement un encodage approprié est, mais la plupart se réfèrent à un codage binaire , le codage unaire ou le codage décimal comme un codage fixe et approprié. Il est également possible de montrer que la fixation d'un codage est nécessaire pour la définition de la calculabilité de Turing. Mais qu'est-ce qui rend, disons, l'encodage binaire des nombres naturels si spécial que nous pouvons l'axiomatiser comme l'encodage approprié? Probablement parce qu'il correspond à la notion intuitive de ce que signifie la calculabilité par coïncidence .

Et si nous regardions des modèles de calcul plus faibles que les machines de Turing? Par exemple, considérons l'ensemble des machines de turing "paralysées" avec l'alphabet $M_c$ qui ne peut se déplacer que vers la droite, et une définition deturing paralysé calculablequi est cohérente avec celle de la calculabilité de turing:$\{0,1\}$

Définition 2: Une fonction est appelé infirme turing calculable ou calculable en M c ssi il existe une machine de Turing infirme$f : \mathbb{N}^k \to \mathbb{N}$$M_c$ qui calcule f en utilisant un codage approprié des nombres naturels sous formechaîne.$M$$f$

Si nous définissons "codage approprié" comme "codage binaire", alors la fonction n'est pas calculable dans M c . Si nous axiomatisons "codage approprié" comme "codage unaire", alors f est calculable dans M c . Cela semble gênant étant donné que tout le monde peut corriger à volonté l'un des infiniment nombreux encodages intuitifs. Il doit être clair si un modèle de calcul peut calculer $f : \mathbb{N} \to \mathbb{N}, n \mapsto n+1$$M_c$$f$ $M_c$$f$ ou pas sans se référer à un encodage spécifique - du moins, je n'ai jamais vu personne mentionner quel encodage est utilisé pour déclarer que "les programmes en boucle sont plus faibles que les machines de Turing".

Après cette introduction, je peux enfin formuler ma question: comment définir des "encodages appropriés" et "calculabilité" pour des modèles de calcul arbitraires qui ne coïncident pas avec la notion intuitive de calculabilité? Est-ce possible dans le cadre de la calculabilité de Turing?

Edit: j'ai raccourci l'introduction, cela n'a pas ajouté à la question.

Un fait fondamental qui vous manque ici est que tous les encodages que vous mentionnez sont équivalents du point de vue de la calculabilité: il existe une fonction calculable mappant l'encodage binaire d'un nombre à son encodage unaire, ou vice versa. Par conséquent, pour définir la calculabilité, peu importe lequel de ces encodages vous choisissez pour les nombres. Corrigez simplement votre encodage préféré.

La calculabilité est au cœur d'une propriété des fonctions de chaîne $f\colon \Sigma^* \to \Sigma^*$ . Lorsque vous définissez la calculabilité dans tout autre domaine, vous devez corriger un encodage. En pratique, tous les encodages "raisonnables" sont équivalents au sens du paragraphe précédent, donc l'encodage exact n'a pas d'importance.

Le codage importe cependant dans les modèles de calcul restreints. Pour prendre un exemple extrême, supposons que vous envisagiez des machines de Turing limitées dans le temps: supposons que vous vouliez que votre machine se termine dans le temps pour certains c , où n est la longueur de l'entrée (sous forme de chaîne). Nous ne pouvons plus basculer entre le codage binaire et le codage unaire, car le codage binaire est beaucoup plus compact. Lorsque nous parlons d'une fonction polynomiale calculable en temps d' entiers , nous spécifions que les entiers sont codés en binaire. Même ceci est un choix quelque peu arbitraire, car le codage décimal conduirait à la même notion de calcul de temps polynomial.$O(n^c)$$c$$n$

Donc, pour répondre à votre question - l'encodage est spécifié dans le cadre de la définition du modèle restreint.

Tout d'abord, vous ne pouvez pas définir un "codage approprié" comme des chaînes binaires ou tout autre codage. En effet, vous perdriez trop de modèles de calcul, car différents modèles de calcul peuvent avoir des modèles d'entrée et de sortie très différents. En d'autres termes, ils ne peuvent pas "parler" de chaînes.

Par exemple, les termes du calcul lambda non typé sont soit des variables, soit l'application d'un terme à un autre, soit une abstraction d'un terme lambda. L'entrée et la sortie sont des termes, des chaînes arbitraires. Pourtant, le calcul lambda non typé est Turing-complet car il existe un "codage approprié" qui code les nombres naturels en termes lambda d'une certaine forme, et sous ce codage pour chaque fonction calculable, il existe un terme lambda qui le calcule.

Vous pouvez formaliser un «codage approprié» si vous fixez les machines Turing comme modèle de calcul de référence, puis exiger que le codage et le décodage depuis et vers les chaînes binaires soient effectués par une machine Turing qui s'arrête toujours. Par exemple, une machine de Turing serait capable de traduire un nombre naturel sous forme de chaîne binaire en un terme Lambda qui exprime ce nombre, de simuler la réduction du calcul lambda et de traduire le résultat en une chaîne binaire.

Pour des modèles de calcul plus simples, je m'attendrais à la même approche: prendre un modèle de calcul de référence et fixer un codage des nombres naturels, puis s'assurer que le codage et le décodage sont effectués par des instances de ce modèle simple. Comme vous l'avez noté, pour les machines de Turing paralysées, l'utilisation de nombres codés unaires et binaires ne donnerait pas un modèle de calcul équivalent.