Вариант 20.

Задание 3.1.1.

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

Задание 3.1.3.

1. Написать формулу числовой функции , вычислимой машиной Тьюринга с множеством внутренних состояний , где 0 – заключительное, а 1 – начальное состояния, если машина задана своей программой.

2. Проверить работу машины Тьюринга с некоторым набором значений аргументов.

Задание 3.1.4.

1. По данному коду  восстановить программу машины Тьюринга.

2. Выяснить, является ли машина  самоприменимой или несамоприменимой.

При составлении  использована следующая кодировка:

, , , , , , , , .

Задание 3.2.1.

1. Построить нормальный алгоритм, применимый ко всем словам , в алфавите  и переводящий их в слово .

2. Проверить работу построенного нормального алгоритма над некоторыми словами.

Задание 3.2.3.

1. Написать формулу для функции , вычисляемой нормальным алгоритмом.

2. Проверить работу алгоритма над некоторым набором значений аргументов.

.

Задание 3.3.1.

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

, .

Задание 3.3.2.

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

, .

Задание 4.1.2.

Выяснить местность и тип предиката , каждый аргумент которого принимает значения из множества .

, .

Задание 4.1.3.

Найти значение высказывания , полученного из трехместного предиката, определенного на множестве .

, .

Задание 4.1.4.

Предикаты  и  определены на множестве .

1. Найти предикат, равносильный предикату , но не содержащий кванторов.

2. Выяснить, может ли предикат  быть выполнимым, но не тождественно истинным.

.

Задание 4.1.5.

1. Представить в приведенной форме предикат  варианта №.

.

2. Представить в предваренной нормальной форме предикат  варианта №+1.

.

Вы можете заказать другой вариант или другие сочетания номеров данной контрольной работы, а также любую другую работу здесь.