О.Б. Лупанов - Курс лекций по математической логике (1109964), страница 9
Текст из файла (страница 9)
Тогда построим машину Mприменимую к коду несамоприменимых машин, добавлением к MS двух команд: q0 0 → q0′ 0S и q0 1 → q0 1S.f, а некоторое новое состояние q0′ сделаем для неё стоповым.При этом q0 сделаем «обычным» состоянием MfПрименим M саму к себе. Она не может быть самоприменимой, поскольку в этом случае MS выдаст 1, иf зациклится. Но она не может быть и несамоприменимой, поскольку в этом случае MS выдаст 0, и онаMостановится. Противоречие, значит MS не существует. Поставим вопрос: существует ли машина MP , определяющая, применима ли некоторая машина M к входнымданным B.
Входные данные MP — код вида K(M )△B.Теорема 6.2. Машина MP не существует, т. е. проблема применимости алгоритмически неразрешима. Пусть существует MP . Присоединим к ней спереди машину удвоения слова MD . Подсунем ей в качествевходных данных код K(M ). Она удвоит его, и затем решит, применима ли M к K(M ), то есть решит проблемусамоприменимости, что невозможно. Противоречие. 23В заключение приведём без доказательства более общую теорему.Теорема 6.3 (Райса). Задача определения того, обладает ли некоторый объект нетривиальным свойством, алгоритмически неразрешима. Свойство называется нетривиальным, если существуют объекты, обладающие им, и объекты, не обладающие им.24.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
