Математическая логика и теория алгоритмов

Содержание
Задание № 1 3
Задание № 2 3
Задание № 3 4
Задание № 4 4
Задание № 5 5
Задание № 6 6
Задание № 7 9
Список использованных источников 12

-

Контрольная работа
для студентов заочной формы обучения

Направление «Информатика и вычислительная техника»

Профиль: Автоматизированные системы обработки информации и управления.

Дисциплина: Математическая логика и теория алгоритмов.

Вариант 2


Профессор Кожухов С.Ф.

-

Задание № 1
Известно, что функция примитивно рекурсивна. Показать примитивную рекурсивность функции g, если она имеет следующий вид:
1.2.
Решение
...

Задание № 2
Даны функции g(x) и h(x,y,z). Определить, какая функция f(x,y) получается из них с помощью операции примитивной рекурсии.
2.2. g(x)=x, h(x,y,z)=z
Решение
...

Задание № 3
В канторовской нумерации определить номер тройки и тройку с номером n.
1.2. ; n=15;
Решение
...

Задание № 4
Дан алфавит А= . Определить словарный номер С ( ) слова , и определить слово (n), имеющее номер n.
1.2. =a3 a1 a2 a3; n=67;
Решение
...

Задание № 5
В алфавите А= показать примитивную рекурсивность словарной функции.
5.1 – 5.5 F( , )= – функция, приписывающая к слову справа слово .
Решение
...

Задание № 6
В алфавите А= построить машину Тьюринга, вычисляющую функцию (n). Программу записать в виде таблицы.
6.1 – 6.5. (n)= n+3;
Решение
...

Задание № 7
В алфавите А= построить машину Тьюринга, вычисляющую функцию (x,y). Использовать машины Т+ и Ткоп.
7.1 – 7.5. (x,y)=xy.
Решение
...