Доказано.

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

Программа МТ выглядит следующим образом:

q₁1→ 1Пq₁; … q₁0→ 0Лq₁; q₁0→ 0Лq₁; q₁0→ 0Лq₀.

согласно которой для любой начальной конфигурации, когда считывающая головка обозревает одну из единиц, в каждый момент эта единица остается на месте, и головка сдвигается вправо на одну ячейку. Этот процесс продолжается до тех пор, пока головка не выйдет на пустую ячейку. Тогда в головка смещается влево и записывает 0, производит еще 2 такие операции. Машина перейдет в состояние q₀.

Стоит учесть, что если вводные данные меньше трех машина зацикливается и переходит в состояние q₀.

5. Суперпозиция (сложная функция) — это функция, полученная из некоторого множества функций путем подстановки одной функции в другую или отождествления переменных.

Способы получения суперпозиций Рассмотрим две булевы функции: функцию от аргументов и функцию от аргументов .
Тогда мы можем получить новую функцию из имеющихся двумя способами:

· Подстановкой одной функции в качестве некоторого аргумента для другой;

· Отождествлением аргументов функций.