Числовые функции и алгоритмы их вычисления. Понятие вычислимой функции

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

Примеры числовых функций и алгоритмов их вычисления.

1. . В качестве алгоритма используется решение Эратосфена.

2. f(x,y)={ наибольший общий делитель чисел x и y}. Алгоритмом, вычисляющим эту функцию служит алгоритм Евклида.

3. f(x,y)={натуральное число ≤9, чья цифровая запись является x-м десятичным знаком в десятичном разложении числа π}. В качестве алгоритма можно взять квадратуру круга, радиуса 1 по правилу Симпсона.

4. f(x,y)={сумма x и y}. Алгоритмом служит известное правило сложения натуральных чисел, записанных в десятичной системе счисления.

5. f(x,y)={произведение x и y}. Алгоритм умножения, изучают в школьном курсе математики.

 

Разрешимы и неразрешимые множества. График вычислимой функции

Пусть А – подмножество множества натуральных чисел. Характеристической функцией множества А называется функция  определяемая условиями

Определение: Множество А называется разрешимым, если его характеристическая функция Х_А вычислима.

Теорема 1. Если А и В – разрешимые множества, то множества  разрешимы.

Полухарактеристическая функция множества А:

, такая что

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

Теорема 2. Всякое разрешимое множество полуразрешимо.

Теорема 3. (теорема Поста). Множество  разрешимо тогда и только тогда, когда оба множества А и N\A полуразрешимы.

Определение: Множество  называется перечислимым, если  или А является множеством значений некоторой вычислимой функции.

Теорема 4. Всякое перечислимое множество полуразрешимо.

Теорема 5. (теорема о графике). Частичная функция f из А в В вычислима тогда и только тогда, когда ее график Г_f перечислим.

 

Формальная теория вычислимости. Исходные функции. Частично рекурсивные функции. Рекурсивные предикаты

Простейшие функции:

Основные вычислительные операторы: оператор суперпозиции частичных функций, оператор примитивной рекурсии.

Примитивно рекурсивные функции. Примеры примитивно рекурсивных функций.

Оператор минимизации. Частично рекурсивные функции. Общерекурсивные функции.

Рекурсивные предикаты. Пусть Р – n- местный предикат на множестве натуральных чисел N. Функция  называется характеристической для предиката Р, если эта функция удовлетворяет условиям

Определение: Предикат Р называется рекурсивным (примитивно рекурсивным) если его характеристические функция общерекурсивна(примитивно рекурсивна).

 

Логические операции над предикатами. Ограниченные кванторы. Постановка функции в предикат. Кусочное задание функции

Над предикатами, заданными на множестве натуральных чисел N будем использовать операции отрицания (), конъюнкции(^), дизъюнкции(, импликации(→) и эквивалентности, а также ограниченные кванторы:

Например, запись  означает предикаты «для любого у такого, что y<z и ».

Теорема. Предикаты, которые можно получить из примитивно рекурсивных(или рекурсивных) с помощью логических операций и ограниченных кванторов также примитивно рекурсивны (соотв. рекурсивны).

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

Определение: функция  называется кусочно заданной, если она удовлетворяет условиям:

 

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

Теорема. Если функции  и предикаты  примитивно рекурсивны (рекурсивны), то функция  примитивно рекурсивна (рекурсивна).