Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
Поскольку машины Тьюринга подробно описаны в литературе $[2$, 16], мы ограничимся кратким изложением проблемы. Машина Тьюринга состоит из трех частей: внутренней машины $\mathscr{L}$, вычислительной ленты $\mathscr{T}$ и вычислительной головки h. Состояния $\mathscr{L}$ можно представить числами $0,1, \ldots$ из $\mathbb{N}, \mathscr{T}$ — это лента, состоящая из бесконечного числа клеток, каждая из которых может находиться в одном из конечного числа состояний из $S$ — алфавита символов. Особый элемент из $S-b$ — обозначает пустую клетку. На ленте $\mathscr{T}$ можно написать выражения — последовательности символов $\gamma: \mathbb{Z} \rightarrow S$, где $\mathbb{Z}$ — множество целых чисел и $\gamma(j)=b$, исключая не более чем конечное число значений $j$. Элементарные операции машины задаются пятерками $l\left(s, s^{\prime}, \alpha\right) l^{\prime}$, каждая из которых означает, что $\mathscr{L}$ в состоянии $l$ и символ $s$ в клетке из $\mathscr{T}$, только что прочитанный $\mathbf{h}$, переходят в состояния $l^{\prime}$ и $s^{\prime}$, а головка $\mathbf{h}$ перемещается на одну клетку вправо $(\alpha=+1)$ или влево $(\alpha=-1)$, либо остается на месте $(\alpha=0)$. Каждая машина Тьюринга соответствует конечному множеству пятерок $Q$, в котором нет пятерок, начинающихся с двух одинаковых символов. Если в конце некоторого шага $\mathscr{L}$ находится в состоянии $l$, а $s$ — символ, прочитанный $\mathbf{h}$, то следующий шаг задается пятеркой вида $l(s,-,-)-$. Если такой пятерки в $Q$ нет, то машина останавливается. Каждая машина $Q$ определяет функцию $\tau_{Q}: \mathbb{N} \times S \rightarrow \mathbb{N} \times S \times$ $\times\{-1,0,1\}$, где для каждой пары $(l s)$ из пятерки $l\left(s s^{\prime} \alpha\right) l^{\prime}$, принадлежащей $Q$. Если в $Q$ нет пятерки, начинающейся с $l$ и $s$, то $\tau_{Q}(l S)=(l s 0)$. С помощью функции $\tau_{Q}$ можно определить функцию перехода машины $T_{Q}$ как отображение $T_{Q}: I D \rightarrow I D$, где $I D=\mathbb{N} \times(S)_{b}^{\mathbb{Z}} \times \mathbb{Z}-$ множество мгновенных описаний машины. Приведем явное выражение функции $T_{Q}$ : Удобно ограничиться такими машинами Тьюринга, которые выполняют вычисления в стандартной форме. В этом случае начальное состояние определяется как состояние «1», головка $\mathbf{h}$ читает символ в клетке «0» из $\mathscr{T}$ и каждое выражение $\gamma_{i}(j)=b$, если $j<0$, и не существует двух непустых состояний символов в $\gamma_{i}$, разделенных пустым. В этом случае после $n$ шагов вычислений стандартной машины Тьюринга состояние внутренней машины $\mathscr{L}$ находится среди первых $N_{n}$ чисел из $\mathbb{N}$, где Здесь и далее $m$ — число символов в алфавите $S$. Стандартное конечное состояние похоже на начальное, следует только принять во внимание, что теперь это — одно из допустимых состояний. Нам понадобятся числа, которые представляют в решетчатой модели двоичные цепочки спинов, направленных вверх (+) и вниз (-). Для представления всех положительных чисел, не превосходящих $n$, требуется $l_{2}(n)$ двоичных цепочек, где где $[r]$ означает наибольшее целое число, содержащееся в $r$. Пустые клетки $\mathscr{T}$ моделируются цепочками (-)-спинов. В представлении двоичных чисел на решетке спинов (+)-спины соответствуют единице, а (-)-спины — нулю. Таким образом, каждая пустая клетка $\mathscr{T}$ соответствует числу 0 , записанному в клетке. В дальнейшем будут рассматриваться системы, которые моделируют только $J$ первых шагов стандартной машины Тьюринга. Это ограничение, вызываемое исключительно интересами математической простоты, позволяет избежать бесконечномерных квантовых систем. Теперь состояния внутренней машины $\mathscr{L}$ будут находиться среди чисел $\left\{1,2, \ldots, N_{j}\right\}$.
|
1 |
Оглавление
|