Структуры данных и модели вычислений



             

Частично-рекурсивные функции


Пытаясь выяснить содержание интуитивного понятия вычислимой функции, А.Черч в 1936 году рассмотрел класс так называемых рекурсивных функций, а Клини расширил его до класса частично-рекурсивных функций. В то же время впервые была высказана естественно-научная гипотеза о том, что интуитивное понятие вычислимой частичной функции совпадает с понятием частично рекурсивной функции. Эту гипотезу называют тезисом Черча. Здесь мы напомним понятие частично-рекурсивной функции и покажем, что любая частично-рекурсивная функция вычислима по Тьюрингу. Набор аргументов

обозначим через .

Функция называется суперпозицией -местных функций , и -местной функции , если

Говорят, что -местная функция

получена примитивной рекурсией из -местной функции

и -местной функции , если

Говорят, что -местная функция

получена минимизацией из -местной функции , если

Часто обозначают через .

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

Числовая функция называется частично рекурсивной, если она является одной из базисных функций:

а) (при всех ),

б) (при всех ),

в)

или получена из них с помощью конечного числа применений суперпозиции, примитивной рекурсии и минимизации.

Теорема.

Любая частично-рекурсивная функция вычислима по Тьюрингу.

Доказательство теоремы заключено в следующих четырех леммах, с использованием унарного кодирования чисел.

Лемма 1 (о базисных функциях).

Базисные функции , , вычислимы по Тьюрингу.

Действительно, функцию вычисляет программа , функцию — программа , функцию — программа .

Лемма 2 (о суперпозиции).

Если функции и

вычислимы, соответственно, программами , и , то функцию

вычисляет программа:

Доказательство.

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




Содержание  Назад  Вперед