test3 var4 s otvetami

Фамилия _______________________ 2007 год, группа К3-___________ Вар.4

Вопрос 1. Теоремы и доказательства (0,5 балла) Уточните формулировку (обведите ключевое слово) и приведите строгое и подробное доказательство теоремы

Общерекурсивные функции
возможно эффективно перечислить
не поддаются эффективному перечислению



На уровне тезисов (0.1 балла можно поставить, если полного док-ва студент так и не вспомнил)):
Из тезиса Чёрча: всякая арифметическая функция, вычислимая в обычном смысле (ВАФ) есть рекурсивная функция (РФ), а всякая частичная арифметическая функция, вычислимая в обычном смысле (ЧВАФ), есть частично рекурсивная функция (ЧРФ). Известно (на основании теоремы Тьюринга), что ВАФ эффективно не перечислимы. Отсюда следует, что и РФ эффективно не перечислимы (так как ВАФ эффективно не перечислимы, а ВАФ есть РФ).

Строгое (по сути, копия док-ва теоремы Тьюринга) (0,5 балла)
Допустим, что множество рекурсивных функций n-переменных эффективно перечислимо.
Тогда существует алгоритм, по которому их можно перечислить. Применим этот алгоритм. Получим последовательность
F0(x1,,xn), F1(x1,,xn),.. Fn(x1,,xn),..
Построим диагональную функцию:

Fx1(x1,,xn)+1, при x1==xn
G(x1,,xn)=
0, в противном случае

Процедура вычисления G. Для любых значений x,y,z мы можем сначала провести операцию сравнения, и затем, если x=y=z, отыскать функцию Fx. Это вполне рекурсивная операция (сравнение аргументов). Если результат сравнения отрицательный (ложь), значение функции G(x1,,xn)=0. Если результат сравнения положительный (истина), далее можем применить к ней алгоритм вычисления функции Fx(x,x,x) в заданной точке. Такой алгоритм существует в силу рекурсивности функций вида Fi(x1,,xn). Прибавление к результату вычисления единички есть тривиальная рекурсивная функция операция. Т.о. видно, что эта диагональная функция будет тоже рекурсивной.
Раз построенная функция принадлежит к множеству рекурсивных функций, то она должна быть среди ранее эффективно перечисленных функций, но по построению она не может быть среди них, так как от каждой функции она отличается хотя бы в одной точке. Получили противоречие, следовательно, рекурсивные функции нельзя эффективно перечислить.



Вопрос 2. Принадлежность функций к определенным классам (1 балл) (ОЦЕНКА: пять подвопросов по 0.2 балла). Укажите ВСЕ (!!!) множества, к которым принадлежит функция (поставьте в соотв. ячейках «+»). Если функция данному множеству не принадлежит, ставьте «-». Хотя бы одна ошибка в строке зануляет результат по подвопросу.
Функция
Примитивно-рекурсивная
Рекурсивная
Частично-рекурсивная
Нерекурсивная

= x-y, если x > y+2
F (x, y) = 2y-х, если x< y
= (x+y)/2 если x=y
+
+
+
-

= x, если машина Тьюринга Тх не
F(x) остановится на чистой ленте
= 1 иначе
-
-
-
+


E(x)= (y[y+x=5]

-
-
+
-

Функция F(x), заданная через функцию E(x) из предыдущего задания
F(x)=(y[E(y)=3]
+
+
+
-

F(x) = g(x) если x>20
= 5x + p(x) в остальных случаях
где g(x) -рекурсивная, но не примитивно-рекурсивная функция, а p(x) - примитивно-рекурсивная функция
-
+
+
-



Вопрос 3. Вычисления и определения (0,5 балла)

Запишите через базисные операторы обращение функции f(x)=s(x) и найдите значение полученной функции в точках 0,1,2,3
x-1 при x>0
s-1(x) =
·y(f(y)=x) =
не опр при x=0
((0)=не опр, ((1)=0, ((2)=1, ((3)=2

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


f(x)= 1 если машина Тьюринга Tx останавливается на чистой ленте
f(x)= 0 если машина Тьюринга Tx не останавливается на чистой ленте


Поставьте в соответствующих колонках на следующих двух строчках значки +/ - или словами «да» / «нет». В последней строчке укажите мощность множества с помощью натурального или трансфинитного числа


Нерекурсивные функции
Частично-рекурсивные функции
Общерекурсивные функции
Примитивно-рекурсивные функции

Счетность
-
+
+
+

Эффективная перечислимость
-
+
-
+

Мощность
Алеф
Алеф-ноль
Алеф-ноль
Алеф-ноль






Заголовок 1 Заголовок 2 Заголовок 3 Заголовок 4 Заголовок 515

Приложенные файлы

  • doc 19021695
    Размер файла: 60 kB Загрузок: 0

Добавить комментарий