4194
правки
Машина Тьюринга: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KEV (обсуждение | вклад) (Создана новая страница размером '''Машина Тьюринга'''(''Turing machine'') - одна из основных конструкций, кот...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 36: | Строка 36: | ||
''Начальной'' конфигурацией <math>M</math> называется конфигурация | ''Начальной'' конфигурацией <math>M</math> называется конфигурация | ||
вида <math>q_0\omega</math>, где <math>\omega\in\Sigma^*</math>. | вида <math>q_0\omega</math>, где <math>\omega\in\Sigma^*</math>. Заключительная конфигурация --- это конфигурация вида <math>xq_f | ||
Заключительная | |||
y</math>. | y</math>. | ||
| Строка 61: | Строка 60: | ||
цепочек, допускаемых <math>M</math>. | цепочек, допускаемых <math>M</math>. | ||
Таким образом, подобно конечному автомату машина | Таким образом, подобно конечному автомату машина Тьюринга | ||
состоит из ленты, головки и управляющего устройства с конечным | состоит из ленты, головки и управляющего устройства с конечным | ||
числом состояний. | числом состояний. | ||