Понятие алгоритмической разрешимости

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

И теория алгоритмов позволяет оценить алгоритмическую разрешимость тез или иных задач.

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

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

I подход: машина Тьюринга

II подход: алгоритм Маркова

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

Машина Тьюринга

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

Эти алфавиты носят названия “внешние алфавиты”.

	внутренние алфавиты

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

Логический блок осуществляет чтение из любой ячейки непрерывной ленты входной переменной и записывает на ее место выходную переменную.

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

В машине Тьюринга 3 управления:

П – переместиться на одну ячейку вправо;

Л – переместиться на одну ячейку влево;

Н – не перемещаться(обозревать ту же самую ячейку);

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

- выходная переменная, замещающая входную;

- управление в конце данного такта;

- состояние в следующем такте.