Discussion:Castor affairé

Démonstration de l'incalculabilité de Σ

J'ai supprimé un passage sur la démonstration de l'incalculabilité de Σ, essentiellement parce que je ne le trouve pas clair (la définition de la fonction u, par exemple). Je le laisse ici, afin de le mettre un peu d'équerre si quelqu'un est intéressé. — Poulpy (d) 10 juillet 2012 à 18:35 (CEST)

Il existe plusieurs moyens de prouver l'incalculabilité de $\Sigma$ ; la démonstration qui suit utilise la fonction de combinaison des machines de Turing.

Hypothèse de départ : supposons que $\Sigma$ soit calculable.

Si $\Sigma$ est calculable, alors la fonction D définie par $D(n)=\Sigma (2n)$ l'est également. Si la fonction $D$ est calculable, alors elle peut être représentée à l'aide d'une machine de Turing, que nous appellerons $M_{d}$, et qui possédera un nombre fini d'état k (que nous ne connaissons pas).

Prenons maintenant la fonction $u(f(n))=f(n)$, qui se contentera d'afficher la valeur de retour d'une certaine fonction passée en paramètre. À l'instar de la fonction D, cette fonction u peut être représentée par une machine de Turing, que nous appellerons $M_{u}$. On prendra note qu'il est possible de coder cette machine $M_{u}$ en utilisant n états (nous pourrions l'implémenter en moins que cela, mais cela ne nous intéresse pas dans le cadre de cette preuve).

Définissons maintenant la machine M, qui est une composition des machines $M_{u}$ et $M_{d}$. Autrement dit, nous allons passer en paramètre de la fonction u la fonction D afin de réaliser l'opération $u(D(n))$. Du fait de la composition, cette machine M sera composée de n + k états et, conformément aux descriptions précédentes, écrira sur une bande vierge $D(n)=\Sigma (2n)$ symboles 1.

En résumé, nous avons obtenu une machine de Turing de n + k états et qui produit $\Sigma (2n)$ symboles. Que pouvons-nous dire sur la valeur de $\Sigma (n+k)$, qui est le nombre de 1 pouvant être écrits avec $n+k$ états ? On peut affirmer que cette fonction retournera une valeur plus grande ou en tout cas égale au nombre de 1 écrits par la machine M, c'est-à-dire : $\Sigma (n+k)$ ≥ $\Sigma (2n)$.

$\Sigma$ étant une fonction monotone, on peut affirmer que pour tout k < n, $\Sigma (2n)$ > $\Sigma (n+k)$. Cette inéquation, combinée avec celle obtenue précédemment, nous donne : $\Sigma (2n)$ > $\Sigma (n+k)$ ≥ $\Sigma (2n)$ (avec $k<n$).

Cette contradiction permet d'affirmer que notre hypothèse de départ était fausse, $\Sigma$ n'est pas calculable.

valeurs pas à jour

ça fait presque 1 an que l'on connait une machine à 6 états qui explose la borne inferieure donnée dans l'article.

la machine en question: https://www.sligocki.com/2022/06/21/bb-6-2-t15.html

cela fait qu'il faudrait refaire toute la partie sur "6 états" ainsi que celle sur les valeurs connues Marcocorico (discuter) 12 mars 2023 à 00:19 (CET)

@ Marcocorico :

Bonjour, Merci de votre remarque. Je vous encourage vivement à participer activement à Wikipédia, en mettant à jour l'article, puisque vous semblez avoir les informations. Pierre Lescanne (discuter) 12 mars 2023 à 16:23 (CET)