Тема 8.3 Уточнения понятия алгоритм.

Существует четыре уточнения понятия алгоритм (тезисы):

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

2. Тезис Чорча: Функция f, определенная на множестве N вычислима тогда и только тогда, когда она является частично рекурсивной.

3. Нормальный алгоритм Маркова:

, где , все р_i, a_i – слова в алфавите А, А – конечный алфавит.

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

Заменяем самое левое вхождение р_i в слове самым правым вхождением a_i. Если ни одно р_i не входит в слово , то будем считать, что алгоритм не применим к этому слову.

Заменив р_i на a_i, получим новое слово и повторим процесс.

Процесс заканчивается на том шаге, когда .

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