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

неразрешимость этих задач. Для каждой конкретной задачи, напри­ мер, для каждого данного слова Р может быть и можно выяснить, применим к нему "данный нормальный алгоритм или нет, но нет алгоритма, позволяющего выяснить применимость любого нормаль­ ного алгоритма к любому слову. Это означает, что рассматриваемый класс задач достаточно обширен и надо как-то разумно делить их на подклассы и искать для них разрешающие алгоритмы. 2. Теоремы об алгоритмической неразрешимости показывают, что математика не сводится к построению алгоритмов, 3. Область применения алгоритмов весьма широка и к ней относятся не только вычислительные процессы. Более того, для многих проблем, считающихся трудными, теоретически построить алгоритм можно, но его реализация сопряжена с очень долгим счетом и необходимостью запоминать большое количество промежуточных результатов. Создание быстродействующих вычислительных машин значительно расширило круг решаемых задач. § 14. Сведение любого преобразования слов в алфавите к вычислению значений целочисленных функций Пусть А - алфавит, содержащий п букв. Поставим в соот­ ветствие каждой букве а ( а е А ) число (геделев номер) g { a ) из чисел причем различным буквам поставим в соответствие различные числа (геделевы номера). Очевидно, что по каждому g ( a ) всегда можно восстановить букву. Если задано некоторое слово F, например, P=aic\ak2--Mkm (а/^вА), то сопоставим ему геделев номер: g(P)=2'' ЗИ5 " где bi=g{akj и - т-е простое число. Легко видеть, что таким образом можно определить геделев номер каждому слову Р и по каждому геделеву номеру g ( P ) легко восстановить слово, которому соответствует этот номер. Пример. Пусть А={а,Ь,с}. Тогда можно положить g(a)=l, g i b ) - 2 , g(c)=3. Если P=aaba, то g(P)=2'*3'*5^*7'. Если же задано 251