Словарные множества и словарные функции

Математическая логика и теория алгоритмов Глава 2. Теория алгоритмов Параграф 5. Словарные множества и словарные функции Произвольная конечная совокупность букв (символов) называется алфавитом алфавитом.. Всякая конечная последовательность букв из данного алфавита называется словом в данном алфавите. Например, если алфавит состоит из букв { a, b, c } , то a, aba, abcba, baa, bc слова в этом алфавите. В то же время a, aba, baa - слова в алфавите { a, b } . Поэтому надо обязательно указывать, в каком алфавите рассматриваются слова. Если задан алфавит A = { a 1 , a 2 , … , a p } , то слово a i1 a i2 … a in в этом алфавите будем обозначать в виде вектора ⏨ x = a i1 a i2 … a in . Пусть ⏨ a, ⏨ b - слова, записанные в алфавите, не содержащем ⏨ aи⏨ b в качестве символов. Тогда через ⏨ a⏨ b обозначим слово, полученное из слова ⏨ a путем приписывания справа слова ⏨ b . Слово ⏨ a⏨ b называется произведением слов ⏨ aи⏨ b . Легко видеть, что операция умножения слов ассоциативна ассоциативна,, но не коммутативна. коммутативна. Слово, не содержащее ни одной буквы алфавита, называется пустым пустым.. Будем его обозначать через 𝛬. Очевидно, что a 𝛬 = 𝛬⏨ a=⏨ a , т.е. 𝛬 является нейтральным элементом во множестве всех слов ⏨ алфавита. Обозначим через S A множество всех слов алфавита A. Из вышесказанного следует, что S A образует не коммутативную полугруппу с единицей 𝛬. Любое подмножество слов из S A будем называть словарным множеством алфавита A. Любое отображение из S A × S A ×…× S A (n раз) в S A называется словарной функцией от n переменных алфавита A. Обозначается функция стандартно как F( ⏨ x 1, ⏨ x 2, … , ⏨ x n ) , где ⏨ x i - слова алфавита A. Пусть дан алфавит A = { a 1 , a 2 , … , a p } . Проведем так называемую алфавитную нумерацию слов из S A . Номер пустого слова по определению полагается равным 0. Пусть дано слово ⏨ a = aik aik-1 … ai1 ai0 . Номером слова ⏨ a называется число C( ⏨ a ) = i0 + i1 p +…+ ik p k , 1 ⩽ im ⩽ p, то имеем функцию 𝛼(n), ставящую любому натуральному числy n в соответствие слово ⏨ x = aik aik-1 … ai1 ai0 , номер которого равен n. Определение. Множество M слов в алфавите A называется примитивно рекурсивным (частично рекурсивным, рекурсивным, рекурсивно перечислимым), если таковым является множество номеров слов из M. Очевидно, имеет место Теорема.. Имеют место следующие утверждения: Теорема 1. Каждое конечное множество слов алфавита A примитивно рекурсивно. 2. Объединение и пересечение конечной системы примитивно рекурсивных (рекурсивных, рекурсивно перечислимых) множеств есть множество того же типа. ⏨ = SA \ M примитивно рекурсивного (рекурсивного) множества есть 3. Дополнение M множество того же типа. ⏨ и SA рекурсивно перечислимо, то M и M ⏨ рекурсивны 4.Если множества M и M (теорема Поста). Определение. Числовая n-местная функция f(x 1 , … , x n ) называется функцией, представляющей словарную функцию F( ⏨ x 1, ⏨ x 2, … , ⏨ x n ) в данном алфавите, алфавите, если F(𝛼(x1 ), … , 𝛼(xn )) = 𝛼(f(x1 , … , xn )) для всех x1 , … , xn , для которых определено значение f(x 1 , … , x n ) . Теорема. Каждая частичная словарная функция обладает единственной Теорема. представляющей числовой, и наоборот, каждая числовая функция является представляющей для некоторой словарной. Доказательство.. Пусть F( ⏨ Доказательство x 1, ⏨ x 2, … , ⏨ x n ) - некоторая словарная функция. Для любого набора чисел x 1 , … , x n определим f(x 1 , … , x n ) = C(F(𝛼(x 1 ), … 𝛼(x n ))) . Легко проверить, что полученная функция f(x 1 , … , x n ) будет представляющей для функции F( ⏨ x 1, … , ⏨ x n) . Обратно, пусть задана числовая функция f(x 1 , … , x n ) . Для любых слов ⏨ x 1, … , ⏨ xn зададим F( ⏨ x 1, … , ⏨ x n ) = 𝛼(f(C(x1 ), … , C(xn ))) . Для построенной функции F( ⏨ x 1, … , ⏨ x n ) заданная числовая функция f(x1 , … , xn ) будет представляющей. Определение.. Словарная функция F( ⏨ Определение x 1, … , ⏨ x n ) называется примитивно рекурсивной (частично рекурсивной, общерекурсивной), если таковой является представляющая ее числовая функция. Следующая теорема играет очень важную роль. Теорема.. Пусть дан алфавит A = { a 1 , a 2 , … , a p } и A 1 = { a 1 , … , a p , a p+1 , … , a q } Теорема некоторое его расширение. Имеют место следующие утверждения: 1. Словарное множество M в алфавите A примитивно рекурсивно (рекурсивно, рекурсивно перечислимо) в алфавит A тогда и только тогда, когда оно имеет тот же тип в алфавите A 1 . 2. Частичная словарная функция F( ⏨ x 1, … , ⏨ x n ) , определенная в алфавите A, частично рекурсивна в алфавите A тогда и только тогда, когда она частично рекурсивна в алфавите A 1 . 3. Всюду определенная на S A словарная функция F( ⏨ x 1, ⏨ x 2, … , ⏨ x n ) примитивно рекурсивна (общерекурсивна) в алфавите A тогда и только тогда, когда она может быть доопределена до примитивно рекурсивной (общерекурсивной) функции в алфавите A 1 . По аналогии с числовыми функциями для словарных функций можно ввести операции подстановки, рекурсии и другие. Определение.. Простейшими словарными функциями в алфавите A = { a 1 , … , a p } Определение называются функции следующего вида: 1) 0( ⏨ x ) = 𝛬 - оператор аннулирования; 2) S i ( ⏨ x) = ⏨ x ai - оператор сдвига на букву ai , i = 1, 2, … , p ; n 3) ⏨ Im (⏨ x 1, … , ⏨ x n) = ⏨ x m , 1 ⩽ m ⩽ n, - оператор проектирования на слово ⏨ xm. Уже было показано, что функции 0( ⏨ x ) и Si ( ⏨ x ) примитивно рекурсивны. Далее, n n Im (x1 , … , xn ) = xm = C(𝛼(xm )) = C ⏨ Im (𝛼(x1 ), … , 𝛼(xn )) . Это равенство говорит о n том, что простейшая числовая функция I m (x1 , … , xn ) является представляющей для n простейшей словарной функции ⏨ Im (⏨ x 1, … , ⏨ x n ) . Следовательно, функция n ⏨ Im (⏨ x 1, … , ⏨ x n ) примитивно рекурсивна. Следующая теорема говорит о том, что операция суперпозиции (подстановки), примененная к примитивно рекурсивным (частично рекурсивным, общерекурсивным) словарным функциям, дает в итоге функцию того же типа. Теорема. Пусть G 1 ( ⏨ x 1, … , ⏨ x n ), … , G m ( ⏨ x 1, … , ⏨ x n ), G( ⏨ x 1, … , ⏨ x m ) - словарные функции, а g 1 (x 1 , … , x n ), … , g m (x 1 , … , x n ), g(x 1 , … , x m ) - представляющие их числовые функции, соответственно. Тогда 1) функция f(x 1 , … , x n ) = g(g 1 (x 1 , … , x n ), … , g m (x 1 , … , x n )) является представляющей функцией для словарной функции F( ⏨ x 1, … , ⏨ x n ) = G(G1 ( ⏨ x 1, … , ⏨ x n ), … , G m ( ⏨ x 1, … , ⏨ x n )) . 2) функция F( ⏨ x 1, … , ⏨ x n ) = G(G1 ( ⏨ x 1, … , ⏨ x n ), … , G m ( ⏨ x 1, … , ⏨ x n )) является той словарной функцией, для которой f(x 1 , … , x n ) = g(g 1 (x 1 , … , x n ), … , g m (x 1 , … , x n )) является представляющей числовой функцией. Доказательство.. Доказательство F(𝛼(x1 ), … , 𝛼(xn )) = G(G1 (𝛼(x1 ), … , 𝛼(xn )), … , Gm (𝛼(x1 ), … , 𝛼(xn ))) = = G(𝛼[g1 (C[𝛼(x1 )], … , C[𝛼(xn )])], … , 𝛼[gm (C[𝛼(x1 )], … , C[𝛼(xn )])]) = = G(𝛼[g1 (x1 , … , xn )], … , 𝛼[gm (x1 , … , xn )]) = = 𝛼(g(C(𝛼[g1 (x1 , … , xn )]), … , C(𝛼[gm (x1 , … , xn )]))) = = 𝛼(g(g1 (x1 , … , xn ), … , gm (x1 , … , xn ))) Отсюда C(F(𝛼(x 1 ), … , 𝛼(x n ))) = C(𝛼(g(g 1 (x 1 , … , x n ), … , g m (x 1 , … , x n )))) = = g(g1 (x1 , … , xn ), … , gm (x1 , … , xn )) = f(x1 , … , xn ) . Аналогично доказывается утверждение 2). Следствие.. Суперпозиция примитивно рекурсивных (частично рекурсивных, Следствие общерекурсивных) словарных функций есть словарная функция того же типа. Определение.. Говорят, что (n + 1) -местная словарная функция F( ⏨ Определение x 1, … , ⏨ x n, ⏨ y) получена примитивной словарной рекурсией из n-местной словарной функции G( ⏨ x 1, … , ⏨ x n ) и (n + 2) -местных словарных функций Hi ( ⏨ x 1, … , ⏨ x n, ⏨ y, ⏨ z ) , если выполнены следующие условия: 1) F( ⏨ x 1, … , ⏨ x n , 𝛬) = G( ⏨ x 1, … , ⏨ x n) ; 2) F( ⏨ x 1, … , ⏨ x n, ⏨ y ai ) = Hi ( ⏨ x 1, … , ⏨ x n, ⏨ y , F( ⏨ x 1, … , ⏨ x n, ⏨ y )) , i = 1, 2, … , p . Теорема. Пусть словарная функция F получена примитивной словарной рекурсией из Теорема. функций G, H 1 , … , H p . Тогда числовая функция f, представляющая функцию F, может быть получена из соответствующих представляющих функций g, h 1 , … , h p и некоторых простейших числовых функций с помощью конечного числа операций подстановки и примитивной рекурсии. В частности, если функции G, H 1 , … , H p примитивно рекурсивны, то функция F также примитивно рекурсивна. Теорема.. Для того, чтобы словарная функция F( ⏨ Теорема x 1, … , ⏨ x n ) в алфавите A была примитивно рекурсивной, необходимо и достаточно, чтобы она могла быть получена из простейших словарных функций конечным числом операций подстановки и словарной рекурсии. Математическая логика и теория алгоритмов Тема. Словарные множества и словарные функции Пример 1. Пусть A = { a 1 , a 2 , a 3 } и ⏨ a = a1 a2 a1 a3 a2 . Вычислите его номер C( ⏨ a ). Решение: Его номером C( ⏨ a ) будет число 2 + 3 ⋅ 3 1 + 1 ⋅ 3 2 + 2 ⋅ 3 3 + 1 ⋅ 3 4 = 2 + 9 + 9 + 54 + 81 = 155 . Пример 2. 2. Выясните, какое слово в этом алфавите имеет номер 38. Решение: Число n единственным образом раскладывается по степеням числа 3, а именно 38 = 2 + 3 ⋅ 3 + 3 ⋅ 3 2 . Значит 𝛼(38) = a3 a3 a2 . Пример 3. 3. Покажите, что постоянная словарная функция F( ⏨ x 1, … , ⏨ x n) = ⏨ a является примитивно рекурсивной. Решение: Действительно, как в теореме об взаимно однозначном представлении словарной функции и числовой построим для функции F( ⏨ x 1, … , ⏨ x n ) представляющую. Имеем, f(x1 , … , xn ) = C(F(𝛼(x1 ), … 𝛼(xn ))) = C( ⏨ a ) - const , т.е. представляющая числовая функция f(x 1 , … , x n ) является const, которая примитивно рекурсивна. Пример 4. 4. Для любой буквы a i из алфавита A = { a 1 , a 2 , … , a p } определим словарную функцию S i ( ⏨ x) = ⏨ x ai . Покажите, что эта функция примитивно рекурсивна. Решение: Если ⏨ x = aik aik-1 … ai1 ai0 , то C( ⏨ x ) = ik p k +…+ i1 p + i0 . Далее, ⏨ x ai = aik aik-1 … ai1 ai0 ai , и поэтому C( ⏨ x ai ) = ik p k +…+ i1 p + i0 + i = p ik p k +…+ i1 p + i0 + i = pC( ⏨ x ) + i . Имеем равенство, C( ⏨ x ai ) = pC( ⏨ x ) + i , из которого легко получить, что функция Si ( ⏨ x ) = px + i является представляющей для S i ( ⏨ x) = ⏨ x ai . Т.к. функция px + i примитивно рекурсивна, то функция S i ( ⏨ x ) примитивно рекурсивна по определению. Пример 5. 5. Покажите, что F( ⏨ x, ⏨ y) = ⏨ x⏨ y - примитивно рекурсивная функция Решение: Пусть F( ⏨ x, ⏨ y) = ⏨ x⏨ y. Т.к. ⏨ x𝛬 = ⏨ x=⏨ I 11 ( ⏨ x) и ⏨ x⋅⏨ y ai = ( ⏨ x⏨ y ) ⋅ ai = Si ( ⏨ x⏨ y ) , то функция F( ⏨ x, ⏨ y ) получается из примитивно рекурсивных функций G( ⏨ x) = ⏨ x и Hi ( ⏨ x, ⏨ y, ⏨ z ) = Si ( ⏨ z ) , i = 1, … , p . Следовательно, F( ⏨ x, ⏨ y ) - примитивно рекурсивная функция. Пример 6. 6. Пусть ⏨ x ~ обозначает слово, записанное из тех же букв, что и ⏨ x , но в ~ обратном порядке. Покажите, что функция F( ⏨ x) = ⏨ x примитивно рекурсивна. Решение: Т.к. 𝛬 ~ = 𝛬, то в качестве 0-местной функции G (константы) возьмем G = 𝛬, которая примитивно рекурсивна. Далее, F( ⏨ x ai ) = ( ⏨ x ai ) ~ = ai ⏨ x ~ = ai F( ⏨ x). Рассмотрим функции H i ( ⏨ x, ⏨ y ) = ai ⏨ y , которые примитивно рекурсивны как произведения примитивно рекурсивных функций. Тогда F( ⏨ x ai ) = ai F( ⏨ x ) = Hi ( ⏨ x , F( ⏨ x )) . Следовательно, F( ⏨ x ) получается из G = 𝛬 и Hi ( ⏨ x, ⏨ y ) = ai ⏨ y с помощью словарной рекурсии, т.е. F( ⏨ x ) примитивно рекурсивна. Пример 7. Пусть словарные функции G( ⏨ x 1, … , ⏨ x n ) и Hi ( ⏨ x 1, … , ⏨ x n, ⏨ y, ⏨ z ) , i = 1, … p , примитивно рекурсивны, и пусть функция F( ⏨ x 1, … , ⏨ x n, ⏨ y ) такова, что F( ⏨ x 1, … , ⏨ x n , 𝛬) = G( ⏨ x 1, … , ⏨ x n) и F( ⏨ x 1, … , ⏨ x n, ⏨ y ) = Hi ( ⏨ x 1, … , ⏨ x n, ⏨ y , F( ⏨ x 1, … , ⏨ x n, ⏨ y )) , i = 1, … , p . Покажите, что функция F( ⏨ x 1, … , ⏨ x n ) примитивно рекурсивна. Решение: Пусть F 1 ( ⏨ x 1, … , ⏨ x n, ⏨ y ) - функция, полученная из G( ⏨ x 1, … , ⏨ x n ) и Hi ( ⏨ x 1, … , ⏨ x n, ⏨ y, ⏨ z) с помощью словарной рекурсии, которая примитивно рекурсивна. В качестве функции следует взять F( ⏨ x 1, … , ⏨ x n, ⏨ y ) = F1 ⏨ x 1, … , ⏨ x n, ⏨ y~ . Вышесказанное говорит о том, что в определении словарной рекурсии сдвиг на букву a i можно проводить не только вправо F( ⏨ x 1, … , ⏨ x n, ⏨ y ai ) , но и влево F( ⏨ x 1, … , ⏨ x n , ai ⏨ y) . Итоговая функция будет все равно примитивно рекурсивной, если таковыми являются функции G( ⏨ x 1, … , ⏨ x n ) и Hi ( ⏨ x 1, … , ⏨ x n, ⏨ y, ⏨ z) .