Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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

Допустим противное, то есть пусть - наименьший в L элемент. Тогда _Ø), где с_Ø – нигде неопределенная функция.

Следовательно, Ø и (с_Ø).

Возьмем всюду определенную функцию h. Ясно, что с_Ø≤_mh.

С одной стороны, (с_Ø) – наименьший элемент, то есть с_Ø≤_mh; с другой стороны с_Ø≤_mh.

Получили противоречие, то есть в L наименьшего элемента нет. Ч.т.д.

Утверждение 3.2: m-степень, содержащая универсальную функцию, является наибольшей в L.

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

Пусть Ψ – универсальная функция, а α – произвольная ЧРФ. Так как α – ЧРФ, то найдется такое число х₀, что α=φ₀.

Покажем, что . В качестве сводящей возмем функцию f(x₀,y). Тогда из определения Ψ вытекает, что , где , то есть .

Таким образом, - наибольшая в L. Ч.т.д.

Введем обозначение: .

Ясно, что .

Утверждение 3.3: с_Ø и множество всех функций вида c_n(x) и только они образуют множество минимальных в L элементов.

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

Из утверждения 3.1. следует, что с_Ø – минимальный в L элемент.

Возьмем произвольную функцию c_n(x).

Пусть .

Ясно, что { }, кроме того α – всюду определенная функция, так как иначе , следовательно, .

Пусть теперь минимальный в L элемент, отличный от с_Ø и от всех с_n, тогда определена в некоторой точке х₀; пусть , имеем , где , то есть, . Получили противоречие. Ч.т.д. [1,2]

2. Практическая часть.

§1. Идеалы полурешетки m-степеней частично рекурсивных функций

Определение:

Идеалом полурешетки L назовем всякое подмножество I отличное от Ø, удовлетворяющее следующим условиям:

1. ;

2. .

Идеал называется главным, если он содержит наибольший элемент.

Рассмотрим множество всех m-степеней частичных характеристических функций, то есть:

Н={ }.

Предположение 4.1:

Множество Н является главным идеалом полурешетки L.

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

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

Определим множество А В:

{ }.

Докажем, что .

Будем пользоваться определением 15 для доказательства данного равенства.

Рассмотрим 4 случая.

1. если x=2t,

И если x=2t,

1. Если x=2t,

И если x=2t,

1. Если x=2t+1,

И если x=2t+1,

1. Если x=2t+1,

И если x=2t+1,

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

.

1. Пусть . По определению m-сводимости из следует, что существует рекурсивная функция f такая, что: , откуда . Из утверждения 2.2 и того, что всякое р.п. множество m-сводимо к креативному следует, что: - наибольший элемент в Н, где k – креативно.

Тогда Н – главный идеал полурешетки L. Ч.т.д.

Рассмотрим множество всех m-степеней рекурсивных функций, то есть:

М={ }.

Предположение 4.2: Данное множество М является главным идеалом полурешетки L.

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

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

2. Если , откуда существует рекурсивная функция h, такая, что , где также рекурсивная функция. Далее, посредством f(x) для любой рекурсивной функции f(x), отсюда - наибольший элемент в М.

М – главный идеал полурешетки L. Ч.т.д.

Литература

1. Дегтев А.Н. Сводимость частично-рекурсивных функций. – Сибирский математический журнал, 1975 т. 16, №5, с. 970-988.

2. Ершов Ю.Л. Теория нумераций. – М.: Наука, 1977.

3. Кагленд Н. Вычислимость. Введение в теорию рекурсивных функций. – М.: Мир, 1983.

4. Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: Наука, 1965.

5. Поляков Е.А., Розинас М.Г. Теория алгоритмов. – Иваново: ИвГУ, 1976.

6. Поляков Е.А., Маринина Н.В. Теория алгоритмов. – Шуя: ШГПУ, 2004.

7. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. – М.: Мир, 1972.

Характеристики

Список файлов ответов (шпаргалок)