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

число 7V=18, то, представив 18 в виде произведения степеней простых чисел 18=2 *3^, получаем, что 18 является геделевым номером слова Q=ab. Пусть задана последовательность слов в алфавите А , которую можно, например, назвать предложением в алфавите А . Тогда этой последовательности слов молшо сопоставить последовательность геделевых номеров каждого слова в том же порядке, что и слова, либо, считая, что пробел между словами имеет геделев номер (н+1), сопоставить всей последовательности один геделев номер. Например, пусть А={а,Ь,с] и задана последовательность слов P=abb cabb аа, тогда либо g{P)=g{abb\ g(cabb). giaa)=2^*3^*5\ 2'*3', либо 1^*1З'*17^*19^*23''*29'*31'. Ясно, что в данных случаях по данному номеру или последо­ вательности номеров можно единственным обра'зом восстановить исходную последовательность слов (предлолсение). Как только проведена нумерация, становится понятным, что любое преобразование слов или предложений в алфавите А в слова или предложения >4 можно свести к вычислению значений функции т= ф(«) или ф где п,п\,пъ:-,щ - геделевы номера преобразуемых слов или пред­ ложений, a m — геделев номер результата. Это следует из того, что после введения нумерации можно иметь дело уже только с соответст­ вующими номерами слов или предложений, а не с самими словами или предложениями. Очевидно, что если у нас есть метод преобразования слов (предложений) алфавита А , то есть и метод вычисления значений соответствующей функции. Действительно, чтобы найти значение ф(п) при п = а , можно по а восстановить слово (предложение), затем с помощью имеющегося метода преобразовать его в слово, являя^ ющееся результатом и по результирующему слову (предложению) найти геделев номер ф(а). Следовательно, ф(а)=р. . 252