URL: https://linuxfr.org/users/montaigne/journaux/d%C3%A9terminer-le-domaine-dun-programme Title: Déterminer le domaine d'un programme Authors: Ontologia Date: 2009年02月24日T13:07:39+01:00 Tags: Score: 1 Je devrais la mettre en forum, mais ça peut être intéressant. Une question aux théoriciens qui traînent par ici : est-on capable pour une fonction définie dans un langage turing-complet, ayant défini son ensemble de départ, de déterminer l'ensemble d'arrivé de la fonction ? Google n'est pas mon ami, pas plus que google scholar, mais je me doute que je ne lui donne pas les bons mots-clés. Soit f une fonction (un programme), avec E et F tel que f : E -> F Sait-on définir le domaine de F, en fonction du code de f ? On part du principe que E et F sont des produits cartésiens d'ensembles d'entiers naturels, sachant qu'on peut assimiler le calcul réel à de la virgule fixe (je fais un grosse approximation là..). On peut découper le problème en curryfiant récursivement f p fois (sachant que E = |N^p) de sorte à obtenir p fonction du type fi : |N -> F En improvisant, j'imagine que par analyse de flot, on peut déterminer pas mal de choses, à condition que le programme ne soit pas trop gros. Et encore, espérer tomber sur une fonction qui ne soit pas de complexité exponentielle... L'idée est d'injecter des intervals et d'analyser toutes les branches en exportant l'interval, l'ensemble sur chacune des branches possible. Il y a probablement d'autres méthodes utilisant d'autres outils : l'analyse de flot est un algo exponentiel qui peut par conséquent vite devenir inutilisable en pratique. D'où ma question : est-ce un problème qui prend en pleine figure une incomplétude gödelienne, ou s'agit-il d'un problème résolvable et si oui quel recherches ont été faites là dessus, quel mots clés donner à manger à google scholar ?