Theorema Posner–Robinson est theorema theoriae facultatis calculandi de gradibus Turing.

Expositio recensere

Theorema. Sit   copia numerorum naturalium, quae calculari non potest. (Id est  .) Tum est copia   ut  .

Demonstratio recensere

Sit  . Volumus facere series  , quorum:

  •   est copia finita rerum sicut  , in qua  ,  .   est functio ab   in  , ut   si et tantum si  ,
  •   est copia finita rerum  ,

in qua serie, si  :

  • (a) Cuique   et  ,  ,
  • (b)   et  ,
  • (c) Cuique  ,  .

ita ut, si  , tum  . Sit  . Si habemus  , sic agamus ut   faciamus:

  1. Sit   formula numero  . Si nancisci possumus copiam   quae (a) satisfaciat, ut cuique  ,  , tum sit   et  .
  2. Sin nancisci non possumus  , tum sciamus cuique copiae   quae (a) satisfaciat esse   ut  . Sit igitur collectio   ut:
 
Sed scilicet  , ergo  . Lemma habemus:
Lemma. (de conis vitandis) Sit collectio non vacua   ut  , in quo   (vide pagina de hierarchia arithmetica). Sit  . Tum est   ut  .
Ergo, sit  , tum est   ut  , id est,  . Igitur sit   et  .

Nunc tota serie facta habemus   ut  . Ergo  , quod erat demonstrandum.

Significatio recensere

Hoc theorema naturam omnium copiarum quae calculari non possunt patefacit. Si   est copia quae calculari non potest, tum nancisci possumus copia  , ut differentia inter   et   sit  .