Discussion:Théorie de la calculabilité

Preuve par th. de Cantor

Pourquoi as-tu supprimé la référence que j'avais ajouté concernant la démonstration par th. de Cantor de l'existence de fn non calculables ? Cordialement --Jean-Christophe BENOIST (d) 23 juin 2011 à 14:00 (CEST)

Tu peux le rétablir si tu veux.--Pierre de Lyon (d) 23 juin 2011 à 22:15 (CEST)

mais il y avait une raison ? Tu as vu quelque-chose qui n'allait pas ? --Jean-Christophe BENOIST (d) 23 juin 2011 à 23:10 (CEST)

FonctionS non calculableS

La fonction R --> {0, 1}

nature(x) = {entier(x) --> 3 ; rationnel(x)--> 2 ; algébrique(x)-->1 sinon 0}

est-elle calculable ???? . --Lf69100 (discuter) 17 octobre 2015 à 10:35 (CEST)

Question intéressante, qui peut avoir des répercussions dans l'article. Je dirais intuitivement qu'elle est approchable, selon le commentaire dans Discussion:Nombre réel calculable. A nos sources. --Jean-Christophe BENOIST (discuter) 17 octobre 2015 à 11:59 (CEST)

C'est vraiment une question très intéressante, et non triviale. Je pense qu'il doit exister un algorithme pour déterminer dans un temps fini si x est entier, rationnel ou algébrique (période dans divers développements, fractions continues..). On pourrait en conclure que R est calculable, mais non car il n'y a aucun moyen de savoir à partir de combien de temps on doit abandonner la recherche de périodicité pour distinguer 1 ou 0. De même que Oméga n'est pas calculable bien que on finisse par obtenir sa valeur au bout d'un temps infini (car il n'y a pas de convergence effective), R n'est pas calculable bien que on finisse par l'obtenir en un temps infini (pour la même raison). Mais je trouve 0 sources déjà sur la calculabilité de l'agébricité d'un nombre, et sur la notion de "convergence effective" pour une fonction ainsi définie. Si on en trouve, il y a des ajouts à faire à cet article. --Jean-Christophe BENOIST (discuter) 18 octobre 2015 à 00:06 (CEST)

Il me semble que cela dépend de la présentation des nombres. --Pierre de Lyon (discuter) 18 octobre 2015 à 10:15 (CEST)

Histoire de la calculabilité

Bonjour, Pensez-vous que ce soit utile de détailler la partie Histoire de la calculabilité ? Le renvoi à la page Histoire des mathématiques pourrait être plus précis. Pourquoi ne pas ajouter la section à regarder ? Cordialement, --Cclaire03 (discuter) 3 janvier 2019 à 16:57 (CET)

Merci pour votre intérêt. Bien sûr que cette section mérite d'être détaillée. Il y a un gros travail à faire ! Je pense que le renvoi à la page Histoire des mathématiques est maladroit et doit être mentionné avec "Article connexe : ...." (il y a un modèle pour ça je crois). Je pense que cette section historique doit s'appuyer sur des sources secondaires (livre de calculabilité qui parle de l'histoire) et des sources primaires (lien vers les articles fondateurs). Il faut des sources "inline" dans le texte. Bonne journée. --Fschwarzentruber (discuter) 3 janvier 2019 à 17:07 (CET)

Définition de la calculabilité

Bonjour, Pour la définition de la calculabilité, j'ai lu celle proposée sur la page Wikipédia anglaise et je trouve qu'elle est plus facile à comprendre. Ainsi, on pourrait rajouter au tout début que la calculabilité est la capacité de résoudre un problème de manière efficace. De plus, dans une partie "Lien entre calcul et calculabilité" ou toujours dans la définition du début, on pourrait revenir à la racine même du mot calcul en disant qu'il vient du latin "calculus" qui signifie cailloux ; ce qui a du sens parce que lorsqu'on apprend à calculer on fait des manipulations avec des objets/ symboles comme des cailloux. On rappellerait que les multiplications sont des additions successives et que les divisions sont des additions et soustractions successives ; donc ce sont des manipulations de symboles (cailloux). On finirait par dire que au final, quand on aborde la calculabilité, on cherche à déterminer la classe des fonctions calculables, c'est-à-dire les fonctions qui peuvent s'exprimer avec des manipulations de symboles (cailloux). D'où le lien entre calcul et calculabilité qui enrichirait la définition de la calculabilité. Qu'en pensez-vous ? --Cclaire03 (discuter) 8 janvier 2019 à 17:19 (CET)

Je ne sais pas s'il existe une source qui aborde les choses ainsi. La calculabilité n'est sans doute pas réductible au calcul avec des cailloux, qui n'est certainement pas Turing-complet. De plus, la calculabilité a un sens fondamental, pas facile à cerner, qui est en jeu dans la thèse de Church, et réduire ce sens au calcul avec des cailloux ne me semble pas une bonne idée sauf pour faire une vulgarisation extrême. Mais là encore nos opinions personnelles ont peu d'importance, il faut voir comment les sources vulgarisent le concept de calcul, et s'en inspirer. --Jean-Christophe BENOIST (discuter) 8 janvier 2019 à 17:27 (CET)

D'accord, merci de vos informations. --Cclaire03 (discuter) 8 janvier 2019 à 22:01 (CET)

Si les liens entre la calculabilité et les cailloux vous intéressent, vous pouvez lire cela Est-ce que ça s’arrête ?. --Pierre de Lyon (discuter) 9 janvier 2019 à 12:28 (CET)

Oui, cela revient à implémenter une MdT avec des cailloux et des manipulations de cailloux. Mais ce n'est pas ce à quoi on pense spontanément quand on parle de "calcul avec des cailloux", on pense spontanément à des abaques et même plus spécifiquement à Abaque_(calcul)#Cailloux et ce sont des systèmes formels beaucoup plus simples, qui ne recouvrent pas forcément toute la notion de calculabilité. --Jean-Christophe BENOIST (discuter) 9 janvier 2019 à 12:44 (CET)

Mais s'il y a aussi les jeux de cailloux (en) qui sont essentiels en calculabilité et ne sont pas une simple traduction des machines de Turing, puisqu'ils permettent de démontrer des résultats spécifiques. Je ne propose pas de traduire l'article en français, parce qu'il est encore assez pauvre en anglais. --Pierre de Lyon (discuter) 9 janvier 2019 à 15:27 (CET)

Tout à fait, cela n'empêche pas de présenter certains problèmes spécifiques liés à la calculabilité par des jeux de cailloux, au contraire c'est assez didactique. Le problème était de présenter la notion générale de "calculabilité" par du "calcul avec des cailloux", ce qui n'est pas faux, mais (très) incomplet. --Jean-Christophe BENOIST (discuter) 9 janvier 2019 à 15:46 (CET)

 Cclaire03 : Permettez-moi de vous mettre en garde sur la confusion entre « effective » et « efficace ». La calculabilité s'intéresse à l'effectivité, c'est-à-dire au fait qu'un problème puisse être résolu par calcul. --Pierre de Lyon (discuter) 9 janvier 2019 à 17:09 (CET)

 PIerre.Lescanne : En effet, il s'agit d'une erreur de traduction de ma part. Merci de votre mise en garde. --Cclaire03 (discuter) 9 janvier 2019 à 20:19 (CET)

Fini/infini

La dernière modif de l'article montre un imbroglio dans l'article. De mémoire, (je n'ai pas mes sources sous la main) le temps de calcul peut être infini (Pi a une infinité de décimales, mais il est calculable) mais le programme pour le calculer doit être fini (qui est peut-être mentionné dans l'article comme "nombre fini d'étapes", mais ce n'est pas clair et peut être confondu avec un temps fini). Tout cela est assez mal expliqué dans l'article, voire faux (cf le refnec que je viens de rajouter). Je vais essayer de refondre tout cela, mais n'hésitez pas à intervenir aussi, on ne peut pas laisser l'article ainsi. Jean-Christophe BENOIST (discuter) 30 mars 2022 à 11:49 (CEST)

@PIerre.Lescanne Je suis d'accord avec ton ajout, mais cela ne source pas le temps fini ? La notion d'"algorithme" inclue les algorithmes qui ne se terminent pas (notamment le calcul de Pi). Jean-Christophe BENOIST (discuter) 30 mars 2022 à 17:56 (CEST)