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