Задачи по теории алгоритмов. Выпуск 1.

 

Г.П. Гаврилов. А.А. Сапоженко. Сборник задач по дискретной математике.

 

№ 2.1

Применить операцию примитивной рекурсии к функциям и по переменным и . Функцию записать в «аналитической» форме.

 

1)                     

Решение.

Схема примитивной рекурсии:

,

.

 

- аналитическая форма.

 

2)                    

Решение.

, где .

 

3)                    

Решение.

.

 

4)                    

Решение.

 

№2.6

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

 

е.                  

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

Зафиксируем значения .

- примитивно рекурсивная функция (относительно );

- примитивно рекурсивная функция (относительно ).

Функцию мы обозначили через .

Функция получается из функций и примитивной рекурсией (относительно ), при помощи операции примитивной рекурсии, следовательно, также примитивно рекурсивна (относительно ).

:

- примитивно рекурсивная функция;

- примитивно рекурсивная функция (относительно );

- примитивно рекурсивная функция (относительно ).

 

ж.                

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

Зафиксируем значения .

- примитивно рекурсивная функция (относительно );

- примитивно рекурсивная функция (относительно ).

Функцию мы обозначили через .

Функция получается из функций и примитивной рекурсией (относительно ), при помощи операции примитивной рекурсии, следовательно, также примитивно рекурсивна (относительно ).

:

- примитивно рекурсивная функция;

- примитивно рекурсивная функция (относительно );

- примитивно рекурсивная функция (относительно ).

 

з.                  

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

Зафиксируем значения .

- примитивно рекурсивная функция (относительно );

- примитивно рекурсивная функция (относительно ).

Через мы обозначили функцию .

 

и.                 

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

Зафиксируем значения .

- примитивно рекурсивная функция (относительно );

- примитивно рекурсивная функция (относительно ).

Через мы обозначили функцию .

 

И.А. Лавров, Л.Д. Максимова Задачи о теории множеств , математической логике, теории алгоритмов.

 

§1 Рекурсивные функции

 

№1

Доказать, что любая примитивно рекурсивная функция определена.

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

Пусть - примитивно рекурсивная функция. Следовательно, по определению примитивно рекурсивной функции, функция получается из простейших функций при помощи конечного числа операций примитивной рекурсии и суперпозиции. Функции - являются всюду определенными. Так как операции примитивной рекурсии и суперпозиции, примененные к всюду определенным функциям, дают в результате всюду определенные функции, то - является также всюду определенной.

 

№2

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

а.                   (перестановка аргументов)

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

 

б.                  (циклическая перестановка аргументов)

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

 

в.                  (введение фиктивного аргумента)

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

 

г.                   (отождествление аргументов)

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

 

№3

Какие функции получаются из простейших с помощью лишь суперпозиций?

Ответ: Элементарные функции относительно нуль-функций и функций следования.

 

№4

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

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

Пусть функция получена из и с помощью суперпозиций и примитивной рекурсии. Тогда и .

 

№5

Доказать, что следующие функции примитивно рекурсивны:

в.                 

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

 

г.                  

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

- примитивно рекурсивная функция.

 

д.                  (здесь )

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

- примитивно рекурсивная функция.

- примитивно рекурсивная функция. мы обозначили через

 

е.                   (здесь )

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

 

№6

Какая функция получается из и с помощью схемы примитивной рекурсии:

а.                  

Решение.

 

б.                 

Решение.

 

№7

Доказать, что следующие функции примитивно рекурсивны:

в.                 

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

 

е.                  

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

- примитивно рекурсивная функция;

- примитивно рекурсивная функция;

- примитивно рекурсивная функция;

- примитивно рекурсивная функция;

- примитивно рекурсивная функция;

- примитивно рекурсивная функция;

- примитивно рекурсивная функция;

- примитивно рекурсивная функция;

- примитивно рекурсивная функция;

 

§2 Машины Тьюринга

 

№1

Какую функцию вычисляет машина со следующей программой команд:

Решение.

Пусть .

Машинный код для имеет вид:

……………

Машинный код для : .

 

№2

Пусть машина имеет следующую программу: . Какие функции вычисляет эта машина?

Решение.

Пусть .

Машинный код для имеет вид:

Машинный код для :

- ?

Пусть .

Машинный код для имеет вид:

Машинный код для :

Машинный код для : .

 

№3

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

Решение.

Правильно вычисляет:

a)                  Если , то

b)                  Если , то машина начинает работать со слова работает бесконечно.

Просто вычисляет:

a)                  Если , то машина Тьюринга останавливается, т.е. перерабатывает слово в слово содержащее вхождений символа 1.

Смотреть задачу 1.

 

№4

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

Решение.

 

№5

Построить следующие машины Тьюринга.

А. Перенос нуля:

Решение.

…………… …………..

Решение из Мальцева.

……………

. Правый сдвиг:

Решение.

№8 Построить машины Тьюринга для правильного вычисления функций:

а) x+y

 

Нормальные алгоритмы Маркова

Пример1:

Пусть задан алфавит , , , где - пустое слово.

Этот алгорифм преобразует всякое слово в , содержащее хотя бы 1 вхождение буквы в слово, которое получается вычеркиванием в самого левого вхождения буквы ; пустое слово алгорифма преобразует в самого себя; наконец алгорифм неприменим к непустым словам не содержащим вхождение буквы .

Пример2:

, , , где - пустое слово.

Этот нормальный алгорифм при любом , .