Временная и пространственная сложность алгоритмов/Задачи/Машина Тьюринга. Количество.

Маркеева Лариса 973б

У нас есть алфавит , а так же пустой символ - всего символа. А так же - всего состояние. А так же возможные движения головки: влево, вправо, неподвижно - всего 3 действия.
Машина Тьюринга может быть задана таблицей , где в каждой ячейке описаны тройки , где symbol - что записать на ленту, state - в какое состояние перейти, action - куда сдвинуть головку.
Итого, каждая ячейка может содержать одну из троек.
Всего ячеек , следовательно, существует различных таблиц.
Между машинами Тьюринга и такими таблицами установлено взаимно-однозначное соответствие. Следовательно, число различных машин Тьюринга со входным алфавитом и множеством состояний равно .