23. Рекурсивные функции

Df.1.: Следующие числовые ф-ции называются простейшими:

1)Нуль ф-ция О(х)=0

2)Ф-ция следования S(x)=х+1

3)Ф-ция выбора аргумента Iⁿ_m(x₁, x₂, …, x_n)=x_m, 1≤m≤n.

Зам.: Каждая из простейших ф-ций является всюду определённой, т.е. значение ф-ции определено при любом допустимом наборе значений аргумента.

Рассмотрим 3 операции, позволяющие из данных ф-ций получать новые.

Df .2.: пусть дана ф-ция h(x₁, x₂, …, x_m) и пусть дано m-функций: g₁(x₁, x₂, …, x_n) g₂(x₁, x₂, …, x_n) …. g_m(x₁, x₂, …, x_n). Тогда говорят, что ф-ция f(x₁, x₂, …, x_n) получена с помощью операции супперпозиции или подстановки из ф-ций h,g₁,g₂,…,g_m, если выполн. условие: f(x₁, x₂, …, x_n)=h(g₁(x₁, x₂, …, x_n), g₂(x₁, x₂, …, x_n) , …., g_m(x₁, x₂, …, x_n)).

Зам: Можно показать, что, если операция суперпозиции применяется к всюду определённым ф-циям, то в результате получаем ф-цию всюду определённую.

Df.3.:Пусть даны ф-ции g(x₁, x₂, …, x_n) и h(x₁, x₂, …, x_n,x_n+1,x_n+2), где n≥1. Тогда говорят, что ф-ция f(x₁, x₂, …, x_n,x_n+1) получена с помощью операции примитивной рекурсии из ф-ций g и h, если выполняются условия: f(x₁, x₂, …, x_n,0)= g(x₁, x₂, …, x_n), f(x₁, x₂, …, x_n,у+1)= h(x₁, x₂, …, x_n, у, f(x₁, x₂, …, x_n,,у)).

Зам:Если n=0, то схема примитивной рекурсии имеет вид: f(0)=k, k-const; f(y+1)=h(y,f(y)).

Зам: Можно показать, что если операция примитивной рекурсии применяется к всюду определ1нным ф-циям, то мы получаем всюду определённую ф-цию.

Df.4.: Ф-ция называется примитивно-рекурсивной, если её можно получить из простейших с помощью конечного числа раз применения операций суперпозиции и примитивной рекурсии.

Зам: В силу, сделанных ранее, замечаний каждая примитивно-рекурсивная ф-ция является всюду определённой.

Df.5.: Пусть дана ф-ция g(x₁, x₂, …, x_n,x_n+1).Тогда говорят, что ф-ция f(x₁, x₂, …, x_n) получена с помощью операции минимизации из ф-ции g, если её значением является наименьшее у, удовлетворяющее следующим требованиям:

1) g(x₁, x₂, …, x_n,у)=0

2)для каждого 0≤t≤у значения g(x₁, x₂, …, x_n,t) определено и больше 0.

Если хотя бы одно из этих условий не выполняется, то значение у ф-ции f не определено.

Df.6.: Ф-ция называется частично рекурсивной, если её можно получить из простейших с помощью конечного числа раз применения операций суперпозиции, примитивной рекурсии, минимизации.

Df.7.: Всюду определённая частично рекурсивная ф-ция называется общерекурсивной.

Теор.1: Числовая ф-ция является вычислимой по Тьюрингу  она частично рекурсивна.

Зам.: Теорема 1 утверждает эквивалентность 2х различных строгих определений алгоритма: в форме программ МТ, и в форме рекурсивных ф-ций.

24. Алгоритмически неразрешимые проблемы

Df.1.: Массовой проблемой называется бесконечный класс однотипных задач.

Df.2.: Массовая проблема называется алгоритмически неразрешимой, если не существует единого алгоритма, с помощью которого можно решить любую задачу из данной проблемы.

Зам: Алгоритмическая неразрешимость не означает, что нельзя решить никакую задачу из данной проблемы. Алгоритмическая неразрешимость означает только то, что класс задач, составляющих данную проблему, достаточно широк и поэтому нет единого алгоритма для решения всех задач данной проблемы. Алгоритмически неразрешимые проблемы имеются во многих областях математики. Нам уже известна одна алгоритмически неразрешимая проблема-это проблема разрешения в логике предикатов: не существует единого алгоритма, который для произвольной логики предикатов определял бы «является ли данная формулы выполнимой».

В алгебре известна проблема представимости матриц.

Её суть в следующем: имеется m-квадратных матриц А₁, А₂,…, А_m одного и того же размера n. Для произвольной квадратной матрицы А того же размера требуется установить «можно ли её представить в виде произведения нескольких матриц из А₁, А₂,…, А_m ». В 1951 году советский математик А.А.Марков доказал, что эта проблема алгоритмически неразрешима.

Алгоритмически неразрешимые проблемы имеются и в самой теории алгоритмов. Одна из них – проблема остановки МТ: Для произвольной МТ и произвольной начальной конфигурации требуется установить «применима ли данная машина к данной начальной конфигурации».

Отметим, что в математике имеются массовые проблемы, для которых пока не установлено разрешимо алгоритмически или нет. Долгое время (70 лет) в таком положении оставалась десятая проблема Гильберта. Её суть в следующем: для произвольного алгебраического уравнения с целыми коэффициентами и произвольным числом неизвестных требуется установить имеет ли оно целое решение. Только в 1971 году молодой ленинградский математик Ю.Матиясевич доказал, что проблема алгоритмически неразрешима.