Salut,
vlà ce que je viens de lire sous google
une fonction f est calculable si elle est un programme informatique
dont on est certain qu'il s'arrête quelque soit l'entrée fournie.
c est donc clairement calculable puisque il s'agit d'un test sur
un nombre fini de fonctions.
pour les autres , l'idée naïve serait peut être
de construire
calculable en temps n, ce qui ficherait la m....
pour le calcul de l'inf et du sup sur un ensemble dénombrable de fonctions.
(????)
ps: il n'existe pas de compilateur indiquant si une fonction quelconque
est calculable. Les domaines connexes sont très certainement le théorème
d'incomplétude de Gödel: une théorie mathématique, suffisamment élaborée,ie, comprenant l'arithmétique, non contradictoire, est incomplète. On peut toujours rajouter des axiomes à cette théorie.
regardre aussi l'argument diagonal de Cantor, les machines de Turing
et le lambda-calcul.
