Discussion :

[lemacdupc33]

Bonjour

Il existe des limites à l'informatique : il y a un nombre dénombrable d'algorithmes donc certaines fonctions indénombrables sont incalculables si j'ai bien compris.

Comment résoudre de telles fonctions ?

Es ce que les problèmes de calculabilité ne concernent que les mathématiques ou bien touche aussi le développement ?

Ou peut on rencontrer des fonctions incalculables ? Peut on quand même "tout faire" avec un langage turing complet ?

merci pour votre réponse.

cdt

[dourouc05]

Non, tu ne peux pas tout faire avec un langage de programmation, justement pour la raison que tu as donnée. Par contre, les problèmes impossibles à résoudre complètement sont extrêmement rares en pratique.

Tu as probablement déjà rencontré le problème de l'arrêt : déterminer si un programme s'arrête. Il est impossible d'écrire un programme qui détermine si un autre programme se termine ; par contre, les analyseurs statiques de code montrent qu'on peut résoudre un grand nombre d'instances du problème de l'arrêt, eux qui peuvent détecter un certain nombre de cas de boucles infinies, par exemple. Maintenant, un analyseur statique ne pourra jamais dire qu'un problème est exempt de défaut, pour cette raison théorique.

[lemacdupc33]

Merci pour votre réponse

Es ce que cela signifie qu'il y a des cas ou le compilateur ne trouve pas l'erreur ? Es ce frequent ?

Merci de votre reponse

[dourouc05]

Pour un compilateur, au contraire, on est toujours dans le domaine du calculable (un langage de programmation correspond à une grammaire algébrique, avec des algorithmes efficaces : CYK, Early). L'analyse sémantique n'est pas vraiment un problème non plus, en tout cas quand elle ne fait que le travail nécessaire à la compilation (pas trop de vérification d'erreurs).

Cela signifie qu'un ordinateur ne peut pas, en général, prouver que ton code est correct (c'est plus le rôle d'un logiciel d'analyse statique que d'un compilateur — à la limite, peut-être de l'analyse sémantique du compilateur) ; par contre, dès que tu ne cherches "qu"'à trouver un très grand nombre de défauts courants ou que tu te restreins dans l'expressivité de ton langage, il y a moyen d'y arriver.
C'est pour ça que ces logiciels sont souvent implémentés avec des motifs qu'ils recherchent : s'il est présent, c'est qu'il y a un problème, directement remonté à l'utilisateur.

[tbc92]

Concrètement, pour qu'on arrive à suivre cette discussion intéressante, on peut traduire ?

Par exemple, la toute première phrase :

Il existe des limites à l'informatique : il y a un nombre dénombrable d'algorithmes donc certaines fonctions indénombrables sont incalculables si j'ai bien compris.

Il y a un nombre dénombrable d'algorithmes : Ok, je pense comprendre, et être d'accord.

donc certaines fonctions indénombrables sont incalculables : c'est quoi une fonction indénombrable ? Et c'est quoi une fonction incalculable ?

[lemacdupc33]

je te conseille de lire sur Wikipedia : https://fr.wikipedia.org/wiki/Calculabilit%C3%A9

C'est de l'informatique théorique

En gros Il existe des fonctions infinies or les ordinateurs sont finis et par conséquent elles sont incalculables.
Dénombrable signifie que l'on peut dénombrer comme l'ensemble des entiers. Tandis que l'ensemble des réels sont indénombrables.

Comme un algorithme est fini il ne pourra pas "compter" quelque chose d'infini : c'est le problème de l'arrêt

Je ne suis pas expert mais c'est ce que j'ai compris.

[dourouc05]

En gros Il existe des fonctions infinies or les ordinateurs sont finis et par conséquent elles sont incalculables.
Dénombrable signifie que l'on peut dénombrer comme l'ensemble des entiers. Tandis que l'ensemble des réels sont indénombrables.

Une fonction n'est pas "infinie" : il y a un nombre infini et indénombrable de problèmes à résoudre, pour lesquels on ne peut apporter qu'un nombre infini et dénombrable d'algorithmes (on peut "compter" les algorithmes, puisqu'il s'agit de mots générés par une grammaire). Il doit donc y avoir des problèmes pour lesquels on ne peut apporter aucune solution algorithmique, parfaite : ils sont dits incalculables. (Ça doit être le théorème de Cantor qui dit ça.)
Pour la théorie, calculer la valeur d'une fonction ou résoudre un problème, c'est (en gros) du pareil au même.

Enfin bon, sans passer sur toutes les étapes de la théorie, ça devient très vite imbuvable , avec des concepts qui s'imbriquent à l'infini. (Et, d'ailleurs, même avec la théorie devant les yeux, c'est imbuvable par moments… et je vais me faire taper parce que j'ai dit ça .)

Au fait, @macdupc93, il te reste des questions ?

[lemacdupc33]

Oui j'ai encore une question profonde :

Se peut il qu'une intelligence artificielle soit incalculable ? Auquel cas il soit impossible de créer une conscience ? Puisqu'il y a une infinité de fonctions incalculable du même genre.

Merci

[dourouc05]

C'est philosophique ! Déjà, il faudrait définir la notion de conscience. Cependant, les techniques actuelles se font avec des réseaux neuronaux (et pas mal de sophistication à côté), pas impossible qu'on arrive à créer un semblant de conscience qui peut recréer tout ce qu'on lui a déjà montré et arrive à en extrapoler le comportement à avoir dans d'autres situations — le tout avec un algorithme d'apprentissage en temps polynomial.

[lemacdupc33]

Bonjour,

Autre chose : Y a t il de la programmation dans les domaines de la logique floue, les réseaux neuraux ou de latence réseau ?

Merci

[dourouc05]

Oui : il faut implémenter la logique floue, les réseaux neuronaux (apprentissage et prédiction) ; la latence réseau n'existe que par les routeurs et autres appareils réseau. Maintenant, je ne suis pas sûr de saisir la finalité de la question .

[lemacdupc33]

Merci de votre reponse: je débute en programmation.