Лемма (о декартовом произведении)., Замечания и упражнения - Рекурсивные функции
Если А - эффективное множество, то
Для любого эффективного множества B AB эффективно (и, следовательно, любое декартово произведение A1A2...Аn эффективных множествэффективно);
Множество A*, A*=N N AN, всех конечных последовательностей элементов А эффективно счетно.
Если B - эффективно счетно, то утверждение тривиально следует из показанного в лекции 1 факта эффективной счетности NN. Если же B - конечно, то пусть f1:NA - эффективное кодирование, а f2 - 1-1 конечное отображение N в B, B={f(1),...,f(k)}. Тогда
F(n)= < f1(n div k), f2(n mod k) >
Где n div k, n mod k - соответственно, целая часть и остаток от деления n на k, -1-1 отображение N на AB.
По основной теореме арифметики, для любого числа n, n N, существует единственное разложение на произведение степеней простых чисел :
N=p(1)n(1)* p(2)n(2)*... *p(k)n(k)=i=1,k p(i)n(i)
(где p(i) - i-ое простое число), что и дает требуемое 1-1 отображение N на N*:n<n(1),n(2),...,n(k)> и, следовательно, на A*.
Замечания и упражнения
Закончите доказательство, построив FD-программы вычисления функций n div k, n mod k и разложения числа на простые множители и показав, тем самым, эффективность выбранных кодировок.
Взятое нами из процедурного программирования понятие (конструктивного) типа данных (в терминологии объектного программирования - классов, в терминологии универсальной алгебры - алгебраических систем) подразумевает рассмотрениенекоторого множества А значений данных Совместно со средствами их обработки, т. е. наличия некоторых Вычислимых функций на А. Если f: AN эффективное кодирование и g:AA, то g естественно считать вычислимой тогда и только тогда, когда вычислима соответствующая функция на кодах - образ g при отображении f, т. е.функция f(x)fg(x).
Покажите, что для любого эффективного счетного множества A
Операция конкатенации ( соединения, приписывания ) последовательностей вычислима;
Операции
Элемент_n-ки(<a(1),a(2),...,a(n)>,i)=a(i), i N,
Элемент_последовательности(<a(1),a(2),...,a(n)>,i)=a(i), i N,
Взятия проекции AN, для любого n N, и A* на заданную координату вычислима.
С) Заметим, что операции взятия проекции можно трактовать как операции "выборки компоненты по индексу", что открывает нам путь к неявному употреблению Статических и Динамических массивов в языке FD-программ. Действительно, можно завести обычную (числовую) переменную - скажем, с именем ArrayCode, полагая, что она содержит код некоторой конечной числовой последовательности Array и моделируя нужные операции над элементами массива функциями над их кодами. Скажем, присваивание ArrayCode:= ArrayCode*pI ,будет моделировать присваивание Array[i]:=S(Array[i]). Таким образом, мы можем без опасения расширить синтаксис FD-программ введением индексных переменных, полагая операторы работы с массивами просто иной формой записи операторов работы с их кодами.
Приступим теперь к построению нумерации программ. FD-программы, по определению, есть конечные последовательности пар вида <k: op> k, k N - числовая метка, а op - оператор. Мы уже научились строить кодирования конечных последовательностей и пар, для этого достаточно построить эффективное кодирование всех возможных операторов.
Каждый оператор однозначно характеризуется следующей парой - Тип (название) оператора (stop, if-then-else, приваивания) и Список параметров оператора <y1, y2,..., yM>, среди которых - метки операторов, переменные, функциональные и логические выражения. Оператор start стоит всегда в начале FD-программы и может быть задан только списком своих параметров. Типам других операторов нетрудно сопоставить числовые коды - скажем, перенумеровать в приведенном выше порядке. Остается закодировать числами каждое из возможных значений параметров оператора.
Метки операторов не нуждаются в особом кодировании - это уже натуральные числа. Без ограничения общности, можно полагать, что каждая из переменных имеет вид xI, iN-поставим каждой из переменных xI в соответствие ее номерi. Наконец, перенумеруем все функциональные и предикатные символы (скажем, ноль-функцию 0 - нулем, функцию следования S - единицей и предикат равенства - двойкой) и закодируем функциональные и логические выражения, имеющие вид f(x1, x2,..., xN) кодом пары <i, j>, где i - номер функционального или предикатного символа f, j - код n-ки < j1, j2,..., jN >, j1, j2,..., jN - коды имен переменных x1, x2,..., xN.
(конец доказательства)
Замечание. Внимательный к деталям читатель, вероятно, заметил, что для того, чтобы не перегружать изложение деталями, мы немного упростили синтаксис FD - программ, разрешая переход на несуществующие метки - что, с точки зрения семантики, естественно трактовать как "ошибку программы", т. е. неопределенность значения вычисляемой функции.
Подчеркнем снова, что для построенного кодирования существует не только алгоритм нахождения номера программы по ее тексту, но и обратный алгоритм, восстанавливающий полный синтаксис каждой программы по ее номеру. В теории алгоритмов такие нумерации программ называют геделевыми (в честь знаменитого немецкого логика Курта Геделя, впервые, с целью вложения логики в арифметику, применившим такие нумерации для кодирования логических формул). В качественной теории алгоритмов нас интересует лишь наличие либо отсутствие, но не конкретный вид алгоритмов, поэтому мы далее мы можем допускать вольность, отождествляя программы и их геделевы номера и говоря, например, о программе i вместо - программа с геделевым номером i. Особо отметим, что, в любом случае, наши результаты не будут зависеть от выбора конкретной геделевой нумерации.
Поскольку каждая программа вычисляет некоторую функцию, введенная нумерация программ порождает некоторую нумерацию функций. Через Pk обозначим программу с кодом k, а через K - (одноместную) функцию, вычисляемую программойPk (для n-местных функций будем употреблять обозначение K(n) ). Очевидно,
1, 2, 3,....
Некоторая нумерация (перечисление) Всех вычислимых функций, которую мы также назовем Геделевой.
Правда, в отличие от нумерации программ, у нас нет никаких оснований считать эту нумерацию эффективным кодированием. Заметим пока, что, как минимум, это нумерацияне взаимно-однозначна. Действительно, мы кодировали синтаксис программ, и любые синтаксически различные программы имеют разные коды. С другой стороны, каждая вычислимая функция вычисляется бесконечным классом программ. Скажем, если P - одна такая программа, то программа, полученная дописыванием к ней "фиктивного" оператора x:=x, вычисляет ту же функцию.
Однако, как показывают следующие результаты, полученная таким образом нумерация обладает рядом фундаментальных и практически полезных свойств.
Пусть А - счетный класс одноместных (не обязательно - всюду определенных) функций,
A={f1, f2,..., fI,...}
Даже если Каждая из функций fI вычислима (некоторым алгоритмом PI), это не гарантирует существование Единого алгоритма вычисления Всех функций. Назовем класс A Равномерно перечислимым, Если это действительно так, т. е. существует двуместная вычислимая функция F, что класс А состоит в точности из функций вида F(n, x), для некоторых n из N; функцию F назовем универсальной Функцией класса A. Ясно (пусть пока, быть может, лишь на интуитивном уровне), что nF(n, x) - эффективная нумерация класса А, которую мы также назовем равномерной.
Наша ближайшая цель - показать, что
Определенная нами геделева нумерация вычислимых функций равномерна (теорема об универсальной функции),
Она уникальна по отношению к другим равномерным нумерациям - по номеру вычислимой функции в заданной равномерной нумерации можно эффективно найти его номер в геделевой нумерации (теорема о параметризации).
Более точные (и программистские по духу) формулировки и пояснения следует далее. По сложившейся традиции, начнем с обсуждения второго результата.
Похожие статьи
-
Теория алгоритмов. Основные результаты, Программы как данные - Рекурсивные функции
Вместо предисловия . Сверх-идеей любой научной теории можно считать перевод знания из сферы подсознательного, интуитивногов осознанную, точную и...
-
Кодирование программ - Рекурсивные функции
(Эффективной) Нумерацией , или Перечислением множества А назовем Произвольное эффективное отображение f :N A, f(N)=A; таким образом, мы допускаем, что в...
-
Еще одним подходом к проблеме формализации алгоритма являются, так называемые, рекурсивные функции. Исторически этот подход возник первым, поэтому в...
-
Теорема об универсальной функции - Рекурсивные функции
Для любого n, nN, универсальная функция u(n) вычислима. Доказательство. При доказательстве мы можем ограничиться случаем N=1. Действительно, программу,...
-
Теорема о параметризации - Рекурсивные функции
Одно и то же выражение может порождать несколько разных функций, от разного числа аргументов. Так, обычное арифметическое выражение xK можно считать...
-
ФУНКЦИИ, Основные понятия - Свойства функций
Основные понятия При изучении различного рода явлений приходится иметь дело с совокупностью переменных величин, которые связаны между собой таким...
-
Перечислимость. - Рекурсивные функции
В предыдущем упражнении мы показали, что операции алгебры логики не выводят за пределы разрешимых предикатов. Но полный язык математической логики, как...
-
Неразрешимость - Рекурсивные функции
Сейчас же займемся более важной задачей - определением принципиальных границ вычислимости. Если теоремы о параметризации, универсальнойфункциии...
-
Синтаксис и семантика. Теорема Райса - Рекурсивные функции
Попробуем теперь проанализировать круг проблем, неразрешимость которых доказана в предыдущем пункте. Общим для них является то, что по кодам, т. е....
-
Неразрешимость - методы доказательства, Диагонализация - Рекурсивные функции
Основными методами при доказательстве теорем о не существовании алгоритмовявляются - прямой метод Диагонализации, восходящий к "диагональному"...
-
Теорема о параметризации., Универсальные функции - Рекурсивные функции
Любую часть x1,x2,...,xn входных значений можно породить программно, более того - существует алгоритм, который генерирует по x1,x2,...,xn текст...
-
ПОНЯТИЕ ФУНКЦИИ Если некоторому множеству значений поставлено по определенному правилу F во взаимнооднозначное соответствие некоторое множество, то тогда...
-
Принцип сходимости, Предел функции. Теорема Гейне - Свойства функций
Рассмотрим вопрос о существовании пределов последовательностей концевых точек бесконечной системы промежутков, вложенных друг в друга. Лемма Кантора ....
-
Сходящиеся последовательности, Основные свойства сходящихся последовательностей: - Свойства функций
Говорят, что Последовательность сходится, если существует число такое, что для любого существует такое , что для любого , выполняется неравенство: ....
-
Теорема Клини о нормальной форме - Рекурсивные функции
Существуютпримитивнорекурсивныефункция u и примитивно разрешимый предикат T такие, что e, x ( E(x)=p ( k [T(e, x,k)])). В частности, e, x ( E(x) k T(e,...
-
Понятие числовой последовательности - Свойства функций
Числовой последовательностью называется числовая функция, определенная на множестве натуральных чисел . Если функцию задать на множестве натуральных...
-
Теорема: Для того, чтобы ограниченная на сегменте функция была интегрируемой на этом сегменте, необходимо и достаточно, чтобы для любого нашлось такое...
-
Линейная функция - Конформное отображение
Определение 2. Функция вида: , где - фиксированные комплексные числа, называется линейной. Определение 3. Отображение, осуществимое линейной функцией...
-
Функции и ее свойства - Методы решения системы линейных уравнений
В современной математике понятие множества является одним из основных. Универсальность этого понятия в том, что под него можно подвести любую...
-
На уровне общества для описания поведения потребителей вводится целевая функция потребления. Целевая функция потребления - функция, выражающая уровень...
-
Ответ: Функция f называется четной если для любого х из ее области определения f(-x)=f(x) График четной функции симметричен относительно оси ординат....
-
Сложение, вычитание, умножение комплексных чисел в алгебраической форме производят по правилам соответствующих действий над многочленами. Четность и...
-
Сводимость - Рекурсивные функции
Помимо построения контрпримеров, в математических доказательствах часто используют метод сведения, который на практике мы часто формулируем в виде...
-
Теорема 1. Предел постоянной равен самой постоянной. . Доказательство. f(x)=с, докажем, что . Возьмем произвольное e>0. В качестве d можно взять любое...
-
Бесконечные пределы - Свойства функций
Функция называется Бесконечно малой при (или, или ) если для сколь угодно малого положительного числа найдется такое положительное число (), что для всех...
-
Односторонние пределы, Пределы на бесконечности - Свойства функций
В определении предела функции предполагалось, что произвольным образом. Если при вычислении предела функции при считать, что, то получают Односторонний...
-
Теорема: Непрерывная на сегменте функция интегрируема на этом сегменте. Теорема: Если функция определена и ограничена на сегменте, и если для любого...
-
Ответ: уравнение ax2+bx+c=0. Где а не равно нулю, называется квадратным. Чтобы его решить нужно вычислить дискриминант. D=b2 -4ac и сравнить его с нулем....
-
Выделим случай, когда входной сигнал X ( T ) является элементарной функцией 1( T ). Реакцию системы на воздействие 1( T ) можно компактно: [1] Где...
-
Логарифм алгебраический угол число Формулы двойного аргумента Sin 2x=2sin xЧcos x Cos 2x=cosІx-sinІx Cos 2x=1-2sinІx Cos 2x=2cosІx-1 Обратные...
-
Пусть на некотором отрезке [a, b] задана кусочно-монотонная функция f(x). Покажем, что данную функцию в точках ее непрерывности можно представить в виде...
-
ПРАВАЯ И ЛЕВАЯ ТРОЙКИ ВЕКТОРОВ Линейно независимые векторы, и образуют Правую Тройку векторов, если они имеют такую же ориентацию, как соответственно...
-
СКАЛЯРНОЕ ПРОИЗВЕДЕНИЕ ВЕКТОРОВ Скалярным произведением двух векторов иназывается число S =|| || сos (). Эта операция обозначается. В частности,...
-
1. Нормальные алгоритмы Маркова Для формализации понятия алгоритма российский математик А. А. Марков предложил использовать ассоциативные исчисления....
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ: ОСНОВНАЯ СХЕМА - Задача коммивояжера
Пусть - конечное множество и - вещественно-значная функция на нем; требуется найти минимум этой функции и элемент множества, на котором этот минимум...
-
Счетные и несчетные множества - Методы решения системы линейных уравнений
Пусть, например, А и В Ї некоторые множества. Тогда их возможные взаимоотношения можно рассмотреть в виде таблицы: Диаграмма Венна Диаграмма Венна...
-
Некоторые особенности решения задач нелинейного программирования - Экономико-математические методы
Для решения ЗНП существенно знать: 1) выпукло или не выпукло множество допустимых решений задачи; 2) является ли целевая функция выпуклой или вогнутой...
-
Бесконечный предел, Замечательные пределы - Свойства функций
Наряду с бесконечно малыми существуют и бесконечно большие величины, являющиеся обратными по отношению к бесконечно малым. Поэтому является бесконечно...
-
Пусть Dl, r() соответственно левые (правые) границы интервалов I, отвечающих на криволинейной трапеции ОИО значениям 0< < 1. Тогда интересующая нас...
-
Вариации коэффициентов целевой функции ЗЛП приводят к изменению направления вектора градиента. Так как при этом не затрагивается допустимое множество, то...
Лемма (о декартовом произведении)., Замечания и упражнения - Рекурсивные функции