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

Тьюринга, способную выполнять любой алгоритм, а значит работу любой машины
Тьюринга. В ней входное слово должно включать изображение программы и входное слово
интерпретируемой машины.
    Чтобы получить изображение программы интерпретируемой машины, нужно
последовательно, строка за строкой, закодировать эту программу в алфавите универсальной
машины. Универсальная машина Тьюринга должна иметь фиксированный внешний
алфавит, используемый при записи программы, включая и алфавит интерпретируемой
машины.
    Она должна быть приспособлена к приему в качестве исходной информации
всевозможных состояний устройства управления и конфигураций, в которых могут
встречаться буквы из разнообразных алфавитов со сколь угодно большим числом различных
букв.
    Это достигается путем кодирования конфигурации и программы любой заданной
машины Тьюринга в символах входного алфавита универсальной машины.                         Само
кодирование должно выполняться следующим образом:
    1) различные буквы должны заменяться различными кодовыми группами, но одна и та
же буква должна заменяться всюду, где бы она не встречалась, одной и той же кодовой
группой;
    2) строки кодовых записей должны однозначным образом разбиваться на отдельные
кодовые группы;
    3) должна существовать возможность распознать, какие кодовые группы соответствуют
различным сдвигам управляющей головки (R, L, E), и различать кодовые группы,
соответствующие буквам внутреннего алфавита и буквам внешнего алфавита.
    Рассмотрим пример такого кодирования для машины Тьюринга Т, имеющей внешний
алфавит A = {a1, a2, ... , ak} и внутренний алфавит Q = {q1, q2, ... , qz}. Если внешний алфавит
состоит из символов А = {0, 1}, то условия кодирования будут соблюдены при следующем
способе кодирования.
   1. В качестве кодовых групп возьмем 3+k+m различных слов вида 100...01, где между
единицами проставляются нули; k - число символов внешнего алфавита; m - число
состояний устройства управления.
   Тогда разбивка строк на кодовые группы производится путем выделения
последовательностей нулей, заключенных между двумя единицами.
    2. Сопоставление кодовых групп исходным символам внешнего и внутреннего
        алфавитов осуществляется согласно следующей таблице кодирования:

                                          Буква         К о д о в а я гр у п п а

                                             R                       101
                                             E                      1001
                                             L                     10001
                                                                                                          Ч ет н о е
                                             a1                    100001         - 4 нуля                 ч и сл о
                        В н еш н и й         a2               10000001           - 6 н у л ей             н у л ей ,
                        а л фа в и т         .................................                           б о л ь ш ее
                                             ak             1 0 ...........0 1   2 ( k + 1) н у л е й      ч ем 2


                       В н у т р ен н и й q1                  1000001            - 5 н у л ей            Н еч ет н о е
                         а л фа в и т     q2             100000001               - 7 н у л ей              ч и сл о
                       (со ст о я н и я )                                                                 н у л ей ,
                                          .................................
                                                                                                         б о л ь ш ее
                                          qm        1 0 ................0 1      2 ( m + 1) + 1 н у л е й ч е м 3



    Например, для машины Тьюринга, которая перерабатывает слово bcad в слово bccd,
входное слово в универсальной машине Тьюринга с данным кодом будет представлено
следующей строкой:
      10000001 1000000001 100001 100000000001,