Математическая логика и теория алгоритмов. Стенюшкина В.А. - 63 стр.

      Наряду с рекурсивными функциями и машинами Тьюринга нормальные
алгоритмы (НА) получили известность в качестве одного из наиболее удобных
уточнений общего интуитивного представления об алгоритме. Понятие НА бы-
ло выработано А.А. Марковым (1947).
      Нормальные алгоритмы оперируют со словами конечной длины, преобра-
зуя их друг в друга с помощью подстановок, то есть замены одних частей слова
на другие. Любой нормальный алгоритм в фиксированном алфавите А вполне
определяется указанием его схемы – упорядоченного конечного списка подста-
новок типа U→V (U заменяется на V), где U, V – слова в алфавите А. Заключи-
тельная подстановка записывается в виде U→ • V.
      Нормальный алгоритм работает следующим образом. Пусть Р – заданное
слово в фиксированном алфавите. Принимаем его за начальное слово Р0 и стро-
им следующее слово Р1. Если слово Рi (i ≥ 0) построено и работа алгоритма не
закончена, то просматриваются подстановки (слева направо) и первая подхо-
дящая применяется. Если эта подстановка заключительная, работа заканчивает-
ся успешно, если не заключительная, то построено слово Рi +1 и процесс продо-
лжается. Если нет подходящей подстановки, алгоритм не применим к данному
слову. Возможна также бесконечная работа алгоритма – неуспех.
      Пример - Дан алфавит русского языка и схема S = я→ у, л→ у, с→ м, в→
б, р→ m, m→•р, о→ х, н→ а. Тогда, имея слово «слон», можно получить слово
«муха». (Проверьте!)
      В теории алгоритмов строго доказано, что по своим возможностям пре-
образования нормальных алгоритмов эквивалентны частичным рекурсивным
функциям и машинам Тьюринга. Соглашение о том, что для всякого алгоритма
А в каком – либо алфавите может быть построен нормальный алгоритм, носит
название принципа нормализации. Этот принцип равносилен тезису Черча и
тезису Тьюринга.

       2.4 Алгоритмические проблемы

      Алгоритмическая проблема (АП) – проблема, в которой требуется найти
единый метод (алгоритм) для решения бесконечной серии однотипных единич-
ных задач.
      Примеры
      1 Найти алгоритм для выяснения, имеются ли целые корни у данного ал-
гебраического уравнения а0 xn + a1 x n-1 +…+ a n = 0, где а0, a1 ,…, a n - целые чис-
ла. Искомый алгоритм существует и основан на факте, что, если такое уравне-
ние имеет целый корень p, то p должно быть делителем числа a n , и для данного
уравнения можно найти все делители числа a n , и все их по очереди проверить.
Эта задача алгоритмически разрешима.
      2 Аналогичная проблема для для уравнения P(x 1 ,…, x m) = 0, где P(x 1
,…, x m ) – произвольный многочлен с целыми коэффициентами от любого чис-
ла m неизвестных (10 – я проблема Гильберта) неразрешима.