Алгоритмическая разрешимость. 
Теоретические основы информатики

С точки зрения понятий современной вычислительной техники элементы машины Тыоринга являются упрощенными моделями отдельных компонент вычислительных устройств.

• 1. Устройство управления и устройство обращения представляют собой аналог логического блока процессора.
• 2. Бесконечная лента это модель устройства внешней памяти, в которую заносятся исходные данные и сохраняются результаты работы.
• 3. Хранимые и обрабатываемые данные это слова, записанные в алфавите S.
• 4. Совокупность направления сдвига (Е, L, R) и текущего состояния машины можно понимать как внутреннюю память.

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

Тезис Черча. Для всякой интуитивно вычислимой функции (для которой существует алгоритм ее вычисления) существует машина Тьюринга, вычисляющая значение этой функции.

Данный тезис устанавливает соответствие между неформальным определением вычислимой функции и формальным определением МТ.

Тезис Тьюринга. Для всякого алгоритма А, записанного в некотором алфавите V, может быть построена МТ, результаты работы которой совпадают с результатами алгоритма А при одинаковых входных данных.

Тезис Черча Тьюринга Дойна. Любой конечный физический процесс, не использующий аппарат, связанный с непрерывностью и бесконечностью, может быть вычислен физическим устройством.

Физический тезис Черча — Тыориига. Любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга.

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

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

В общем случае, иод проблемой разрешимости понимается сформулированный вопрос в рамках некоторой формальной теории, ответом на который является «да» или «нет».

Пример проблемы разрешимости: является ли некоторое натуральное число п простым? В качестве ответа может быть дано «да» или «нет» в зависимости от числа п.

Алгоритм, позволяющий решить проблему разрешимости, называется разрешающим алгоритмом, а сама проблема — (алгоритлшчески) разрешимой. Если же такого алгоритма не существует, то проблема называется неразрешимой.

Проблема определения простоты натурального числа является разрешимой, так как можно предложить следующий способ проверки: разделить число п на каждое из чисел 2,3,./7-/2 (для четного п) или 2,3,(п — 1)/2 (для нечетного п). Если хотя бы один остаток от деления равен 0, то ответ «нет», иначе — «да».

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

Примером неразрешимой задачи может служить проблема остановки: для некоторого алгоритма А и множества входных данных этого алгоритма определить, остановится ли когда-нибудь его выполнение? В терминах машин Тьюринга задача формулируется следующим образом: достигнет ли состояния покоя произвольная машина Тыоринга с произвольной начальной конфигурацией?

Теорема (Черча Тьюринга). Не существует алгоритма распознавания остановки произвольной машины Тыоринга для произвольной начальной се конфигурации.

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

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

Проблема нулевой (единичной) матрицы. Пусть дано некоторое конечное множество М_пхп целочисленных квадратных матриц размерности п х п. Определить, существует ли произведение конечного числа матриц из М_пхп (возможно, с повторениями) в каком-либо порядке, дающее нулевую (единичную) матрицу.

Доказано, что проблема нулевой матрицы алгоритмически неразрешима для п ^ 3, вопрос для п = 2 остается открытым. Проблема единичной матрицы неразрешима для п ^ 4, разрешима для п = 2. Для п = 3 вопрос остается открытым.

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

Десятая проблема Гильберта. Существует ли универсальный метод нахождения целочисленного решения произвольного диофантова уравнения.

где все а, — и п — целые?

Все приведенные алгоритмически неразрешимые проблемы содержат указание на произвольность рассматриваемых в них объектов. Из-за этого они получили название массовых.

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