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

Важнейшие классы алгоритмов можно описать в терминах теории слов в некотором алфавите. Как уже отмечалось, произвольная конечная совокупность букв называется алфавитом. Последовательность из нескольких букв называется словом. Например, если алфавит состоит из букв A, B, C, то последовательности A, BAA, CA, CC, ACBAB будут словами в этом алфавите. Длиной слова называется число входящих в него букв.

Пусть символы и обозначают слова, записанные в алфавите, не содержащем самих символов и . Тогда обозначается слово, получающееся, если сначала выписать слово , а затем приписать к нему слово . Слово называется композицией (иногда произведением) слов и . Операция композиции слов, очевидно, ассоциативна, но не коммутативна. Слово называется подсловом слова , если можно представить в виде , где – подходящие (возможно пустые) слова. Пусть А = – какой-нибудь конечный набор символов. Обозначим через совокупность всех слов в алфавите А, включая пустое слово . Всевозможные подмножества совокупности , в том числе пустые, будут называться словарными множествами валфавите А.

Для нумерации словарных множеств вводится понятие алфавитных номеров следующим образом. Номер пустого слова полагается равным нулю. Далее в каком-нибудь порядке числами 1, 2, 3, …, p нумеруются символы алфавита. Пусть – символ с номером i. Тогда номером слова называется число .

Рассмотрим пример. Из данного определения номера следует, что каждое слово совокупности будет иметь единственный и отличный от других алфавитный номер. Пусть , а слово , тогда . По своему составу и методу получения это обычное число в троичной системе счисления.

Множество слов M в алфавите А называется примитивно рекурсивным, если соответственно примитивно рекурсивна совокупности алфавитных номеров всех слов из М. Говорят, что в алфавите А задана n -местная словарная функция F, если некоторым n -кам слов из поставлены в соответствие однозначно определенные слова F( ) в А. Числовая n -местная функция f называется функцией, представляющей словарную функцию F в нумерации К, если

для всех натуральных x₁, x₂, …, x_n и, следовательно, или , где К – первоначальная нумерация алфавитных символов. Здесь – алфавитный номер слова , К x_i – слово, имеющее номер x_i в нумерации К.

Рассмотрим пример. Пусть и . Тогда f₁(x)=c(F₁(Kx))=c(Kx∙A), т.к. по определению представляющей функции изменяется только аргумент, а не прочие символы, входящие в ее состав. . Действительно,

– основание системы счисления при нумерации символов алфавита. Тогда f₁(x)=1+px=1+3x – числовая функция, представляющая словарную функцию . Если же

то

.

Тогда f₂(x)=x+3⁵ – числовая функция, представляющая словарную функцию .

Итак, свойство словарных функций быть рекурсивными связано с рекурсивностью совокупности алфавитных номеров всех слов. Ясно, что и определение словарной функции это подтверждает, что свойство быть рекурсивным множеством слов не зависит ни от нумерации К символов алфавита, ни от того, в каком алфавите это множество рассматривается.

По аналоги с основными вычислимыми операциями над числовыми функциями можно определить операции подстановки (суперпозиции), рекурсии и минимизации, производимые над словарными функциями. При помощи этих «словарных операторов» легко и без каких-либо вычислений показывается примитивная рекурсивность всех наиболее употребительных словарных функций. Например, так же вводятся основные элементарные операторы сдвига, аннулирования и проектирования.

Пусть алфавит А состоит из букв a₁, a₂, …, a_p. Словарные функции (m=1, 2, …, p, m n), определенные в алфавите А равенствами , называются простейшими.

Рассмотрим теперь какие-нибудь частичные словарные функции G и H₁, H₂, …, H_p соответственно от n и n+2 переменных, заданных в алфавите А, состоящего из букв a₁, a₂, …, a_p.

Результатом операции словарной примитивной рекурсии над функциями G, H₁, H₂, …, H_p называется (n+1)-местная словарная функция F, которая для любых слов в алфавите А удовлетворяет равенствам

(3.1)

Это определение, если перейти от словарных функций к представляющим их числовым функциям, выглядит так

(3.2)

Представляющая функция f расписывается следующим образом

или

(3.3)

Операция словарной минимизации проводится аналогично, хотя и более сложным способом: вместо одной операции минимизации рассматривается минимизация по каждой букве алфавита a_i.

Теорема 6. Для того, чтобы заданная в алфавите А словарная функция была частично рекурсивной, необходимо и достаточно, чтобы она могла быть получена из простейших словарных функций конечным числом операций суперпозиции, словарной рекурсии и словарной минимизации.

Пример. В алфавите А = рассмотрим словарную функцию и определим рекурсивно второй аргумент . Пусть функция определяется следующим образом:

Пусть, кроме того, и

Тогда

При таком определении может сложиться впечатление, что количество функций H_i недостаточно для построения функции при любом , ведь и неизвестно. Однако, если , то можно найти для всех букв алфавита А, т.к.

.

Затем, взяв , можем определить функцию F для и т.д. для всех слов произвольной длины. Пусть, например, , . Вычислим только . Для этого необходимо определить несколько промежуточных значений этой функции ,

и так далее.

Найдем все представляющие функции. g(x)=c(G( K x)), где К – первоначальная нумерация алфавитных символов А = , p =4; .

Итак, g(x)=2+4x – функция, представляющая словарную функцию .

, h₁(x,y,z)=c(H₁(K x, K y, K z))=

h₂(x,y,z)=c(H₂(K x, K y, K z)=

h₃(x,y,z)=

h₄(x,y,z)=

Перейдем теперь от формул (3.1) к формулам (3.2) для представляющих функций

Вычислим несколько значений представляющих функций:

f(0,0)=g(0)=2+4∙0+2, f(1,0)=6, f(2,0)=10.

и т.д.

Проверим совпадение номеров слов и значений представляющих функций.

Пусть =А, G (A)=AB, c (AB)=2+1∙4=6, c (A)=1, g (1)=2+4∙1=6.

То же наблюдается, например, для функции

и так далее.

Поиск по сайту: