Научная электронная библиотека
Монографии, изданные в издательстве Российской Академии Естествознания

1.4. Вычислимые функции и породимые множества. Перечислимые множества и разрешимые множества

Вычислимая функция – это функция, которая вычисляется каким-либо алгоритмом.

Термин «вычисляется» означает следующее:

– если на вход алгоритма подано значение аргумента из области определения функции, то на выходе получается результат, совпадающий со значением функции на этом входе;

– если вход не принадлежит области определения функции, то на выходе нет никакого результата.

Символом  обозначают класс всех вычислимых функций из  в . Например, если, то, где

1) , ;

2) ;

3) ;

4) .

Упражнение 1.1.Перечислить функции из , где , .

Породимое множество (ПМ) – это множество, которое порождается каким либо исчислением (в том смысле, что порождаются все элементы породимого множества и не порождается ничего лишнего) [55]. ПМ является одним из фундаментальных понятий логики и теории алгоритмов. Пусть  – породимое множество. Через  обозначается класс всех породимых подмножеств множества .

Рассмотрим конструктивные объекты. Они естественным образом группируются в скопления, состоящие из схожих или однородных между собой объектов. Примером такого скопления может служить множество всех -слов, т.е. множество всех слов над алфавитом . Такого рода скопления принято называть ансамблями.

Примечание 1.4.Понятие ансамбля является первичным, по отношению к понятию конструктивного объекта. Ибо объект может восприниматься как конструктивный только в рамках некоторого ансамбля.

Примечание 1.5.В случае, если алфавит является однобуквенным, то ансамбль - слов естественно отождествляется с натуральным рядом .

Упражнение 1.2.Представить в явном виде множество, состоящее из пяти представителей ансамбля -слов: Например,

– первые 5 нечетных натуральных чисел

Упражнение 1.3.Представить в явном виде множество, состоящее из пяти представителей ансамбля -слов, где .

Рассмотрим всевозможные подмножества некоторого ансамбля .

Алгоритм называется разрешающим алгоритмом для множества  ансамбля , если выполняются два условия:

10 Множество допустимых входов для  совпадает с .

20 отвечает на все вопросы типа «Принадлежит ли множеству А?».

Какое-либо множество  называется разрешимым, или распознаваемым, если оно содержится в некотором ансамбле и для него существует разрешающий алгоритм. Проблема отыскания такого алгоритма и называется проблемой разрешения для .

Утверждение 1.1.Множество разрешимо тогда и только тогда, когда его проблема разрешения является разрешимой, т.е. может быть в принципе решена, имеет решение.

Применим эти понятия к основаниям какой-либо математической дисциплины. Например, рассмотрим понятие доказательства в какой-либо логической системе. Фундаментальное требование к ней состоит в том, что множество всех доказательств этой системы было разрешимым множеством.

Понятия вычислимой функции, породимого и разрешимого множества тесно связаны друг с другом.


Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1,674