Временная и пространственная сложность алгоритмов/Задачи/Машина Тьюринга. Количество. — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
| Строка 1: | Строка 1: | ||
| − | + | Маркеева Лариса 973б | |
| − | + | ||
| − | + | ||
| − | [[ | + | У нас есть алфавит <math>\Sigma=\left\{a_0\dots a_n\right\}</math>, а так же пустой символ <math>\Lambda</math> - всего <math>n+2</math> символа. А так же <math>S=\left\{s_0\dots s_m\right\}</math> - всего <math>m+1</math> состояние. А так же возможные движения головки: влево, вправо, неподвижно - всего 3 действия.<br /> |
| + | Машина Тьюринга может быть задана таблицей <math>\left(n+2\right) \times \left(m+1\right)</math>, где в каждой ячейке описаны тройки <math>\left\{symbol, state, action\right\}</math>, где symbol - что записать на ленту, state - в какое состояние перейти, action - куда сдвинуть головку. <br /> | ||
| + | Итого, каждая ячейка может содержать одну из <math>3\cdot\left(n+2\right)\left(m+1\right)</math> троек.<br /> | ||
| + | Всего ячеек <math>\left(n+2\right) \left(m+1\right)</math>, следовательно, существует <math>\left(3\cdot\left(n+2\right)\left(m+1\right)\right)^{\left(n+2\right) \left(m+1\right)}\right)</math> различных таблиц. <br /> | ||
| + | Между машинами Тьюринга и такими таблицами установлено взаимно-однозначное соответствие. Следовательно, число различных машин Тьюринга со входным алфавитом <math>A</math> и множеством состояний <math>S</math> равно <math>\left(3\cdot\left(n+2\right)\left(m+1\right)\right)^{\left(n+2\right) \left(m+1\right)}\right)</math>. | ||
| + | |||
| + | |||
| + | [[Категория:На проверку]] | ||
Версия 20:23, 7 октября 2014
Маркеева Лариса 973б
У нас есть алфавит , а так же пустой символ - всего символа. А так же - всего состояние. А так же возможные движения головки: влево, вправо, неподвижно - всего 3 действия.
Машина Тьюринга может быть задана таблицей , где в каждой ячейке описаны тройки , где symbol - что записать на ленту, state - в какое состояние перейти, action - куда сдвинуть головку.
Итого, каждая ячейка может содержать одну из троек.
Всего ячеек , следовательно, существует различных таблиц.
Между машинами Тьюринга и такими таблицами установлено взаимно-однозначное соответствие. Следовательно, число различных машин Тьюринга со входным алфавитом и множеством состояний равно .