Аноним

Машина Тьюринга: различия между версиями

Материал из WEGA
нет описания правки
(Создана новая страница размером '''Машина Тьюринга'''(''Turing machine'') - одна из основных конструкций, кот...)
 
Нет описания правки
Строка 36: Строка 36:


''Начальной'' конфигурацией <math>M</math> называется конфигурация
''Начальной'' конфигурацией <math>M</math> называется конфигурация
вида <math>q_0\omega</math>, где <math>\omega\in\Sigma^*</math>. {\it
вида <math>q_0\omega</math>, где <math>\omega\in\Sigma^*</math>. Заключительная конфигурация --- это конфигурация вида <math>xq_f
Заключительная} конфигурация --- это конфигурация вида <math>xq_f
y</math>.
y</math>.


Строка 61: Строка 60:
цепочек, допускаемых <math>M</math>.
цепочек, допускаемых <math>M</math>.


Таким образом, подобно конечному автомату машина Тью\-рин\-га
Таким образом, подобно конечному автомату машина Тьюринга
состоит из ленты, головки и управляющего устройства с конечным
состоит из ленты, головки и управляющего устройства с конечным
числом состояний.
числом состояний.