R (сложеност)

С Википедије, слободне енциклопедије

У рачунарској теорији сложености R је класа проблема одлучивости, које решава Тјурингова машина, а представља скуп рекурзивних језика.

Еквивалентне формулације[уреди | уреди извор]

R је једнака скупу свих потпуно израчунљивих функција (computable functions).

Релације према другим класама[уреди | уреди извор]

Пошто можемо да одлучимо било који проблем за који постоји препознавање и прихват улаза и ко-препознавање једноставним преклапањем (interleaving) док се не добије резултат, класа је једнака RE ∩ coRE.

Литература[уреди | уреди извор]

  • Блум, Леноре, Мајк Шаб, и Стив Смејл. "Теорија рачунања и сложеност реалних бројева: NP-потпуност, рекурзивне функције и универзалне машине."