Cardinalité de l'ensemble des algorithmes

Quelqu'un dans une discussion a évoqué (il estime) qu'il peut y avoir au moins un nombre continu de stratégies pour aborder un problème spécifique. Le problème spécifique était les stratégies de trading (pas les algorithmes mais les stratégies) mais je pense que c'est à côté du point de ma question.

Cela m'a fait réfléchir sur la cardinalité de l'ensemble des algorithmes. J'ai cherché un peu mais je n'ai rien trouvé. J'ai pensé que, puisque les machines de turing fonctionnent avec un ensemble fini d'alphabet et que la bande doit être indexable et donc dénombrable, il est impossible d'avoir un nombre indénombrable d'algorithmes. Ma théorie des ensembles est certes rouillée, donc je ne suis pas du tout certain que mon raisonnement soit valide et je ne serais probablement pas en mesure de le prouver, mais c'est une pensée intéressante.

Quelle est la cardinalité de l'ensemble des algorithmes?

Un algorithme est officieusement décrit comme une séquence finie d'instructions écrites pour accomplir une tâche. Plus formellement, ils sont identifiés comme des machines Turing, bien que vous puissiez également les décrire comme des programmes informatiques.

Le formalisme précis que vous utilisez n'a pas beaucoup d'importance, mais le point fondamental est que chaque algorithme peut être écrit comme une séquence finie de caractères, où les caractères sont choisis parmi un ensemble fini, par exemple, des lettres romaines, ASCII ou des zéros et des uns. Pour simplifier, supposons les zéros et les uns. Toute séquence de zéros et de uns n'est qu'un nombre naturel écrit en binaire. Cela signifie qu'il existe au plus une infinité d'algorithmes dénombrable, puisque chaque algorithme peut être représenté comme un nombre naturel.

Pour un crédit complet, vous devez vous inquiéter du fait que certains nombres naturels ne codent pas des programmes valides, il peut donc y avoir moins d'algorithmes que les nombres naturels. (Pour le crédit bonus, vous pouvez également vous demander s'il est possible que deux différents nombres naturels représentent le même algorithme.) Cependant, print 1, print 2, print 3et ainsi de suite sont tous les algorithmes et tous différents, donc il y a au moins dénombrable infiniment nombreux algorithmes.

Nous concluons donc que l'ensemble des algorithmes est infiniment dénombrable.

L'ensemble des algorithmes est infiniment infini. C'est parce que chaque algorithme a une description finie, disons comme une machine de Turing.

Le fait qu'un algorithme ait une description finie nous permet de saisir un algorithme dans un autre, et c'est la base de la théorie de la calculabilité. Il nous permet par exemple de formuler le problème d'arrêt.

au moins un nombre continu de stratégies pour aborder un problème spécifique

"Continuum" est probablement censé signifier les vrais nombres ... utiliser "au moins" avec ce mot est absurdement excessif. Pour être un peu ironique: infiniment infini est assez grand, mais infiniment infini est ... plus grand que grand. Plus encore. Insondable.

Alors jetons ça par la fenêtre. Pour voir à quel type d'infini nous avons affaire est d'une simplicité déconcertante (et intuitive, même si votre ami n'a jamais entendu parler d'informatique théorique):

• Tout algorithme peut être implémenté avec n'importe quel langage complet de Turing; choisissez votre poison préféré des langages du monde réel (Java, C, ...) pour démystifier un peu cela. Tous ces éléments sont équivalents à l'ensemble théorique d'algorithmes que n'importe qui pourrait jamais trouver. Notez que chaque algorithme est en lui-même fini, c'est-à-dire qu'il n'y a pas d'algorithmes qui prendraient infiniment de symboles à écrire.
• Ne pensez pas aux machines de Turing compliquées. La langue de votre choix utilise des fichiers simples pour stocker son code source. Chaque fichier est une collection de petits nombres (aka, octets). L'important est que ces nombres soient très certainement entiers et non continus. (Si vous êtes un puriste et que vous souhaitez rester dans le régime théorique, remplacez le mot "octet" par "symbole", cela ne change rien.) Si vous avez peur des gros programmes qui sont répartis sur plusieurs fichiers (et bibliothèques , et d'autres choses), puis zippez-les simplement dans une seule archive compressée (c'est-à-dire un seul fichier).
• Maintenant, vous pouvez attribuer un seul nombre entier à chaque fichier, bijectivement. Nous écrivons simplement le désordre entier des bits / octets du fichier l'un après l'autre, et nous nous retrouvons avec un très grand nombre exprimé en binaire. Dans un passé lointain, les gens l'ont fait: ils ont imprimé des programmes binaires compilés comme de longues listes de nombres hexadécimaux dans des magazines; vous les saisiriez, mais ne les verriez jamais autrement que sous forme de nombres (souvent regroupés de manière pratique en ensembles de 8 ou 16 chiffres pour faciliter la saisie).
• Donc: chaque programme peut être représenté par un nombre entier, quoique arbitrairement grand. L'inverse fonctionne également - chaque entier peut être immédiatement et trivialement transféré dans un fichier et lancé sur un compilateur (évidemment, seule une petite partie de ceux-ci seront des programmes valides, mais cela n'a plus d'importance pour nous maintenant).
• En fin de compte, les programmes, et donc les algorithmes, sont un sous-ensemble des entiers; par conséquent, seuls de nombreux nombres peuvent exister.
• NB, le fait qu'il existe de nombreuses implémentations différentes d'un seul algorithme est en notre faveur, c'est-à-dire que beaucoup de ces entiers se condensent en (différentes représentations de) le même algorithme. Donc, si l'infini dénombrable n'était pas déjà le plus petit type d'infini, nous devrions nous inquiéter du fait que le nombre d'algorithmes soit encore plus petit, mais certainement pas plus grand (c'est-à-dire indénombrable).

Le problème spécifique était les stratégies de trading (pas les algorithmes mais les stratégies)

Je ne sais pas ce que votre ami veut dire par "stratégie"; Je suppose qu'il veut dire quelque chose qui est un peu comme un algorithme, mais pas assez formulé avec suffisamment de détails pour le pirater dans un ordinateur? Ou qui dépend en quelque sorte de "l'intuition" humaine pendant l'exécution? Si oui, alors ce ne sont que des détails non pertinents. L'humanité n'a pas encore trouvé de description de processus plus puissante ou plus large que les «algorithmes» dans le sens que nous utilisons dans CS.

Voir la numérotation de Gödel , c'est un fait fondamental en informatique que les algorithmes sont dénombrables, comme le sont par extension les ensembles énumérables récursivement.

Les algorithmes étant dénombrables, il est facile de montrer qu'il n'existe pas d'algorithme pour vérifier chaque ensemble dans un système formel (attribuer une valeur de vérité à un problème). Cela équivaudrait à affecter un algorithme à chaque fonction mappant l'ensemble des problèmes aux valeurs booléennes. L'ensemble de ces fonctions est cependant indénombrable (trivialement de même cardinalité que l'ensemble de puissance de l'ensemble des problèmes, donc indénombrable).

J'espère que cela donne une idée de pourquoi les algorithmes doivent être "moins puissants" que n'importe quelle fonction, donc dénombrable (ignorons l'hypothèse du continuum ici).

Si l'on ne part pas de l'exigence qu'une stratégie doit être implémentable avec un algorithme, et ignore les effets de discrétisation réels, on pourrait par exemple accepter ce qui suit comme stratégie de trading paramétrée:

$a$$b$$a$$b$

$a$$b$

Si nous concevons les algorithmes comme des programmes informatiques écrits en binaire *, alors le nombre d'algorithmes est le nombre de nombres binaires (entiers). Ainsi la cardinalité des algorithmes est la cardinalité des entiers.

* Une preuve que les machines de turing peuvent exécuter tous les algorithmes et que les ordinateurs peuvent exécuter n'importe quel programme de machines de turing rendrait cette réponse inutilement longue. Le premier peut dépendre de la définition d'un algorithme, mais je ne pense pas que vous utilisez des stratégies de trading non calculables.

Les autres réponses ont déjà expliqué que dans le modèle standard de calcul (machines de Turing, calcul lambda, etc.) l'ensemble des algorithmes est infiniment comptable.

Cependant, il existe d'autres modèles théoriques de calcul dans lesquels l'ensemble des algorithmes est infiniment infini. Par exemple, les machines Blum – Shub – Smale ont un ensemble d'instructions infiniment infini ¹ , de sorte que leur ensemble d'algorithmes est également infiniment infini.

puisque les machines de turing fonctionnent avec un ensemble fini d'alphabet et la bande doit être indexable donc dénombrable

Étant donné une taille particulière, il existe un nombre fini de machines Turing et il existe de nombreuses tailles. Un ensemble dénombrable de nombres, tant qu'ils sont finis, est dénombrable. La taille de l'alphabet est un facteur dans le nombre de machines Turing, mais pas la taille de la bande. Si l'alphabet était autorisé à avoir un nombre innombrable de caractères, alors il y aurait un nombre incalculable de machines (chaque nombre réel pourrait être codé comme une séquence de symboles).

$\sqrt{.5}$$\sqrt{.5}$