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

    100000001 10000001 10000000001 1000000001 10001
    10000000001 1000000001 1000001 10000001 101
    1000001 1000000001 100000001 1000000001 101
    100000001 1000000001 1000001 1000000001 101
    1000001 100000000001 1000000000001 100000000001       1001.
    Таким образом, если какая-либо машина Тьюринга Т решает некоторую задачу, то и
универсальная машина Тьюринга способна решить эту задачу при условии, что кроме кодов
исходных данных этой задачи на ее ленту будет подан код программы машины Т. Задавая
универсальной машине Тьюринга Тu изображение программы любой данной машины
Тьюринга Тn и изображение любого ее входного слова xn, получим изображение выходного
слова yn, в которое машина Тn переводит слово xn .
    Если же алгоритм, реализуемый машиной Тn, не применим к слову xn, то алгоритм,
реализуемый универсальной машиной Тu, также не применим к слову, образованному из
изображения xn и программы машины Тn.
    Таким образом, машина Тьюринга Тn может рассматриваться как одна из программ для
универсальной машины Тu .
    В связи с существованием универсальной машины Тьюринга таблицы соответствия,
описывающие различные состояния устройства управления машины, имеют двоякое
назначение:
    1) для описания состояний устройства управления специальной машины Тьюринга,
реализующей соответствующий алгоритм;
    2) для описания программы, подаваемой на ленту универсальной машины Тьюринга,
при реализации соответствующего алгоритма.
    Современные ЭВМ строятся как универсальные; в запоминающее устройство наряду с
исходными данными поставленной задачи вводится также и программа ее решения.
    Однако в отличие от машины Тьюринга, в которой внешняя память (лента) бесконечна, в
любой реальной вычислительной машине она конечна.

      3.10. Алгоритмически неразрешимые проблемы
    Свойство массовости алгоритмов означает, что они предназначены для решения
некоторой массовой проблемы, формулируемой в виде отображения множества входных
слов в соответствующие им выходные слова. Поэтому всякий алгоритм можно
рассматривать как универсальное средство для решения целого класса задач.
    В теории алгоритмов известны некоторые задачи, для решения которых не существует
единого универсального приема. Однако алгоритмическая неразрешимость проблемы
решения задач того или иного класса не означает невозможность решения любой конкретной
задачи из этого класса. В данном случае речь идет о невозможности решения всех задач
одного класса одним и тем же приемом.
    Таким образом, задачи (проблемы) можно разделить на алгоритмически разрешимые и
алгоритмически неразрешимые.
         Обычно алгоритмическая неразрешимость новых задач доказывается методом
   сведения к этим задачам известных алгоритмически неразрешимых задач. Тем самым
   доказывается, что если бы была разрешима новая задача, то можно было бы решить и
   заведомо неразрешимую задачу. Применяя метод сведения, обычно ссылаются на
   искусственные задачи, которые не представляют самостоятельного интереса, но для
   которых легко непосредственно доказать их разрешимость. К числу таких задач относится
   проблема распознавания самоприменимости.
    Самоприменимыми называются алгоритмы, которые, начав работу над собственным
описанием, рано или поздно останавливаются. Если же алгоритм в таком случае
зацикливается, он называется несамоприменимым. Аналогично можно говорить о