|
|
| Строка 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 />
| + | [[Category:Решенные задачи]] |
| − | Машина Тьюринга может быть задана таблицей <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>.
| + | |
| − | | + | |
| − | | + | |
| − | [[Категория:На проверку]] | + | |