Numérotation admissible - Admissible numbering

Dans la théorie de la calculabilité , les numérotations admissibles sont des énumérations ( numérotations ) de l'ensemble des fonctions calculables partielles qui peuvent être converties vers et à partir de la numérotation standard. Ces numérotations sont également appelées numérotations acceptables et systèmes de programmation acceptables .

Le théorème d'équivalence de Rogers montre que tous les systèmes de programmation acceptables sont équivalents les uns aux autres au sens formel de la théorie des nombres.

Définition

La formalisation de la théorie de la calculabilité par Kleene a conduit à une fonction calculable partielle universelle particulière Ψ( e , x ) définie en utilisant le prédicat T . Cette fonction est universelle dans le sens où elle est calculable partielle, et pour toute fonction calculable partielle f il existe un e tel que, pour tout x , f ( x ) = ( e , x ), où l'égalité signifie que soit les deux les côtés ne sont pas définis ou les deux sont définis et égaux. Il est courant d'écrire ψ e ( x ) pour Ψ( e , x ); ainsi la suite ψ 0 , ψ 1 , ... est une énumération de toutes les fonctions calculables partielles. De telles énumérations sont formellement appelées numérotations calculables des fonctions calculables partielles.

Une numérotation arbitraire η de fonctions partielles est définie comme une numérotation admissible si :

  • La fonction H ( e , x ) = e ( x ) est une fonction calculable partielle.
  • Il existe une fonction totale calculable f telle que, pour tout e , η e = ψ f ( e ) .
  • Il existe une fonction calculable totale g telle que, pour tout e , e = η g ( e ) .

Ici, la première puce exige que la numérotation soit calculable ; la seconde exige que tout indice de la numérotation η puisse être effectivement converti en un indice de la numérotation ψ ; et le troisième exige que tout indice pour la numérotation ψ puisse être effectivement converti en un indice pour la numérotation η.

Théorème d'équivalence de Rogers

Hartley Rogers, Jr. a montré qu'une numérotation η des fonctions calculables partielles est admissible si et seulement s'il existe une bijection calculable totale p telle que, pour tout e , η e = p ( e ) (Soare 1987 :25).

Voir également

Les références

  • YL Ershov (1999), "Théorie des numérotations", Handbook of Computability Theory , ER Griffor (éd.), Elsevier, pp. 473-506. ISBN  978-0-444-89882-1
  • M. Machtey et P. Young (1978), Une introduction à la théorie générale des algorithmes , North-Holland, 1978. ISBN  0-444-00226-X
  • H. Rogers, Jr. (1967), The Theory of Recursive Functions and Effective Computability , deuxième édition 1987, MIT Press. ISBN  0-262-68052-1 (broché), ISBN  0-07-053522-1
  • R. Soare (1987), Ensembles et degrés récursivement énumérables , Perspectives en logique mathématique, Springer-Verlag. ISBN  3-540-15299-7