Математическая логика и теория алгоритмов. Стенюшкина В.А. - 56 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

Составители: 

Рубрика: 

Теорема 5 Для каждого бесконечного перечислимого множества Х суще-
ствует вычислимая функция, определенная на подмножестве этого множества и
не продолжаемая до вычислимой функции, определенной на всем Х.
Теоремы 4, 5 в совокупности дают пример алгоритма с неразрешимой об-
ластью применимости.
Разрешимые и перечислимые множества составляют простейшие и в то
же время важнейшие примеры множеств, строение которых задается с помо-
щью тех или иных алгоритмических процедур. Систематическое изучение
множеств конструктивных объектов с точки зрения таких свойств этих мно-
жеств, которые связаны с наличием тех или иных алгоритмов, образует алгори-
тмическую теорию множеств (так называемую). 
      Теорема 5 Для каждого бесконечного перечислимого множества Х суще-
ствует вычислимая функция, определенная на подмножестве этого множества и
не продолжаемая до вычислимой функции, определенной на всем Х.
      Теоремы 4, 5 в совокупности дают пример алгоритма с неразрешимой об-
ластью применимости.
      Разрешимые и перечислимые множества составляют простейшие и в то
же время важнейшие примеры множеств, строение которых задается с помо-
щью тех или иных алгоритмических процедур. Систематическое изучение
множеств конструктивных объектов с точки зрения таких свойств этих мно-
жеств, которые связаны с наличием тех или иных алгоритмов, образует алгори-
тмическую теорию множеств (так называемую).

Страницы