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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: добавление Категория:Теоретические задачи)
 
(не показано 20 промежуточных версий этого же участника)
Строка 1: Строка 1:
Маркеева Лариса 973б
+
<latex>
 +
Пусть есть алфавит $\Sigma =\{a_0,...,a_n\}$, есть множество состояний $S=\{s_0,...,s_m\}$. Сколько существует машин Тьюринга для данных множеств?
 +
</latex>
  
У нас есть алфавит <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>.
+
 
+
 
+
[[Категория:На проверку]]
+

Текущая версия на 06:50, 4 мая 2023