102
правки
Изменения
Нет описания правки
===Булевы функции===
Заметим, что управляющая часть МТ считывает с ленты входную строчку и завершается, записав на ленту выходную строчку. Без ограничения общности, будем рассматривать бинарные строки. Следовательно, управляющая часть МТ есть функция вида
<tex>f:\{0, 1\}^n \rightarrow \{0, 1\}^m </tex>, т.е. из бинарной строки в бинарную строку.
Заметим, что можно построить функции такого вида из булевых функций <tex>f_i:\{0, 1\}^n \rightarrow \{0, 1\}</tex>:
<tex>f(x_1, x_2, x_3 ... x_n) = f(f_1(x_1, x_2, x_3 ... x_n), f_2(x_1, x_2, x_3 ... x_n), ... f_m(x_1, x_2, x_3 ... x_n) </tex>.
