Existe-t-il une notion de calculabilité sur des ensembles autres que les nombres naturels?

Existe-t-il une notion de calculabilité sur des ensembles autres que les nombres naturels? Par souci d'argument, disons sur les ensembles qui se bijectent avec .$S$$\mathbb{N}$

Il est tentant de dire "oui, ce sont ces fonctions de la forme où est toute bijection et est toute fonction calculable ". Je suis prudent avec cette définition pour deux raisons. g N → S f N → $g \circ f \circ g^{-1}$$g$$\mathbb{N} \to S$$f$$\mathbb{N} \to \mathbb{N}$

1. Il privilégie sur les autres ensembles dénombrables. Pourquoi spécial lorsqu'il s'agit de définir la calculabilité? J'aimerais une définition "sans coordonnées" de la calculabilité sans référence à un ensemble privilégié de la même manière. Je voudrais une définition "sans coordonnées" d'un concept d'algèbre linéaire sans référence à une base privilégiée.$\mathbb{N}$$\mathbb{N}$

2. Cela soulève des questions sur le choix de . Je soupçonne qu'il peut être possible de trouver des contradictions par des choix particulièrement pathologiques de et . Par exemple, si je choisis et une bijection non calculable, est-ce vraiment le cas que est calculable pour tout calculable ?S g S = N g g ∘ f ∘ g - 1$g$$S$$g$$S = \mathbb{N}$$g$$g \circ f \circ g^{-1}$$f$

   Il est tentant d'exiger dans la définition que soit calculable, mais malheureusement, cela pose la question.$g$

Existe-t-il un moyen général de décrire la calculabilité sur des ensembles dénombrables autres que ?$\mathbb{N}$

Cette question n'est pas au niveau de la recherche, mais comme elle reçoit des réponses, je voudrais offrir une réponse qui pourrait en fait éclaircir un peu les choses et fournir des références.

Il existe tout un domaine de l'informatique théorique qui étudie la calculabilité en analyse, en algèbre et en topologie. La notion de calculabilité pour les nombres réels est d'une importance capitale. En fait, le document original de Turing sur les machines de Turing commence par la phrase suivante:

Les nombres "calculables" peuvent être décrits brièvement comme les nombres réels dont les expressions sous forme décimale sont calculables par des moyens finis.

Parfois, il vaut mieux retourner à la source.

Il existe plusieurs façons de configurer la calculabilité sur des ensembles généraux, dont l'une des plus générales est la théorie de la réalisabilité . L'idée de la théorie de la réalisabilité remonte à l'article de Kleene On the Interpretation of Intuitionistic Number Theory de 1945, mais a depuis été généralisée et développée en une mini-branche de calculabilité, avec un bon mélange de théorie des catégories, voir par exemple le livre de Jaap van Oosten "Réalisabilité: une introduction à son côté catégorique" (Studies in Logic and the Foundations of Mathematics, vol. 152, Elsevier, 2008).

Permettez-moi de décrire brièvement l'idée de réalisabilité, et de discuter plus tard de votre exigence de "libre coordination". Commencez avec un modèle de calcul, comme les machines de Turing, le -calculus, un langage de programmation ou toute autre algèbre combinatoire partielle (vous pouvez même prendre certains espaces topologiques pour être des "modèles de calcul", ce genre de choses est général ). Pour le concret, considérons les machines de Turing. Nous codons les machines de Turing par des nombres naturels, mais notez que j'aurais pu prendre un autre modèle de calcul, vous ne devez donc pas supposer que l'utilisation de$\lambda$N λ$\mathbb{N}$est en aucun cas essentiel ici. (D'autres possibilités incluent: le jeu de nombres naturels, les séquences infinies de nombres naturels, la syntaxe du -calculus non typé , certaines catégories de jeux, etc.)$\lambda$

Une structure de calculabilité sur un ensemble est donnée par une relation entre et , appelée la relation de réalisabilité , telle que pour chaque il n'y a telle que . Nous appelons de telles structures des assemblées . Cette définition correspond directement à l'idée intuitive que certains morceau de données respresents, ou réalise un , un élément . (Par exemple, certaines séquences de bits représentent des listes finies de paires de chaînes de caractères.)$X$$\Vdash_X$$\mathbb{N}$$X$$x \in X$$n \in \mathbb{N}$$n \Vdash_X x$$n$$x \in X$

Etant donné deux assemblages et , une carte est réalisée (ou "calculable") s'il existe une machine de Turing , telle que, chaque fois que puis termine et . Encore une fois, il s'agit d'une translittération directe de ce que signifie informellement «programmer» une fonction abstraite : la machine de Turing correspondante fait pour représenter les données tout ce que fait aux éléments correspondants.$(X, {\Vdash_X})$$(Y, {\Vdash_Y})$$f : X \to Y$T n ⊩ X x T ( n ) T ( n ) ⊩ Y f ( x ) f f$T$$n \Vdash_X x$$T(n)$$T(n) \Vdash_Y f(x)$$f$$f$

Les assemblages peuvent être étendus à un topos de réalisabilité . Un topos est un modèle de mathématiques intuitionnistes d'ordre supérieur. Cela nous indique que chaque topos de réalisabilité (il y en a un pour chaque modèle de calcul) contient beaucoup d'objets intéressants. Par exemple, il contient un objet de nombres réels, ce qui nous donne donc une calculabilité sur des réels. Mais il contient également de nombreux autres objets, tels que les espaces de Hilbert, les espaces de Banach, les espaces de cartes lisses, etc. Vous avez demandé une autre structure calculable, mais vous avez obtenu quelque chose de bien meilleur: des mondes mathématiques entiers de calculabilité.

Étant donné que la théorie des catégories et les topos peuvent être effrayants et nécessitent une certaine maîtrise technique de la théorie de la calculabilité, de la théorie des catégories et de la logique, nous pourrions également travailler dans un seul topos concret, mais nous exprimons tout de manière concrète et non abstraite. Un monde de calcul particulièrement bon découle de la réalisabilité de la fonction de Kleene et porte le nom d' analyse calculable .

Permettez-moi de commenter l'exigence "sans coordonnées":

• La commutation entre les modèles de calcul donne différents types de mondes calculables. C'est un peu comme basculer entre différents champs donnant différents types d'algèbre linéaire.

• Un ensemble peut être équipé de nombreuses structures de calcul , tout comme un ensemble de vecteurs a de nombreuses bases. Cependant, alors que toutes les bases sont équivalentes, toutes les structures de calculabilité sur sont pas équivalentes par calcul.$X$⊩ X X$\Vdash_X$$X$

• Si nous travaillons concrètement avec des structures de calculabilité , c'est un peu comme travailler avec des matrices en algèbre linéaire. Cela peut être très utile, mais n'est pas abstrait.$(X, {\Vdash_X})$

• Pour travailler de manière "sans coordonnées", nous travaillons de manière réalisable pour exploiter et exploiter la puissance de la théorie des catégories (oui, c'est un cliché mais ça marche).

• Nous pouvons même travailler de façon «libre du monde»: développer les mathématiques dans une logique intuitionniste, puis interpréter les résultats en termes de réalisabilité.

Les deux articles ci-dessous développent une notion de calculabilité pour les ensembles arbitraires. Fait intéressant, même une notion de théorie de la complexité peut être définie pour ce modèle de calcul.

Cobham Recursive Set Functions and Weak Set Theories Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen.

Récursion bornée par sous-ensemble et modèle de circuit pour les fonctions d'ensemble récursif de Cobham Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen.

Il existe un concept de complexité et de calcul sur les réels. Un manuel que je voudrais vous diriger est: https://www.amazon.com/Complexity-Real-Computation-Lenore-Blum/dp/0387982817

Je connais un laboratoire qui étudie cela spécifiquement: https://complexity.kaist.ac.kr/

Ceci est similaire à la façon dont nous définissons la calculabilité en termes de machines Turing, puis oublions rapidement les machines Turing. Puisqu'il s'avère qu'une machine de Turing est aussi bonne définition qu'une autre, nous l'utilisons comme point d'ancrage pour toute une classe d'équivalence de modèles, et nous nous retrouvons avec la même classe, quel que soit l'élément à partir duquel nous la générons. Fondamentalement, c'est la thèse de Church-Turing et elle définit l'ensemble de chaînes de bits calculables.

De même, pour définir la calculabilité sur un autre ensemble , nous jetons l' ancre avec une fonction partielle particulier de chaînes de bits à . En fait, peu importe si cette fonction est une bijection ou une injection ou tout autre type de fonction (pour un cas où nous ne voulons pas vraiment que ce soit une injection, considérons un groupe défini par sa présentation où nous n'avons pas une représentation unique pour ses éléments). Il ne doit même pas être une surjection si nous permettons que les ensembles singleton puissent être non calculables. En composant cette fonction avec toute bijection calculable de chaînes de bits en chaînes de bits (un concept déjà défini), nous obtenons une définition de la calculabilité pourS S $S$$S$$S$c'est invariant par rapport à la fonction que nous avons choisie à l'origine (tant que nous avons choisi quelque chose de raisonnable). Autrement dit, une thèse de CT pour notre série . Mais si nous ne choisissons pas une fonction raisonnable, nous obtenons une définition différente de la calculabilité.$S$

Cette fonction permet également de définir la calculabilitØ d'autres fonctions avec domaine ou intervalle égal à . En changeant la gamme de , en gardant le domaine en tant que , nous obtenons aussi un définition invariante de la complexité de Kolmogorov pour . Et nous pouvons enfin dire que la fonction que nous avons choisie est elle-même calculable.S { 0 , 1 } ∗ O ( 1 ) $S$$S$$\{0,1\}^*$$O(1)$$S$

Je pense donc que la réponse à votre question est NON. Nous devons définir la calculabilité pour chaque ensemble dont nous voulons parler, car il existe des définitions non équivalentes. Mis à part une discussion très technique ou pédagogique, cela ne devrait pas être nécessaire, car une personne raisonnable peut imaginer une définition raisonnable de manière indépendante.

Mais attendez, que soit un ensemble infiniment dénombrable, et c'est tout. Quelle est notre définition raisonnable de la calculabilité pour ? Savoir que l'ensemble des bijections entre et est non vide ne nous dit pas lesquelles sont raisonnables. Nous n'avons pas de chance sans plus de détails.S S { 0 , 1 } $S$$S$$S$$\{0,1\}^*$

Et nous pouvons rencontrer plusieurs alternatives inégales mais tout aussi raisonnables. Supposons que chaque arbre ait un certain nombre de feuilles rouges et un certain nombre de feuilles vertes, et que pour chaque il existe exactement un arbre avec feuilles rouges, et que pour chaque il existe exactement un arbre à feuilles vertes. Les deux bijections sont raisonnables dans le sens où nous pouvons compter les feuilles et distinguer les couleurs, et nous pouvons marcher sans but dans les bois en comptant les feuilles sur les arbres jusqu'à ce que nous trouvions l'arbre avec exactement feuilles vertes, ou celui avec r g ∈ N g 23 23 N 2 N N 2 $r \in \mathbb{N}$$r$$g \in \mathbb{N}$$g$$23$$23$feuilles rouges. Il n'est pas clair s'il faut identifier un arbre à l'aide de son nombre de feuilles rouges ou de son nombre de feuilles vertes car ce choix conduit à des définitions inégales de la calculabilité des ensembles d'arbres. Si nous faisons plutôt notre définition en combinant les nombres avec une fonction d'appariement calculable bijective de à (ayant une calculabilité correctement définie sur ), cela identifie également chaque arbre, mais la situation est encore pire car ce n'est pas une bijection entre les arbres et , maintenant peut-être que tous les ensembles d'arbres calculables sont finis!$\mathbb{N}^2$$\mathbb{N}$$\mathbb{N}^2$$\mathbb{N}$

Ainsi, afin d'éviter toute la discussion, il faut comprendre non seulement qu'il existe une définition raisonnable de la calculabilité sur l'ensemble en question, mais également qu'il existe exactement une classe de définitions raisonnables.

Je pense que la situation devient beaucoup plus intéressante si nous apportons une complexité temporelle à l'image. Même lorsque l'on considère uniquement des entiers, nos choix sont plus importants. Par exemple, que se passerait-il si nous voulions représenter chaque nombre comme une somme de quatre carrés? On peut trouver une telle représentation, à partir d'une représentation de base, en temps quadratique attendu avec accès au hasard. Ou à la place, comme une liste de ses facteurs premiers, qui peuvent ou non être calculables en temps polynomial. Dans la mesure où nous permettons des représentations dures, nous perdons de la précision dans la complexité temporelle. Par exemple, nous ne pouvons pas dire de manière significative que certaines fonctions sont calculables en temps quadratique si nous avons une représentation deN F : N → $F:\mathbb{N} \rightarrow \mathbb{N}$$\mathbb{N}$qui peut nécessiter plus de temps quadratique pour se convertir vers ou depuis une représentation de base. Je pense que cette perspective révèle que la représentation de base est une norme quelque peu arbitraire. (Standard en ce sens que la représentation de base est ce que quelqu'un a en tête quand il dit quelque chose comme " est calculable en temps quadratique", si le modèle sous-jacent est celui qui calcule le bit chaînes de bits et nous sommes censés en déduire le sens.)$F:\mathbb{N} \rightarrow \mathbb{N}$