Déjà, définis proprement le problème. Pour commencer, c'est inutile de considérer autre chose que N, vu que tu peux mettre en bijection N et N^p
Déjà, si la question est "étant donné un programme f, peut-on écrire un programme qui détermine l'ensemble des valeurs prises par f en temps fini", la réponse est non, vu que ça se ramène facilement au problème de l'arrêt.
A partir de là, une question plus intéressante (en supposant que, dans ta formulation E est le domaine de f, donc) est : "étant donné un programme f qui termine pour chaque entrée, est-il possible d'écrire un programme qui détermine l'ensemble des valeurs prises par f en temps fini". Ca m'étonnerait franchement que ce soit possible, à moins que E ne soit fini (tu essaie d'évaluer la fonction en un nombre infini de points), mais j'ai pas de preuve sous la main.
Je suis peut être complètement à côté de la plaque, mais ça me semble être un problème idiot qui ne nécessite certainement pas de parler de curryfication, d'analyse de flot ou d'incomplétude gödelienne.
# Pour en revenir au problème ...
Posté par smeuuh . En réponse au journal Déterminer le domaine d'un programme. Évalué à 5.
Déjà, si la question est "étant donné un programme f, peut-on écrire un programme qui détermine l'ensemble des valeurs prises par f en temps fini", la réponse est non, vu que ça se ramène facilement au problème de l'arrêt.
A partir de là, une question plus intéressante (en supposant que, dans ta formulation E est le domaine de f, donc) est : "étant donné un programme f qui termine pour chaque entrée, est-il possible d'écrire un programme qui détermine l'ensemble des valeurs prises par f en temps fini". Ca m'étonnerait franchement que ce soit possible, à moins que E ne soit fini (tu essaie d'évaluer la fonction en un nombre infini de points), mais j'ai pas de preuve sous la main.
Je suis peut être complètement à côté de la plaque, mais ça me semble être un problème idiot qui ne nécessite certainement pas de parler de curryfication, d'analyse de flot ou d'incomplétude gödelienne.