Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 23 стр.

самоприменимости машин Тьюринга, имея в виду их применение к своим линейным
изображениям.
    Таким образом, возникает задача: как узнать, является ли самоприменимым тот или
иной алгоритм.
    Проблема распознавания самоприменимости алгоритмов состоит в том, чтобы найти
единый конструктивный прием, позволяющий за конечное число шагов по схеме любого
данного алгоритма узнать, является алгоритм самоприменимым или несамоприменимым.
    Доказательство того, что общего алгоритма распознавания самоприменимости не
существует, можно проводить, используя алгоритмические системы Тьюринга. На основе
этого доказательства было показано, что проблема распознавания самоприменимости
алгоритмически неразрешима.

      3.11. Задания для самостоятельной работы
    1. Построить машину Тьюринга, выполняющую операцию конкатенации двух цепочек,
заданных во входном алфавите А = {0, 1, *, ε}.
    2. Построить машину Тьюринга, выполняющую операцию копирования входной
цепочки, заданной в алфавите А = {1, *, ε }, где символ “*” используется в качестве
разделителя двух цепочек.
    3. Построить машину Тьюринга в алфавите А={0, 1}, которая, начав работу с последней
единицы массива из единиц, сдвигает его на одну ячейку влево, не изменяя остального
содержимого ленты. Головка останавливается на первой единице перенесенного массива.
    4. По заданной совокупности команд машины Тьюринга Т и начальной конфигурации К
найти заключительную конфигурацию.
       4.1.
       q01 → q01R,         q10 → qz1E,
       q00 → q11R,         q11 → q11L,
       а) К = 1101q001;   б) К = 101q0010.
       4.2.
       q00 → q01L,       q11 → q00R,
       q01 → q11R,       q10 → qz0L,
       а) K = 1q1 0111; б) K = 1q11111.
       4.3.
       q00 → q10L,       q10 → q11L,
       q01 → q00R,        q11 → qz0R,
       а) K = 1000q1 01; б) K = 11q111101.

     5. Построить машину Тьюринга, которая во входной цепочке, заданной в алфавите А =
{0, 1, ε}, переставляет единицы и нули так, чтобы все единицы были в начале, а нули в конце
цепочки.
     6. Построить композицию Т1⋅Т2 машин Тьюринга Т1 и Т2 по паре состояний (q1z, q20) и
найти результат применения композиции Т1⋅Т2 к слову D.

    6.1. Машины Т1 и Т2 заданы таблицами соответствия:


                                     q10           q11           q12
                  T1:       0        q1z0L         q120R         q100R
                            1        q111R         q121R         q100R

                                             q20           q21