Примеры выполнения заданий. Практическое занятие №17

Практическое занятие №17. Машина Тьюринга.

Машина Тьюринга состоит из бесконечной в обе стороны ленты, разбитой на ячейки, и рабочей головки. Она работает в дискретные моменты времени: t₀, t₁, …, t_n, … В каждый момент во всякой ячейке ленты может быть записана одна из букв некоторого конечного внешнего алфавита A = { a₀, a₁, … a_k-1}, а головка может находиться в одном из конечного числа внутренних состояний
Q = {q₀,q₁,…q_r-1}- внутренний алфавит. Символ a₀является "пустым" (будем обозначать его L) и что все клетки ленты заполнены этим символом.

В каждый момент времени рабочая головка обозревает одну ячейку ленты и выполняет следующие действия:

1) заменяет символ в обозреваемой ячейке новым (возможно, прежним);

2) переходит в новое состояние (возможно, в прежнее);

3) сдвигается на одну ячейку (вправо R или влево L ) либо остается на месте H.

Работа машины задается системой команд вида: q_ia_j ® q_la_pD, где D Î{ R, L, H }.

Совокупность команд будем называть программой машины Тьюринга.

Среди состояний машины (головки) выделено одно, называемое заключительным (впредь мы будем считать, что это состояние q₀).

Под конфигурацией машины Тьюринга мы понимаем распределение букв алфавита А по ячейкам ленты, состояние головки и обозреваемую ячейку. Работа машины Тьюринга по программе состоит в смене конфигураций. Конфигурацию в момент времени t_i будем обозначать K t_i. Если эта конфигурация не является заключительной, то машина в соответствии со следующей командой переходит в конфигурацию K t_i+1.

Если нужно решить некоторую задачу на машине Тьюринга, исходным данным задачи сопоставляется начальная конфигурация K t₀, а ответ задачи определяется заключительной конфигурацией, в которую программа машины переводит конфигурацию K t₀.

1. Пусть требуется добавить 1 к натуральному числу n, представленному на ленте машины Тьюринга в двоичной системе счисления, то есть в алфавите {0,1}.

Решение: внешний алфавит машины будет следующим: { L, 0, 1 }.

Будем считать начальной следующую конфигурацию: Lq₁s₁…s_pL. Для того, чтобы прибавить 1 к двоичному числу n сначала необходимо "отогнать" головку машины вправо и установить ее под последней (самой младшей) цифрой двоичного числа. Если последняя цифра числа есть 0, то достаточно заменить 0 на 1 и завершить процесс, то есть перевести головку (машину) в заключительное состояние q₀.

Если же последняя цифра числа есть 1, то необходимо заменить ее на 0, а головку сдвинуть влево, чтобы "увидеть" следующий разряд двоичного числа. Если окажется, что этот разряд содержит 0, то заменить 0 на 1 и опять-таки перевести головку (машину) в заключительное состояние q₀. Если же этот разряд содержит 1, необходимо заменить ее на 0 и опять сдвинуть головку влево. И так далее, до тех пор, пока либо не встретится разряд, содержащий 0, либо головка дойдет до первого слева пустого символа L. В любом из этих случаев 0 или L следует заменить на 1 и перевести головку (машину) в заключительное состояние q₀.

Программа машины, прибавляющей 1 к двоичному числу, имеет вид:

q11 ®q11R q10 ®q10R q1L ®q2LL q20 ®q31H q21 ®q20L

q2L ®q01H q31 ®q31L q30 ®q30L q3L ®q0LR.

2. Пусть требуется перевести запись натурального числа n, изображенного в виде последовательности n "палочек" (|) n ³ 1, в двоичную запись в алфавите {0,1}. Т.е. конфигурация Lq₁…|L должна быть преобразована в Lq₀s₁s₂…s_p L, где s₁s₂…s_p - двоичная запись n.

Решение: в качестве внешнего алфавита машины берем алфавит:{ L, |, 0,1 }.

Опишем алгоритм решения задачи в словесной форме:

1. "Отогнать" головку машины влево до первого пустого символа, заменить этот символ нулем (0).

2. "Отогнать" головку машины вправо до последней черточки, заменить ее пустым символом. Запомнить, что 1 из унарного представления числа n вычтена.

3. Установить головку под младшим разрядом формируемого двоичного числа и прибавить к двоичному числу 1 (так как мы делали это при построении предыдущей машины). Запомнить, что 1 к двоичному числу прибавлена.

4. Пункты 2 и 3 повторять до тех пор, пока не исчерпается исходное число, то есть на ленте не останется "палочек".

5. Головку отогнать в крайнюю левую позицию полученного двоичного числа и остановить машину.

Программа работы машины имеет вид:

q1| ®q1|L q1L®q20R q2| ®q2|R q2L ®q3LL q3| ®q4 LL q4 | ®q4|L q40 ®q51R q41®q40L

q4 L®q51R q51 ®q51R q50 ®q50R q5| ®q2|H q5 L ®q6 LL q61 ®q61L q60 ®q60L q6 L ®q0LR

3. Составьте программу машины Тьюринга, подсчитывающую число вхождений символа a в слово Р в алфавите {a, b, c}.

Решение: пусть начальная конфигурация машины имеет вид q₁P.

Надо перевести ее в конфигурацию q₀n*P, где n – двоичное число, выражающее число вхождений символа a в слово Р в алфавите { a, b, c }.

Внешний алфавит машины: А = { a, b, c, a^’, 0, 1, *, L }.

Внутренний алфавит машины: Q = { q₀, q₁, q₂, q₃, q₄, q₅, q₆, q₇ }.

Опишем алгоритм решения задачи в словесной форме:

1. Слева от слова Р приписываем символы 0 и *.

2. Находим в слове Р вхождение символа a, заменяем его на a^’, запоминаем, перемещаем головку влево, прибавляем 1 к двоичному числу n («счетчику»).

3. Повторяем п. 2 до тех пор, пока не пройдем все слово P.

4. Убираем все штрихи в слове Р.

5. Устанавливаем головку машины под крайней левой цифрой двоичного числа n и останавливаем машину.

Программа работы машины имеет вид:

q1a ® q2aL q1b ® q2bL q1c ® q2cL q2L ® q3*L q3L ® q40R q40 ® q40R q41 ® q41R

q4*® q5*R q5b® 5bR q5c® q5cR q5a^’®q5a^’R q5a® 6a^’H q6b® q6bL q6c ® q6cL

q6a^’® q6a^’L q6* ® q6*L q60 ® q41R q61 ® q60L q6L ® q41L q5L® q7LL q7a ® q7aL

q7b ® q7bL q7c ® q7cL q7a^’® q7aL q7* ® q7*L q70 ® q70L q71 ® q71L q7L ® q0LR

Задания для самостоятельного выполнения

Дата добавления: 2014-11-20