Применение машин тьюринга к словам
жүктеу/скачать 344.5 Kb.
|
| Практические задания к разделу 5
ПРИМЕНЕНИЕ МАШИН ТЬЮРИНГА К СЛОВАМ 5.1. Имеется машина Тьюринга с внешним алфавитом А={а0, 1}, алфавитом внутренних состояний Q={q0, q1}, и со следующей функциональной схемой (программой):
(В столбце q0 ничего не написано, потому что q0 – заключительное состояние машины, т.е. такое состояние, оказавшись в котором машина останавливается. Функциональную схему или программу кратко можно записать в виде последовательности из двух команд: q1а0 q01, q11 q11П.) Определите, в какое слово переработает машина каждое из следующих слов, если она находится в начальном состоянии q1 и обозревает указанную ячейку: а) 1ao11aoao11 (обозревается ячейка 4, считая слева); б) 11ao111ao1 (обозревается ячейка 2); в) 1aoao111 (обозревается ячейка 3); г) 1111а011 (обозревается ячейка 4); д) 11ao1111 (обозревается ячейка 3); е) 1111111 (обозревается ячейка 4); ж) 11111 (обозревается ячейка 5); з) Изобразите схематически последовательность конфигураций, возникающих на ленте на каждом такте работы машины. Решение. а) Изобразим схематически начальную конфигурацию (начальное положение машины):
Схема означает, что машина находится в состоянии q1 и обозревает ячейку, в которой записана буква 1, в соседней слева ячейке записана та же буква, а в соседней справа ячейке записана буква а0 (т. е. согласно нашему соглашению ничего не записано) и т. д. Ничего не записано и во всех непоказанных ячейках ленты. На первом такте работы согласно команде q11 q11П машина остается в прежнем состоянии q1, в обозреваемую ячейку вписывает букву 1 (т. е. фактически оставляет уже вписанную в эту ячейку букву 1 неизменной ) и переходит к обозрению следующей правой ячейки (т. е. ячейки 5). Изобразим схематически положение, в котором оказалась машина:
На втором такте работы согласно команде q1ao qo1 машина вписывает в обозреваемую ячейку 5 букву 1, продолжает обозревать ту же ячейку и переходит в состояние q0, т. е. останавливается. Создавшаяся конфигурация имеет вид:
Таким образом, из данного начального положения слово 1ao11aoao11 перерабатывается машиной в слово 1ao111ao11. 5.2. Дана машина Тьюринга с внешним алфавитом А = {а0, 1}, алфавитом внутренних состояний Q = { q0, q1, q2, q3, q4, q5, q6, q7 } и со следующей функциональной схемой (программой):
Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина каждое из следующих слов, исходя из начального стандартного положения (стандартным считается такое положение, когда машина находится в состоянии q1 и обозревает крайнюю правую ячейку из тех, в которых записано перерабатываемое слово): а) 11111; б) 111111; в) 1111; г) 1111111; д) 111; е) 1ao111aoao1111; ж) 11aoao111111; з)11ao111. Решение. д) Выписываем последовательность конфигураций машины при переработке ею слова 111 из начального стандартного положения:
Итак, слово 111 из начального стандартного положения перерабатывается машиной в слово 1. 5.3. Машина Тьюринга определяется следующей функциональной схемой:
Определите, в какое слово перерабатывает машина каждое из следующих слов, исходя из начального стандартного состояния (определение которого см. в задаче 5.2). После этого постарайтесь усмотреть общую закономерность в работе машины: а) 111 * 111; б)1111 * 11; в) 111 * 1; г) 1 * 11; д) 11 * 111; е) 11111 * ; ж) * 1111.
Определите, в какое слово перерабатывает машина каждое из следующих слов, исходя из стандартного начального состояния: а) 111 * 11; б) 11 * 11; в) 1111 * 1; г) 11111 * 111; д) 11111 * 1111. Постарайтесь выявить общую закономерность в работе машины.
и для следующих слов определите, в какое слово переработается каждое из них данной машиной, исходя из начального положения, при котором машина находится в состоянии q1 и обозревается указываемая ячейка: а) 11111 (обозревается ячейка 2, считая слева); б) 111 (обозревается ячейка 1); в) 1111111111 (обозревается ячейка 4); г) 111111 (обозревается ячейка 2); д) 111111111111111 (обозревается ячейка 6). Какова общая закономерность работы машины? 5.6. Машина Тьюринга с внешним алфавитом А = {а0, 1} определяется следующей программой:
Остановится ли когда-нибудь эта машина, если она начнет перерабатывать следующее слово (в начальный момент; в состоянии q1, машина обозревает ячейку, в которой записана самая левая буква перерабатываемого слова): а) 111а0а01; б) 11а0а011а01; в) 111111? Если остановка происходит, то какое слово получается в результате, какая ячейка и в каком (перед остановкой) состоянии обозревается?
если она начнет перерабатывать следующее слово, начав в состоянии q1 обозревать ячейку, в которой записана самая левая буква перерабатываемого слова: а) 1111а01; б) 11111; в) 1а01а01? Если машина остановится, то какова ее заключительная конфигурация?
жүктеу/скачать 344.5 Kb. Достарыңызбен бөлісу:
|
111 (обозревается ячейка k).