Pourquoi les fonctions totales non dénombrable?

Question

Nous avons appris le concept de énumérations de fonctions. Dans la pratique, ils correspondent à des langages de programmation.

Dans une remarque en passant, le professeur a mentionné que la classe de toutes les fonctions au total (à savoir les fonctions qui se terminent toujours pour chaque entrée) est pas dénombrable. Cela voudrait dire que nous ne pouvons pas concevoir un langage de programmation qui permet d'écrire toutes les fonctions au total, mais pas d'autres --- ce qui serait agréable d'avoir!

Alors, comment est-ce que nous (apparemment) devons accepter le risque de non-résiliation si l'on veut une puissance de calcul décent?

Answer 1

En raison de diagonalisation. Si $ (f_e: e \ in \ mathbb {N}) $ est une énumération calculable de toutes les fonctions calculables au total de $ \ mathbb {N} $ à $ \ mathbb {N} $, de sorte que tous les f_e $ $ était totale, puis $ g (i) = f_i (i) + 1 $ serait également une fonction totale calculable, mais il ne serait pas dans l'énumération. Ce serait en contradiction avec les hypothèses sur la séquence. Par conséquent, aucune énumération des fonctions calculables peut consister exactement les fonctions totales calculables.

Supposons que nous pensons à une fonction chiffrable universelle $ h (e, i) $, où les moyens « universels » $ h $ est une fonction binaire calculable et que pour chaque fonction totale calculable unaire $ f (n) $ il y a un certain $ e $ tel que $ f (i) = h (e, i) pour tout i $ $ $. Ensuite, il faut aussi avoir un e $ $ tel que $ g (n) = h (e, n) $ est pas une fonction totale, en raison du paragraphe précédent. Sinon $ h $ donnerait une énumération des fonctions calculables au total calculables unaire qui inclut toutes les fonctions calculables au total unaire.

Ainsi, l'exigence que chaque fonction est un système de fonctions est totale est incompatible avec l'existence d'une fonction universelle dans ce système. Pour certains systèmes faibles, tels que les fonctions récursives primitives, chaque fonction est totale, mais il n'y a pas de fonctions universelles. Les systèmes plus solides qui ont des fonctions universelles, comme calculabilité Turing, doivent simplement avoir des fonctions partielles afin de permettre la fonction universelle d'exister.

Answer 2

Pour être clair, il faut distinguer les fonctions mathématiques (je les appellerai Fonctions et il y a souvent indénombrablement beaucoup d'entre eux ne sont donc pas du tout dénombrable) et les fonctions que vous pouvez écrire: I les appellera programmes ou encore fonctions calculables .

Un sous-ensemble $ S $ d'un ensemble dénombrable $ E $ est appelé calculable s'il y a un programme qui, étant donné un élément $ x $ de $ E $ répond "oui" si $ x?S $ et "non" si $ x \ not?S $. (Et il doit toujours répondre quelque chose) Un ensemble est appelé récursive dénombrable si le programme est autorisé à ne pas répondre au lieu de dire "non". (Il est équivalent d'exiger que le programme doit imprimer tous les éléments de $ S $ dans l'ordre)

L'ensemble de tous les programmes qui sont au total sur une ensemble fini dénombrable parce que vous pouvez écrire un interprète qui vient de lancer le programme sur tous les éléments de l'ensemble fini et le retour « oui » si tous se termine. (Mais ne peut pas voir si aucun d'entre eux ne font pas)

Votre professeur a dit que l'ensemble de tous les programmes qui sont sur un total de non dénombrable parce que vous ne pouvez pas exécuter votre programme ensemble infini sur un nombre infini de éléments.

Mais cela ne signifie pas que ce soit mauvais:

1. Par exemple, l'ensemble si tous les programmes qui sont prouvablement total est dénombrable parce que vous pouvez énumérer toutes les épreuves et vérifier mécaniquement si elles prouvent votre programme est totale .

2. Même un ensemble dénombrable ne serait pas pratique, parce que vous pourriez avoir à attendre pour toujours sans être sûr que la procédure se terminerait un jour. Je ne vois pas comment utiliser un programme qui énumèrent toutes les fonctions au total ...

Il y a quelques langages de programmation où tout ce que vous écrivez est garanti pour terminer juste avec le typage statique! Il y a même certains qui vous garantit polynomiale liés. Ils sont la plupart du temps scolaire pour l'instant, l'écriture dans les va probablement vous faire sentir les contraintes plus que l'écriture en Python, mais il y a beaucoup de chercheurs qui travaillent sur ce sujet.

Pour répondre à votre question: dans un sens, oui. non-résiliation potentielle est nécessaire pour être Turing-complet (le plus de puissance de calcul pour l'instant). Mais je ne trouve pas ce lien direct avec le fait que les fonctions totales sont dénombrable ou non. Vous pouvez toujours écrire tous les programmes au total!