Донецкий национальный университет
ДИСКРЕТНАЯ МАТЕМАТИКА
кафедра инженерной и компьютационной педагогики

Коллоквиумы

В процессе изучения дисциплины Дискретная математика студенту предлагается сдать три коллоквиума. Максимальное количество рейтинговых баллов на каждом коллоквиуме равно 8. Всего за три коллоквиума студент может набрать 24 балла. Один поощрительный балл преподаватель может выставить студенту за успешную сдачу всех трех коллоквиумов. Таким образом, за все три коллоквиума студент может получить максимум 25 баллов (при максимальном общем рейтинге 100 баллов). Билеты к коллоквиумам приведены ниже.

Коллоквиум №1: БУЛЕВЫ ФУНКЦИИ

БИЛЕТ № 1

  1. Определение булевой функции. Задание булевой функции таблицей истинности. Примеры.
  2. С помощью равносильных преобразований приведите к ДНФ следующую формулу: (x1 ∨ x2x3)(x1 ∨ x3).

БИЛЕТ № 2

  1. Количество строк в таблице истинности булевой функции. Зависимость количества булевых функций от числа аргументов. Примеры.
  2. Приведите к СДНФ следующую формулу:

БИЛЕТ № 3

  1. Существенные и несущественные аргументы булевой функции. Булевы функции одного аргумента.
  2. С помощью равносильных преобразований приведите к ДНФ следующую формулу:

БИЛЕТ № 4

  1. Дизъюнкция и ее свойства.
  2. Приведите к СКНФ следующую формулу:

БИЛЕТ № 5

  1. Конъюнкция и ее свойства.
  2. Приведите к СДНФ следующую формулу:

БИЛЕТ № 6

  1. Импликация, ее выражение через дизъюнкцию, конъюнкцию и отрицание.
  2. Приведите к СКНФ следующую формулу:

БИЛЕТ № 7

  1. Эквивалентность, ее выражение через импликацию и конъюнкцию.
  2. Приведите к СКНФ следующую формулу:

БИЛЕТ № 8

  1. Сумма по модулю два. Выражение дизъюнкции через конъюнкцию и сумму по модулю два.
  2. Приведите к СДНФ следующую формулу:

БИЛЕТ № 9

  1. Реализация булевых функций формулами. Тождества алгебры булевых функций.
  2. Заданную КНФ приведите к ДНФ:

БИЛЕТ № 10

  1. Совершенная дизъюнктивная нормальная форма (СДНФ).
  2. Заданную КНФ приведите к ДНФ:

БИЛЕТ № 11

  1. Совершенная конъюнктивная нормальная форма (СКНФ).
  2. Заданную КНФ приведите к ДНФ:

БИЛЕТ № 12

  1. Полином Жегалкина. Линейные и нелинейные булевы функции.
  2. Проверьте на монотонность следующую булеву функцию:

БИЛЕТ № 13

  1. Двойственность и самодвойственность булевых функций.
  2. Представьте полиномом Жегалкина следующую булеву функцию:

БИЛЕТ № 14

  1. Монотонные и немонотонные булевы функции.
  2. Представьте полиномом Жегалкина следующую булеву функцию:

БИЛЕТ № 15

  1. Полные системы булевых функций.
  2. Представьте полиномом Жегалкина следующую булеву функцию:

БИЛЕТ № 16

  1. Замкнутые классы булевых функций.
  2. Проверьте на монотонность следующую булеву функцию:

БИЛЕТ № 17

  1. Теорема Поста о полноте системы булевых функций.
  2. Проверьте на монотонность следующую булеву функцию:

БИЛЕТ № 18

  1. Булевы функции, сохраняющие ноль, и булевы функции, сохраняющие единицу. Примеры.
  2. Проверьте на монотонность следующую булеву функцию:

БИЛЕТ № 19

  1. Правила (тождества) де Моргана. Их доказательство.
  2. Проверьте на монотонность следующую булеву функцию:

БИЛЕТ № 20

  1. Выражение дизъюнкции через сумму по модулю два и конъюнкцию. Выражение отрицания через сумму по модулю два.
  2. Проверьте на монотонность следующую булеву функцию:

Задачи

В процессе изучения дисциплины Дискретная математика студенту предлагается решить задачи из приведенного ниже списка (в каждом разделе номер задачи соответствует номеру варианта индивидуального задания студента). За полное правильное решение всех задач своего варианта индивидуального задания студент получает максимум 25 баллов (при максимальном общем рейтинге 100 баллов).

Содержательный модуль БУЛЕВЫ ФУНКЦИИ

1. Совершенная дизъюнктивная нормальная форма (СДНФ) и дизъюнктивная нормальная форма (ДНФ)

1. Записанное в десятичной системе счисления натуральное число 152 переведите в двоичную систему. Допишите, если это будет необходимо, слева столько нулей, сколько нужно, чтобы получилась строка, содержащая восемь цифр. Рассматривайте полученную последовательность нулей и единиц как последний столбец таблицы истинности некоторой булевой функции f (заменив чтение слева направо чтением сверху вниз). Считайте, что эта булева функция зависит от трех аргументов. Постройте для функции f совершенную дизъюнктивную нормальную форму (СДНФ). Упростите ее до дизъюнктивной нормальной формы (ДНФ). По полученной ДНФ выполните проверку.

2. Записанное в десятичной системе счисления натуральное число 67 переведите в двоичную систему. Допишите, если это будет необходимо, слева столько нулей, сколько нужно, чтобы получилась строка, содержащая восемь цифр. Рассматривайте полученную последовательность нулей и единиц как последний столбец таблицы истинности некоторой булевой функции g (заменив чтение слева направо чтением сверху вниз). Считайте, что эта булева функция зависит от трех аргументов. Постройте для функции g совершенную дизъюнктивную нормальную форму (СДНФ). Упростите ее до дизъюнктивной нормальной формы (ДНФ). По полученной ДНФ выполните проверку.

3. Записанное в десятичной системе счисления натуральное число 164 переведите в двоичную систему. Допишите, если это будет необходимо, слева столько нулей, сколько нужно, чтобы получилась строка, содержащая восемь цифр. Рассматривайте полученную последовательность нулей и единиц как последний столбец таблицы истинности некоторой булевой функции h (заменив чтение слева направо чтением сверху вниз). Считайте, что эта булева функция зависит от трех аргументов. Постройте для функции h совершенную дизъюнктивную нормальную форму (СДНФ). Упростите ее до дизъюнктивной нормальной формы (ДНФ). По полученной ДНФ выполните проверку.

4. Записанное в десятичной системе счисления натуральное число 74 переведите в двоичную систему. Допишите, если это будет необходимо, слева столько нулей, сколько нужно, чтобы получилась строка, содержащая восемь цифр. Рассматривайте полученную последовательность нулей и единиц как последний столбец таблицы истинности некоторой булевой функции f (заменив чтение слева направо чтением сверху вниз). Считайте, что эта булева функция зависит от трех аргументов. Постройте для функции f совершенную дизъюнктивную нормальную форму (СДНФ). Упростите ее до дизъюнктивной нормальной формы (ДНФ). По полученной ДНФ выполните проверку.

5. Записанное в десятичной системе счисления натуральное число 100 переведите в двоичную систему. Допишите, если это будет необходимо, слева столько нулей, сколько нужно, чтобы получилась строка, содержащая восемь цифр. Рассматривайте полученную последовательность нулей и единиц как последний столбец таблицы истинности некоторой булевой функции g (заменив чтение слева направо чтением сверху вниз). Считайте, что эта булева функция зависит от трех аргументов. Постройте для функции g совершенную дизъюнктивную нормальную форму (СДНФ). Упростите ее до дизъюнктивной нормальной формы (ДНФ). По полученной ДНФ выполните проверку.

2. Доказательство тождеств алгебры булевых функций

1. Четырьмя способами (сравнением таблиц истинности, сведением обеих частей к одному и тому же выражению, сведением левой части к правой, сведением правой части к левой) докажите справедливость следующего тождества:

(a ↓ c) ∨ a b c = (a ↔ c)(a | b)(b → (1 ⊕ c))

2. Четырьмя способами (сравнением таблиц истинности, сведением обеих частей к одному и тому же выражению, сведением левой части к правой, сведением правой части к левой) докажите справедливость следующего тождества:

(b ↓ c) ∨ a b c = (a → (1 ⊕ b))(a | c)(b ↔ c)

3. Четырьмя способами (сравнением таблиц истинности, сведением обеих частей к одному и тому же выражению, сведением левой части к правой, сведением правой части к левой) докажите справедливость следующего тождества:

(a ↓ b) c ∨ a c = (a ⊕ c)(b → a)(b | c)

4. Четырьмя способами (сравнением таблиц истинности, сведением обеих частей к одному и тому же выражению, сведением левой части к правой, сведением правой части к левой) докажите справедливость следующего тождества:

a b c ∨ (1 ⊕ (a | b)) = (a ↔ b)(c ⊕ a b ⊕ a b c)

5. Четырьмя способами (сравнением таблиц истинности, сведением обеих частей к одному и тому же выражению, сведением левой части к правой, сведением правой части к левой) докажите справедливость следующего тождества:

b c ∨ (a ↓ c) b =(a | b)(a → c)(b ⊕ c)

3. Совершенная конъюнктивная нормальная форма (СКНФ)

1. Записанное в десятичной системе счисления натуральное число 204 переведите в двоичную систему. Допишите, если это будет необходимо, слева столько нулей, сколько нужно, чтобы получилась строка, содержащая восемь цифр. Рассматривайте полученную последовательность нулей и единиц как последний столбец таблицы истинности некоторой булевой функции f (заменив чтение слева направо чтением сверху вниз). Считайте, что эта булева функция зависит от трех аргументов. Постройте для функции f совершенную конъюнктивную нормальную форму (СКНФ). Насколько сможете, упростите формулу. По полученной упрощенной формуле выполните проверку.

2. Записанное в десятичной системе счисления натуральное число 132 переведите в двоичную систему. Допишите, если это будет необходимо, слева столько нулей, сколько нужно, чтобы получилась строка, содержащая восемь цифр. Рассматривайте полученную последовательность нулей и единиц как последний столбец таблицы истинности некоторой булевой функции g (заменив чтение слева направо чтением сверху вниз). Считайте, что эта булева функция зависит от трех аргументов. Постройте для функции g совершенную конъюнктивную нормальную форму (СКНФ). Насколько сможете, упростите формулу. По полученной упрощенной формуле выполните проверку.

3. Записанное в десятичной системе счисления натуральное число 206 переведите в двоичную систему. Допишите, если это будет необходимо, слева столько нулей, сколько нужно, чтобы получилась строка, содержащая восемь цифр. Рассматривайте полученную последовательность нулей и единиц как последний столбец таблицы истинности некоторой булевой функции h (заменив чтение слева направо чтением сверху вниз). Считайте, что эта булева функция зависит от трех аргументов. Постройте для функции h совершенную конъюнктивную нормальную форму (СКНФ). Насколько сможете, упростите формулу. По полученной упрощенной формуле выполните проверку.

4. Записанное в десятичной системе счисления натуральное число 123 переведите в двоичную систему. Допишите, если это будет необходимо, слева столько нулей, сколько нужно, чтобы получилась строка, содержащая восемь цифр. Рассматривайте полученную последовательность нулей и единиц как последний столбец таблицы истинности некоторой булевой функции f (заменив чтение слева направо чтением сверху вниз). Считайте, что эта булева функция зависит от трех аргументов. Постройте для функции f совершенную конъюнктивную нормальную форму (СКНФ). Насколько сможете, упростите формулу. По полученной упрощенной формуле выполните проверку.

5. Записанное в десятичной системе счисления натуральное число 79 переведите в двоичную систему. Допишите, если это будет необходимо, слева столько нулей, сколько нужно, чтобы получилась строка, содержащая восемь цифр. Рассматривайте полученную последовательность нулей и единиц как последний столбец таблицы истинности некоторой булевой функции g (заменив чтение слева направо чтением сверху вниз). Считайте, что эта булева функция зависит от трех аргументов. Постройте для функции g совершенную конъюнктивную нормальную форму (СКНФ). Насколько сможете, упростите формулу. По полученной упрощенной формуле выполните проверку.

4. Полином Жегалкина

1. Записанное в десятичной системе счисления натуральное число 42 переведите в двоичную систему. Допишите, если это будет необходимо, слева столько нулей, сколько нужно, чтобы получилась строка, содержащая восемь цифр. Рассматривайте полученную последовательность нулей и единиц как последний столбец таблицы истинности некоторой булевой функции f (заменив чтение слева направо чтением сверху вниз). Считайте, что эта булева функция зависит от трех аргументов. Постройте для функции f полином Жегалкина. Выполните проверку. Является ли эта функция линейной?

2. Записанное в десятичной системе счисления натуральное число 15 переведите в двоичную систему. Допишите, если это будет необходимо, слева столько нулей, сколько нужно, чтобы получилась строка, содержащая восемь цифр. Рассматривайте полученную последовательность нулей и единиц как последний столбец таблицы истинности некоторой булевой функции g (заменив чтение слева направо чтением сверху вниз). Считайте, что эта булева функция зависит от трех аргументов. Постройте для функции g полином Жегалкина. Выполните проверку. Является ли эта функция линейной?

3. Записанное в десятичной системе счисления натуральное число 62 переведите в двоичную систему. Допишите, если это будет необходимо, слева столько нулей, сколько нужно, чтобы получилась строка, содержащая восемь цифр. Рассматривайте полученную последовательность нулей и единиц как последний столбец таблицы истинности некоторой булевой функции h (заменив чтение слева направо чтением сверху вниз). Считайте, что эта булева функция зависит от трех аргументов. Постройте для функции h полином Жегалкина. Выполните проверку. Является ли эта функция линейной?

4. Записанное в десятичной системе счисления натуральное число 24 переведите в двоичную систему. Допишите, если это будет необходимо, слева столько нулей, сколько нужно, чтобы получилась строка, содержащая восемь цифр. Рассматривайте полученную последовательность нулей и единиц как последний столбец таблицы истинности некоторой булевой функции f (заменив чтение слева направо чтением сверху вниз). Считайте, что эта булева функция зависит от трех аргументов. Постройте для функции f полином Жегалкина. Выполните проверку. Является ли эта функция линейной?

5. Записанное в десятичной системе счисления натуральное число 173 переведите в двоичную систему. Допишите, если это будет необходимо, слева столько нулей, сколько нужно, чтобы получилась строка, содержащая восемь цифр. Рассматривайте полученную последовательность нулей и единиц как последний столбец таблицы истинности некоторой булевой функции g (заменив чтение слева направо чтением сверху вниз). Считайте, что эта булева функция зависит от трех аргументов. Постройте для функции g полином Жегалкина. Выполните проверку. Является ли эта функция линейной?

5. Классы булевых функций P0, P1, S, L

1. Записанное в десятичной системе счисления натуральное число 25 переведите в двоичную систему. Допишите, если это будет необходимо, слева столько нулей, сколько нужно, чтобы получилась строка, содержащая восемь цифр. Рассматривайте полученную последовательность нулей и единиц как последний столбец таблицы истинности некоторой булевой функции f (заменив чтение слева направо чтением сверху вниз). Считайте, что эта булева функция зависит от трех аргументов. Охарактеризуйте ее отношение к классам P0, P1, S и L.

2. Записанное в десятичной системе счисления натуральное число 55 переведите в двоичную систему. Допишите, если это будет необходимо, слева столько нулей, сколько нужно, чтобы получилась строка, содержащая восемь цифр. Рассматривайте полученную последовательность нулей и единиц как последний столбец таблицы истинности некоторой булевой функции g (заменив чтение слева направо чтением сверху вниз). Считайте, что эта булева функция зависит от трех аргументов. Охарактеризуйте ее отношение к классам P0, P1, S и L.

3. Записанное в десятичной системе счисления натуральное число 83 переведите в двоичную систему. Допишите, если это будет необходимо, слева столько нулей, сколько нужно, чтобы получилась строка, содержащая восемь цифр. Рассматривайте полученную последовательность нулей и единиц как последний столбец таблицы истинности некоторой булевой функции h (заменив чтение слева направо чтением сверху вниз). Считайте, что эта булева функция зависит от трех аргументов. Охарактеризуйте ее отношение к классам P0, P1, S и L.

4. Записанное в десятичной системе счисления натуральное число 129 переведите в двоичную систему. Допишите, если это будет необходимо, слева столько нулей, сколько нужно, чтобы получилась строка, содержащая восемь цифр. Рассматривайте полученную последовательность нулей и единиц как последний столбец таблицы истинности некоторой булевой функции f (заменив чтение слева направо чтением сверху вниз). Считайте, что эта булева функция зависит от трех аргументов. Охарактеризуйте ее отношение к классам P0, P1, S и L.

5. Записанное в десятичной системе счисления натуральное число 71 переведите в двоичную систему. Допишите, если это будет необходимо, слева столько нулей, сколько нужно, чтобы получилась строка, содержащая восемь цифр. Рассматривайте полученную последовательность нулей и единиц как последний столбец таблицы истинности некоторой булевой функции g (заменив чтение слева направо чтением сверху вниз). Считайте, что эта булева функция зависит от трех аргументов. Охарактеризуйте ее отношение к классам P0, P1, S и L.

6. Класс булевых функций M

1. Установите, является ли сумма по модулю два (сумма Жегалкина) монотонной булевой функцией.

2. Установите, является ли эквивалентность монотонной булевой функцией.

3. Установите, является ли импликация монотонной булевой функцией.

4. Установите, является ли дизъюнкция монотонной булевой функцией.

5. Установите, является ли конъюнкция монотонной булевой функцией.

7. Критерий полноты системы булевых функций (критерий Поста)

1. Используя критерий Поста, установите, является ли система булевых функций {⊕, ¬, ∨} полной.

2. Используя критерий Поста, установите, является ли система булевых функций {→, ¬, ∧} полной.

3. Используя критерий Поста, установите, является ли система булевых функций {→, ⊕, ¬} полной.

4. Используя критерий Поста, установите, является ли система булевых функций {∧, ⊕, ¬} полной.

5. Используя критерий Поста, установите, является ли система булевых функций {∧, ⊕, ↔} полной.

Содержательный модуль
ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ


8. Задачи на наблюдение за работой
и анализ результатов работы
машин Тьюринга


1. Даны входные слова: а) 11111; б) 111111; в) 1a0111a0a01111; г) 1111111; д) 111; е) 1111; ж) 11a0a0111111; з) 11a0111. Дана программа для машины Тьюринга: 1) q1a0 → q4a0П; 2) q11 → q2; 3) q2a0 → q6a0П; 4) q21 → q3; 5) q3a0 → q6a0П; 6) q31 → q1; 7) q4a0 → q01; 8) q41 → q5a0; 9) q5a0 → q4a0П; 10) q51 → q5a0; 11) q6a0 → q0a0; 12) q61 → q7a0; 13) q7a0 → q6a0П; 14) q71 → q7a0. Перед обработкой каждого входного слова машина находится в состоянии q1, ее головка обозревает крайний правый непробельный символ входного слова. В какое слово перерабатывается каждое входное слово? Ответ обоснуйте, изображая на каждом такте работы машины получающуюся конфигурацию.

2. Дана программа для машины Тьюринга: 1) q11 → q2a0Л; 2) q1* → q0a0; 3) q2a0 → q3; 4) q21 → q2; 5) q2* → q2; 6) q3a0 → q1a0Л; 7) q31 → q3; 8) q3* → q3. Определите, в какое слово перерабатывается каждое из входных слов: а) 111*111; б) 1111*11; в) 111*1; г) 1*11; д) 11*111; е) 11111*; ж) *1111. Ответ обоснуйте, изображая последовательность получающихся для каждого слова на каждом такте конфигураций. После этого постарайтесь усмотреть общую закономерность в работе машины. Перед обработкой каждого входного слова машина находится в состоянии q1, ее головка обозревает крайний правый непробельный символ входного слова.

3. Дана программа для машины Тьюринга: 1) q11 → q2a0Л; 2) q1* → q0a0; 3) q21 → q2; 4) q2* → q2; 5) q2a0 → q3a0П; 6) q31 → q4a0П; 7) q4* → q0*; 8) q41 → q5; 9) q51 → q5; 10) q5* → q5; 11) q5a0 → q1a0Л. Определите, в какое слово машина перерабатывает каждое из входных слов: а) 111*11; б) 11*11; в) 1111*1; г) 11111*111; д) 11111*1111. При этом изобразите последовательность получающихся для каждого слова на каждом такте конфигураций. Выявите общую закономерность в работе машины. Перед обработкой каждого входного слова машина находится в состоянии q1, ее головка обозревает крайний правый непробельный символ входного слова.

4. Дана программа для машины Тьюринга: 1) q1a0 → q4a0П; 2) q11 → q2α; 3) q1α → q1αЛ; 4) q1β → q1βЛ; 5) q2a0 → q3a0Л; 6) q21 → q1β; 7) q2α → q2αП; 8) q2β → q2βП; 9) q3a0 → q1a0П; 10) q31 → q1; 11) q3α → q3; 12) q3β → q3a0Л; 13) q4a0 → q0a0Л; 14) q41 → q1; 15) q4α → q4a0П; 16) q4β → q4. Перед обработкой каждого входного слова машина находится в состоянии q1, ее головка обозревает указываемую вместе с входным словом ячейку. Изображая последовательность получающихся для каждого слова на каждом такте конфигураций, определите, в какое слово перерабатывается каждое из входных слов: а) 11111 (обозревается ячейка 2, считая слева); б) 111 (обозревается ячейка 1); в) 1111111111 (обозревается ячейка 4); г) 111111 (обозревается ячейка 2); д) 111111111111111 (обозревается ячейка 6). Выявите общую закономерность в работе машины.

5. Дана программа для машины Тьюринга: 1) q1a0 → q2a0П; 2) q11 → q1; 3) q2a0 → q2a0П; 4) q21 → q3; 5) q3a0 → q0a0; 6) q31 → q3. Также даны входные слова: a) 111a0a01; б) 11a0a011a01; в) 111111; г) 1a0a0a0a01; д) 11a0a011; е) 1; ж) 1a01a01a01; з) 111; и) 1a01a01; к) 11a011. Для каждого входного слова выясните, остановится ли когда-нибудь машина, если она начнет перерабатывать данное слово. Считайте, что в начальный момент машина находится в состоянии q1 и обозревает ячейку, в которой записана самая левая буква перерабатываемого слова. Если остановка происходит, то определите, какое слово получается в результате, какая ячейка и в каком (перед остановкой) состоянии обозревается. Исследование проведите, изображая последовательность получающихся для каждого слова на каждом такте конфигураций.


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


1. Дана программа для машины Тьюринга: 1) q10 → q2; 2) q20 → q0; 3) q21 → q3; 4) q30 → q7; 5) q71 → q7; 6) q70 → q00; 7) q31 → q4; 8) q41 →q5; 9) q50 → q6a0П; 10) q60 → q1a0П. Какую арифметическую функцию f(x) вычисляет машина? Правильно ли она ее вычисляет?

2. Дана программа для машины Тьюринга: 1) q10 → q2; 2) q20 → q0; 3) q21 → q3βП; 4) q2α → q5α; 5) q31 → q3; 6) q30 → q3αП; 7) q3α → q3αП; 8) q3a0 → q4; 9) q4α → q4αЛ; 10) q41 → q4; 11) q4β → q2βП; 12) q5β → q5; 13) q5α → q5; 14) q50 → q6; 15) q61 → q6; 16) q6β → q6; 17) q60 → q00. Какую арифметическую функцию f(x) вычисляет машина? Правильно ли она ее вычисляет?

3. Дана программа для машины Тьюринга: 1) q10 → q2; 2) q20 → q0; 3) q21 → q3; 4) q31 → q3; 5) q30 → q4a0Л; 6) q41 → q5; 7) q51 → q5; 8) q50 → q00. Какую арифметическую функцию f(x) вычисляет машина? Правильно ли она ее вычисляет?

4. Дана программа для машины Тьюринга: 1) q10 → q2; 2) q21 → q2; 3) q20 → q2; 4) q2a0 → q3; 5) q31 → q3; 6) q30 → q00. Какую арифметическую функцию f(x) вычисляет машина? Правильно ли она ее вычисляет?

5. Дана программа для машины Тьюринга: 1) q10 → q2; 2) q20 → q0; 3) q21 → q3; 4) q31 → q3a0П; 5) q30 → q4a0Л; 6) q4a0 → q4a0Л; 7) q40 → q0. Какую арифметическую функцию f(x) вычисляет машина? Правильно ли она ее вычисляет?


10. Задачи на конструирование
машин Тьюринга


1. Известно, что на ленте записано слово из n единиц (n > 1). Постройте машину Тьюринга с внешним алфавитом А = {a0, 1}, которая отыскивала бы левую единицу этого слова (то есть приходила бы в состояние, при котором обозревалась бы ячейка с самой левой единицей данного слова, и в этом положении останавливалась), если в начальный момент головка машины обозревает одну из ячеек с буквой данного слова.

2. Сконструируйте машину Тьюринга с внешним алфавитом А = {а0, 1}, которая каждое слово в алфавите А1 = {1} перерабатывает в пустое слово, исходя из стандартного начального положения (в нем машина находится в состоянии q1, головка обозревает самый правый непробельный символ входного слова).

3. Сконструируйте машину Тьюринга с внешним алфавитом А = {а0, 1}, которая каждое слово длиной n в алфавите А1 = {1} перерабатывает в слово длиной n + 1 в том же алфавите А1.

4. На ленте машины Тьюринга записаны два массива единиц. Они разделены звездочкой. Составьте функциональную схему машины так, чтобы она, исходя из стандартного начального положения (в нем машина находится в состоянии q1, головка обозревает самый правый непробельный символ входного слова), выбрала больший из этих наборов, а меньший стерла. Звездочка должна быть сохранена, чтобы было видно, какой из массивов выбран. Рассмотрите примеры работы этой машины применительно к словам: а) 1*11; б) 11*1; в) 11*111; г) 111*11; д) 11*1111; е) 1111*11.

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


11. Задачи на построение машин Тьюринга,
правильно вычисляющих заданные
арифметические функции


1. Постройте машину Тьюринга, правильно вычисляющую арифметическую функцию f(x, y) = x + y.

2. Постройте машину Тьюринга, правильно вычисляющую арифметическую функцию I1(x, y) = x.

3. Постройте машину Тьюринга, правильно вычисляющую арифметическую функцию f(x, y) = x - y (x ⩾ y).

4. Постройте машину Тьюринга, правильно вычисляющую сумму по модулю два f(x, y) = x ⊕ y, рассматриваемую как арифметическая функция.

5. Постройте машину Тьюринга, правильно вычисляющую штрих Шеффера f(x, y) = x | y, рассматриваемый как арифметическая функция.


12. Задачи на конструирование машин Тьюринга,
перерабатывающих входные слова
заданным образом


1. Пусть исходное слово W0 состоит только из символов 0 и 1, то есть является словом в алфавите {0, 1}. Пусть слово W1 является словом в том же алфавите и имеет ту же длину, что и слово W0. Если машина Тьюринга перерабатывает слово W0 в слово W1 так, что в процессе работы головка не выходит за границы исходного слова ни влево, ни вправо (то есть головка никогда не обозревает пустую ячейку), используется запись W0 ⤇ W1. Сконструируйте машину Тьюринга, перерабатывающую входные слова следующим образом: q1001x0 ⤇ q001x00. Эта машина называется переносом нуля и обозначается Z.

2. Пусть исходное слово W0 состоит только из символов 0 и 1, то есть является словом в алфавите {0, 1}. Пусть слово W1 является словом в том же алфавите и имеет ту же длину, что и слово W0. Если машина Тьюринга перерабатывает слово W0 в слово W1 так, что в процессе работы головка не выходит за границы исходного слова ни влево, ни вправо (то есть головка никогда не обозревает пустую ячейку), используется запись W0 ⤇ W1. Сконструируйте машину Тьюринга, перерабатывающую входные слова следующим образом: q101x0 ⤇ 01xq00. Эта машина называется сдвигом вправо и обозначается S+.

3. Пусть исходное слово W0 состоит только из символов 0 и 1, то есть является словом в алфавите {0, 1}. Пусть слово W1 является словом в том же алфавите и имеет ту же длину, что и слово W0. Если машина Тьюринга перерабатывает слово W0 в слово W1 так, что в процессе работы головка не выходит за границы исходного слова ни влево, ни вправо (то есть головка никогда не обозревает пустую ячейку), используется запись W0 ⤇ W1. Сконструируйте машину Тьюринга, перерабатывающую входные слова следующим образом: 01xq10 ⤇ q001x0. Эта машина называется сдвигом влево и обозначается S.

4. Пусть исходное слово W0 состоит только из символов 0 и 1, то есть является словом в алфавите {0, 1}. Пусть слово W1 является словом в том же алфавите и имеет ту же длину, что и слово W0. Если машина Тьюринга перерабатывает слово W0 в слово W1 так, что в процессе работы головка не выходит за границы исходного слова ни влево, ни вправо (то есть головка никогда не обозревает пустую ячейку), используется запись W0 ⤇ W1. Сконструируйте машину Тьюринга, перерабатывающую входные слова следующим образом: 01xq101y0 ⤇ 01yq001x0. Эта машина называется транспозицией и обозначается T.

5. Пусть исходное слово W0 состоит только из символов 0 и 1, то есть является словом в алфавите {0, 1}. Пусть слово W1 является словом в том же алфавите и имеет ту же длину, что и слово W0. Если машина Тьюринга перерабатывает слово W0 в слово W1 так, что в процессе работы головка не выходит за границы исходного слова ни влево, ни вправо (то есть головка никогда не обозревает пустую ячейку), используется запись W0 ⤇ W1. Сконструируйте машину Тьюринга, перерабатывающую входные слова следующим образом: q101x0x+2 ⤇ q001x01x0. Эта машина называется удвоением и обозначается D.