Научная электронная библиотека
Монографии, изданные в издательстве Российской Академии Естествознания
Дискретная оптимизация и моделирование в условиях неопределенности данных
Перепелица В. А., Тебуева Ф. Б.,
1.4. Вычислимые функции и породимые множества. Перечислимые множества и разрешимые множества
Вычислимая функция – это функция, которая вычисляется каким-либо алгоритмом.
Термин «вычисляется» означает следующее:
– если на вход алгоритма подано значение аргумента из области определения функции, то на выходе получается результат, совпадающий со значением функции на этом входе;
– если вход не принадлежит области определения функции, то на выходе нет никакого результата.
Символом 
обозначают класс всех вычислимых функций из 
в 
. Например, если
, то
, где
1) , 
;
2) 
, 
;
3) 
;
4) 
.
Упражнение 1.1.Перечислить функции из
, где 
, 
.
Породимое множество (ПМ) – это множество, которое порождается каким либо исчислением (в том смысле, что порождаются все элементы породимого множества и не порождается ничего лишнего) [55]. ПМ является одним из фундаментальных понятий логики и теории алгоритмов. Пусть – породимое множество. Через 
обозначается класс всех породимых подмножеств множества .
Рассмотрим конструктивные объекты. Они естественным образом группируются в скопления, состоящие из схожих или однородных между собой объектов. Примером такого скопления может служить множество всех 
-слов, т.е. множество всех слов над алфавитом
. Такого рода скопления принято называть ансамблями.
Примечание 1.4.Понятие ансамбля является первичным, по отношению к понятию конструктивного объекта. Ибо объект может восприниматься как конструктивный только в рамках некоторого ансамбля.
Примечание 1.5.В случае, если алфавит 
является однобуквенным, то ансамбль - слов естественно отождествляется с натуральным рядом 
.
Упражнение 1.2.Представить в явном виде множество, состоящее из пяти представителей ансамбля -слов: Например,
– первые 5 нечетных натуральных чисел
Упражнение 1.3.Представить в явном виде множество, состоящее из пяти представителей ансамбля 
-слов, где
.
Рассмотрим всевозможные подмножества некоторого ансамбля 
.
Алгоритм 
называется разрешающим алгоритмом для множества ансамбля , если выполняются два условия:
10 Множество допустимых входов для совпадает с .
20. отвечает на все вопросы типа «Принадлежит ли 
множеству А?».
Какое-либо множество называется разрешимым, или распознаваемым, если оно содержится в некотором ансамбле и для него существует разрешающий алгоритм. Проблема отыскания такого алгоритма и называется проблемой разрешения для .
Утверждение 1.1.Множество разрешимо тогда и только тогда, когда его проблема разрешения является разрешимой, т.е. может быть в принципе решена, имеет решение.
Применим эти понятия к основаниям какой-либо математической дисциплины. Например, рассмотрим понятие доказательства в какой-либо логической системе. Фундаментальное требование к ней состоит в том, что множество всех доказательств этой системы было разрешимым множеством.
Понятия вычислимой функции, породимого и разрешимого множества тесно связаны друг с другом.