Жалпыланған есептелiмдi үйiрлердiң универсал нөмiрлеулерi

Аңдатпа

Бұл жұмыста жиындардан және барлық жерде анықталған функциялардан құралған әр түрлi үйiрлердiң универсал жалпыланған есептелiмдi нөмiрлеулерi болуы туралы сұрақтар зерттеледi. Бұрыннан белгiлi кез келген A жиыны үшiн, бұл жерде ∅ 0 ≤T A, A-е.с. S ақырлы үйiрiнде A-есептелiмдi универсал нөмiрлеу болады, сонда тек сонда ғана S үйiрi iшкi жиын қатынасы бойынша ең кiшi элементтi қамтыса. Бұл критерий шексiз үйiрлер үшiн орындалмайды. Кез келген A жиыны үшiн A-есептелiмдi универсал нөмiрлеуi бар iшкi жиын қатынасы бойынша ең кiшi элементтi қамтымайтын жиындардан құралған шексiз A-есептелiмдi S үйiрi табылады, сонымен қатар S үйiрiнде барлық элементтер жұптық қиылыспайды. Егер A– гипериммунды жиын болса, онда кем дегенде екi элементi бар барлық жерде анықталған функциялардан құралған A-есептелiмдi F үйiрiнде A-есептелiмдi универсал нөмiрлеуi болмайды. Ал егер degT (A) гипериммунды-бос болса, онда әрбiр барлық жерде анықталған функциялардан құралған үйiрде A-есептелiмдi универсал нөмiрлеуi болады. Бұл жұмыста бiз A-гипериммунды-бос оракулымен есептелетiн жиындардан құралған кез келген шексiз эффективтi дискреттi үйiрлерде A-есептелiмдi универсал нөмiрелуi болатынын көрсеттiк. Сондай-ақ, егер S үйiрi барлық толықтауы ақырлы жиындарды қамтыса және кем дегенде бiр толықтауы рекурсив саналымды жиынды қамтымаса, онда бұл үйiрдiң универсал Σ −1 2 - есептелiмдi нөмiрлеуi болмайтыны дәлелдендi.