Проблемы распознавания самоприменимости и применимости

Проблема самоприменимости МТ состоит в следующем. Пусть на ленту МТ Т записан ее собственный шифр Ш(Т). МТ Т начинает работу с крайнего левого непустого символа, находясь в состоянии . Если, начав вычисление в указанной конфигурации, МТ Т остановится за конечное число шагов, то она называется самоприменимой, иначе несамоприменимой. Проблема самоприменимости состоит в установлении для произвольной МТ Т свойства: является ли Т самоприменимой или нет.

 

Теорема 8.2. Проблема распознавания самоприменимых машин Тьюринга алгоритмически неразрешима.

Доказательство. От обратного: предположим, что проблема самоприменимости алгоритмически разрешима, т.е. существует МТ , которая для произвольной МТ Т переводит конфигурацию в конфигурацию , если МТ Т самоприменима, и в если МТ Т несамоприменима. Здесь – заключительное состояние МТ . Используя команды , построим МТ , добавив две новые команды

()

, ()

где – заключительное состояние МТ . Состояние , которое было заключительным для МТ , для таковым не является.

Если МТ будет запущена с записью на ленте шифра , являющегося шифром самоприменимой МТ Т, то она, согласно командам МТ , за конечное число шагов перейдет в конфигурацию и «зациклится» в силу команды (). Получили, что МТ не применима к шифрам самоприменимых машин. Если МТ будет запущена с записью на ленте шифра , являющегося шифром несамоприменимой МТ Т, то , начав работу, через некоторое число шагов перейдет в конфигурацию и по команде (), остановится в состоянии . Получили, что МТ применима к шифрам несамоприменимых машин.

Сама машина может быть либо самоприменимой, либо несаморименимой. Согласно доказательству, получили, что если она самоприменима то должна быть применима к собственному шифру, однако не применима к шифрам самоприменимых машин; если не самоприменима, то она должна быть не применима к собственному шифру, однако получили, что применима к шифру несамоприменимых машин.

Таким образом, предположение существования МТ , решающей задачу самоприменимости, привело к противоречию, что доказывает алгоритмическую неразрешимость рассматриваемой проблемы ¡.

Метод алгоритмической сводимости

Рассмотрим метод алгоритмической сводимости, который позволяет доказывать неразрешимость некоторой проблемы, если к ней сводится другая проблема, неразрешимость которой уже доказана.

Пусть и – две проблемы. Пусть существует МТ Т, которая позволяет преобразовывать любую задачу в задачу , т.е. , таким образом, что задача дает ответ «да» тогда и только тогда, когда задача дает ответ «да». В случае, когда такое преобразование имеет место, то считается, что проблема алгоритмически сводится к проблеме .

 

Теорема 8.3. Если проблема неразрешима и сводится к проблеме , то проблема также является неразрешимой.

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

 

Отношение сводимости обладает свойством транзитивности: если сводится к , а сводится к , то сводится к .

Будем считать, что применяется метод алгоритмической сводимости если, используя теорему 8.3 и неразрешимую проблему устанавливается неразрешимость проблемы .

Рассмотрим проблему останова МТ. Нужно по заданной МТ Т и слову на ленте выяснить, применима ли МТ Т к слову или нет, т.е. остановится ли она за конечное число шагов, начав работу в конфигурации .

 

Теорема 8.4. Проблема останова неразрешима.

Доказательство. Покажем, что неразрешимая проблема самоприменимости сводится к проблеме останова. Действительно, алгоритм преобразования состоит в переписи Шифра МТ Т в качестве исходного слова . МТ Т начинает работу с конфигурации , где . МТ применима к слову тогда и только тогда, когда – самоприменима. В силу построенного сведения, проблема останова неразрешима ¡.

Примеры алгоритмически неразрешимых проблем

Рассмотрим еще несколько проблем, которые являются алгоритмически неразрешимыми.

1. Проблема выводимости в Марковской системе подстановок из заданного слова состоит в том, чтобы для произвольного слова выяснить, выводимо ли оно из слова путем применения подстановок нормальной схемы.

Теорема 8.5. Существует система нормальных подстановок и слово такие, что проблема выводимости из слова в схеме нормальных подстановок алгоритмически неразрешима ¡.

 

2. Неразрешимой является проблема эквивалентности алгоритмов: по двум данным алгоритмам нельзя узнать, вычисляют они одну и ту же функцию или нет.

Каждый кто сталкивается с написанием компьютерных программ, знает, что по тексту программы, не запуская ее в работу, трудно понять, что она делает (какую функцию вычисляет).

3. Не существует алгоритма, позволяющего для каждой формулы логики предикатов определить, будет ли эта формула выполнима или общезначима.

4. 10-ая проблема Гильберта (поставлена в 1901 г. на международном математическом конгрессе в Париже): Требуется найти алгоритм, определяющий для любого диафантова уравнения вида f (x, y,…, z)=0, где f (x, y,…, z) – многочлен с целыми показателями степеней и целыми коэффициентами, имеет ли оно целочисленное решение.

В общем случае эта проблема долго оставалась не решенной, и только в 1970 г. советский математик Ю.В. Матиясевич доказал ее неразрешимость.

 

Итак, отметим, что алгоритмическая неразрешимость означает лишь отсутствие единого способа для решения всех единичных задач данной массовой проблемы, в то время как каждая индивидуальная задача проблемы вполне может быть решена своим индивидуальным способом. Более того, может оказаться разрешимой своим индивидуальным способом не только каждая отдельная задача этого класса, но и целые подклассы задач данного класса. Поэтому, если проблема неразрешима в общем случае, нужно искать ее разрешимые частные случаи.

 

[1] ТЬЮРИНГ, Алан Матисон (Turing) (1912–1954) – английский математик, логик, криптограф. Окончил Кембриджский ун-т (1935). В 1936 г., используя схему абстрактной машины, доказал ряд важных положений в области мат.логики. В годы Второй мировой войны возглавил работу по созданию вычислительных машин в Нац. физической лаборатории. Его работы по сооружению первых ЭВМ и развитию методов программирования дали основу исследований в области искусственного интеллекта.

 

[2] АККЕРМАН, Вильгельм (Ackermann) (1896–1962) – Немецкий математик и логик, ученик Д. Гильберта. Родился в Шёнебек. Был профессором в Мюнстере. Основные труды относятся к математической логике. Книга «Основы теоретической логики», написанная совместно с Д. Гильбертом, переведена на русский язык в 1947.

[3] МАРКОВ, Андрей Андреевич (1903–1979) – советский математик, чл.-корр АН СССР. Окончил Ленинградский гос. университет (1924). Основные труды по теории динамических систем, топологии, топологической алгебре, теории алгоритмов и конструктивной математике. Доказал неразрешимость проблемы равенства в ассоциативных системах (1947), проблемы гомеоморфии в топологии (1958), создал школу конструктивной математики и логики в СССР, автор понятия нормального алгорифма.