О длине вычислений арифметических программ

( About difficulties of the calculations of the arithmetical proGrams
Preprint, Inst. Appl. Math., the Russian Academy of Science)

Введение. В работе исследуются свойства программ над двоичным арифметическим базисом [1]. Инструментом исследования выступает обобщенный пропозициональный язык, формулы которого строятся над базисом, расширенным за счет введения бесконечных логических операций.

Обобщенные пропозициональные формулы представляют базисные арифметические и логические операторы. Поэтому средств обобщенного пропозиционального языка почти достаточно для представления арифметических программ. После преобразования программы в логическую формулу, в общем случае, получается формула, длина которой пропорциональна вычислению программы над множеством ее входных значений. Если длины вычисления программы не ограничена, то получается формула не ограниченной длины. Поэтому в работе рассматриваются программы для всюду определенных функций, длина вычисления которых ограничена некоторой функцией p(|x|) от длины входа x программы. В этом случае обобщенная функция F(x, y), представляющая функцию y = (x), вычисляемую программой (x), обладает длиной c p(|x|) для некоторой положительной константы c.

Пусть есть энтропия функции , определенная аргументом x. Показывается, что длина формулы F(x, y) ограничена снизу величиной 2^dдля некоторой положительной константы d. Отсюда следует, что имеется хотя бы одно вычисление программы (x), длина которого также не меньше, чем 2^d.

1. Определение программ и их свойства. Пусть X = {x₁, x₂, … } - входной, а Y = {y₁, y₂, …} – рабочий алфавиты. Буквы этих алфавитов назовем соответственно входными и рабочими переменными. Программой p(x₁, x₂, …, x_n, y₁, y₂, …, y_m) в базисе f₁, f₂, …, f_l, P₁, …, P_h , где f₁, f₂, …, f_l - общерекурсивные функции, P₁, …, P_h – рекурсивные предикаты, называется ориентированный граф, вершинами которого являются выражения следующих двух типов:

1)                      арифметические операторы y_j Ü f_i(y₁, y₂, …, y_m), 1 £ i £ l;

2)                      логические операторы P_i(z₁, …, z_q), где z₁, …, z_q – входные и рабочие переменные, 1 £ i £ h.

При этом каждая арифметическая вершина имеет ровно одного последователя, логическая – двух (один из которых называется 0-последователем, другой 1-последователем), а заключительная  вершина последователей не имеет. Заключительная вершина помечена в точности одной рабочей переменной, которая называется выходной. Кроме того, одна из вершин является начальной вершиной программы.

Полагаем, что рассматривается программа p(x₁, x₂, …, x_n, y₁, y₂, …, y_m) с фиксированными наборами входных и рабочих переменных, а также с фиксированной выходной переменной.

Полным состоянием программы p(x₁, x₂, …, x_n, y₁, y₂, …, y_m) называется пара (x, v), где v – вершина, а x Î N^n+m. Если вершина v – заключительная, то полное состояние (x, v) называется заключительным. Если x = a₁, a₂, …, a_n, b₁, b₂, …, b_m, то числа a₁, a₂, …, a_n, b₁, b₂, …, b_m называются значениями переменных соответственно x₁, x₂, …, x_n, y₁, y₂, …, y_m в состоянии (x, v).

На множестве полных состояний программы p определяется отношение ®: пусть x₁ = a₁, a₂, …, a_n, b¢₁, b¢₂, …, b¢_m, x₂ = a₁, a, …, a_n, b²₁, b²₂, …, b²_m, тогда  (x₁, v₁) ® (x₂, v₂)  Û выполняется одно из следующих условий.

1.                      Если v₁ – арифметическая вершина y_j Ü f(y_j1, y_j2, …, y_jr), то b²_j =  f(c₁, c₂, …, c_r), где c₁, c₂, …, c_r – значения соответствующих переменных, и v₂ является последователем v₁.

2.                      Если v₁ – логическая вершина P(x_j1, x_j2, …, x_jh, y_j1, y_j2, …, y_jl), то x₁ = x₂ и v₂ является P(a_j1, a_j2, …, a_jh, b_j1, b_j2, …, b_jl)-последователем вершины v₁.

Вычислением программы p для значений a₁, a₂, …, a_n входных переменных называется такая последовательность X полных состояний (x₁, v₁), (x₂, v₂), …., (x_l, v_l), … , что x₁ = a₁, a₂, …, a_n, 0, …, 0; вершина v₁ – начальная; (x_i, v_i) ® (x_i+1, v_i+1), i = 1, 2, … . Говорим, что путь t = v₁, v₂, …., v_l, … соответствует вычислению X. Вычисление называется терминальным, если оно конечно и последнее его состояние – заключительное. Путь, соответствующий терминальному вычислению, назовем терминальным. Путь из начальной вершины назовем начальным путем, а начальный путь, кончающийся заключительной вершиной, - полным.

Пусть t =  v₁, v₂, …., v_l, … ‑ начальный путь в программе p. Для каждой вершины этого пути определим значение рабочих переменных y₁, y₂, …, y_m следующим образом.

1.                      В начальной вершине все их значения нулевые.

2.                      Если в арифметической вершине y_j Ü f(y_j1, y_j2, …, y_jr) переменные y₁, y₂, …, y_m имеют значения b₁, b₂, …, b_m, то в ее последователе переменная y_j имеет значение f(b_j1, b_j2, …, b_jr), а остальные переменные не меняют своих значений.

3.                      В последователях логической вершины все переменные сохраняют свои значения.

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

Функцией, вычисляемой программой p, называется частичная функция f_p такая, что f_p(a₁, a₂, …, a_n) = b Û существует терминальное вычисление, начинающееся состоянием (a₁, a₂, …, a_n, 0, 0, …, 0; v₁) и для которого b является значением выходной переменной в заключительном состоянии.

Две программы эквивалентны, если они вычисляют одну функцию.

Вершина v программы называется фиктивной, если ни один полный путь, соответствующий какому-либо вычислению, не проходит через нее.

Справедливо утверждение.

Лемма 1. Любая программа эквивалентна программе, в которой нет фиктивных вершин.

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

Пусть путь t = v₁, v₂, …, v_l, v, l > 0, оканчивается фиктивной вершиной v, и все вершины v₁, v₂, …, v_l  арифметические. В этом случае вершины v₁, v₂, …, v_l так же фиктивные, так как если хотя бы одно вычисление содержит вершину v_i, i = 1, 2, …, l, то это вычисление содержит и вершину v. Поэтому, исключив из программы вершины v₁, v₂, …, v_l и направив все дуги, ведущие в эти вершины, в вершину v, получим программу эквивалентную исходной.

Пусть теперь путь t = v₁, v оканчивается фиктивной вершиной v, вершина v₁ логическая и ее s-выход (s Î {0,1}) ведет в фиктивную вершину v. Выбросим вершину v₁, а ведущие в нее дуги направим в ее (1-s)-последователя. Получим опять программу эквивалентную исходной.

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

Лемма доказана.

Полагаем, что рассматриваемые далее программы не содержат фиктивных вершин.

Будем рассматривать программы над двоичными числами над полным базисом s(x), 0(x) и x = y. При этом полагаем, что в арифметических операторах y Ü f(х), переменные y и х совпадают.

Нам потребуется следующее представление двоичных чисел. Каждое двоичное число представляется бесконечной бинарной последовательностью, младшие разряды числа расположены слева, а справа располагается бесконечная последовательность из нулей.

Логическую вершину вида x = x назовем несущественной. Легко доказывается

Лемма 2. Любая программа эквивалентна программе, в которой нет несущественных вершин.

Поэтому полагаем, что рассматриваемые далее программы не содержат несущественных вершин.

Для удобства пусть начало всякой программы представляет собой m операторов 0(y₁), …, 0(y_m). Назовем эти операторы установочными.

Каждый путь t = v₁, v₂, …., v_l программы следующим образом определяет множество функций f_ti: f_ti(a₁, a₂, …, a_n, b₁, b₂, …, b_m) = b¢_i Û существует вычисление, соответствующее пути t, начинающееся состоянием (a₁, a₂, …, a_n, b₁, b₂, …, b_m; v₁), и оканчивающееся состоянием (a₁, a₂, …, a_n, b¢₁, b¢₂, …, b¢_m; v_l), i = 1, 2, …, m. В свою очередь, каждый полный путь t определяет единственную функцию f_t: f_t(a₁, a₂, …, a_n) = b Û существует терминальное вычисление, соответствующее пути t и начинающееся состоянием (a₁, a₂, …, a_n, 0, 0, …, 0; v₁), для которого b является значением выходной переменной в заключительном состоянии. Тогда функция, вычисляемая программой, представляет собой объединение функций, определяемых всеми ее полными путями.

Пусть t = v₁, v₂, …., v_l, … ‑ путь в программе p. Заменим каждый предикат P(z₁, z₂, …, z_r) в нем предикатом P^s(z₁, z₂, …, z_r), где s Î {0, 1} таково, что следующая в t за P(z₁, z₂, …, z_r) вершина является его s-последователем. Полученную таким образом последовательность назовем размеченным путем и обозначим t.

Программа p может рассматриваться как диаграмма конечного автомата, состояниями которого являются логические и заключительная вершины, а входной алфавит образован из следующих «букв». Если из логической вершины P в логическую вершину P₁ ведет путь P, v₁, …, v_l, P₁, где v₁ является s-последователем вершины P, v₁, …, v_l – арифметические вершины и l ³ 0, то переход из состояния P в состояние P₁ происходит под воздействием автоматной «буквы» P^s, v₁, …, v_l. Событие, представимое таким автоматом, состоит из всех полных размеченных путей программы. Представим регулярное выражение R, задающее множество всех полных путей, в виде суммы R_p = R₁ Ú R₂ Ú …Ú R_r членов, не содержащих операции суммирования.

Покажем, как всякое регулярное подвыражение R выражения R_i определяет совокупность функций, i = 1, 2, …, r.

1.                      Пусть R не содержит оператора ^*. По построению оно задает единственный размеченный путь t, который определяет m частичных функций f_ti(x₁, x₂, …, x_n, y₁, y₂, …, y_m), i = 1, 2, …, m, как описано выше. Будем говорить, что выражение R определяет эти функции. Если t есть полный путь, то определяемая им единственная функция f_t(x₁, x₂, …, x_n) описывает зависимость выходной переменной программы от входных.

2.                      Пусть выражение R = А^*, регулярное выражение А задает совокупность {t} размеченных путей и {t}^* есть совокупность всех размеченных путей, полученных всеми возможными конкатенациями путей из {t}. Каждый из этих путей определяет m частичных функций f_ti(x₁, x₂, …, x_n, y₁, y₂, …, y_m), i = 1, 2, …, m, как описано выше. Будем полагать, что выражением R определяет совокупность всех этих функций.

3.                      Пусть выражение R = АВ, регулярное выражение А определят совокупность F функций, а выражение В – совокупность G. Тогда выражение R определяет совокупность всех возможных суперпозиций вида Gf, где G Î G и на места рабочих переменных функции G подставляются функции из F, задающие значения одноименных рабочих переменных и определяемые выражением A.

Из этого построения вытекает

Лемма 3. Каждое регулярное выражение R_i, i = 1, 2, …, r, определяет функцию f_i, описывающую зависимость выходной переменной от входных, а регулярное выражение R_p определяет функцию f_p = È_i=1,r f_i, вычисляемую программой p.

Доказательство. Каждое регулярное выражение R_i, i = 1, 2, …, r, представляет некоторое множество полных путей программы. Последние, в свою очередь определяют совокупность функций, задающих выходное  значение в зависимости от входных. Их объединение есть функция f_i. Все регулярное выражение R_p представляет множество всех полных путей программы. Поэтому объединение È_i=1,r f_i есть функция, вычисляемая программой.

Лемма доказана.

Справедлива

Лемма 4. Всякое подвыражение R_i, i = 1, 2, …, r регулярного выражения R_p не может оканчиваться выражением вида A^*.

Доказательство вытекает из того, что событие, представимое выражением R_p, состоит из всех полных размеченных путей программы p. Если выражение R_i, i Î{1, 2, …, r} оканчивается подвыражением A^*, то R_i не определяет терминального пути. Это противоречит способу построения регулярного выражения R_p.

Лемма доказана.

Следствие. Всякое подвыражение R_i, i = 1,2, …, r регулярного выражения R_p оканчиваться автоматной буквой вида P^s, v₁, …, v_l , l ³ 0, sÎ {0, 1}.

Лемма 5. Пусть А^* есть регулярное подвыражение выражения R_p, P₁^s1 - предикат, которым начинается первая автоматная буква выражения А, и P_q^sq, v₁, …, v_l - последняя автоматная буква выражения А. Тогда, если l > 0, то в программе вершина v_l соединена дугой с вершиной P₁, если l = 0, то s_q -дуга, выходящая из вершины P_q, ведет в вершину P₁.

Доказательство вытекает из способа построения регулярного выражения R_p.

Лемма 6. Пусть А^*В есть собственное регулярное подвыражение выражения R_p и P₁^s1 - предикат, которым начинается первая автоматная буква выражения А. Тогда первая автоматная буква выражения В начинается с предиката P₁^1-s1.

Доказательство. Рассмотрим вначале простейший случай, когда выражение А не содержит оператора ^*. Тогда оно представляет собой последовательность P₁^s1 А₁ P₂^s2 А₂… P_q^sq А_q автоматных букв. Выражение P₁^s1 А₁ P₂^s2 А₂… P_q^sq А_q определяет размеченный путь t, который проходит через логические вершины P₁, P₂,… , P_q и содержит дуги, ведущие соответственно в их s₁, s₂, …, s_q-последователи. 

Так как выражение A^* содержит оператор ^*, то оно представляет совокупность размеченных путей, которые получаются n-кратным прохождением пути t, при всяком n ³ 0. Поэтому t есть цикл, начинающийся и заканчивающийся вершиной Р₁, которая есть s_q-последователь вершины P_q.

Покажем, что непосредственно после выражения A^* следует буква входного алфавита, начинающаяся с предиката P₁^1-s₁. Действительно, после последнего прохождения пути t следующий путь может начинаться только в логической вершине Р₁  и вести в ее (1-s₁)-последователя. Поэтому непосредственно правее A^* должно располагаться регулярное выражение, первая автоматная буква которого начинается с предиката P₁^1-s1.

Пусть теперь выражение А есть последовательность регулярных выражений: А₁ А₂… А_q, причем каждое из них может содержать оператор ^*. Допустим далее, что выражение А₁ начинается с автоматной буквы, имеющей начальным предикат P₁^s1. В этом случае выражение А₁ А₂… А_q определяет совокупность {t} размеченных путей, которые проходят через логическую вершину P₁ и содержит дугу, ведущую в ее s₁-последователя.

Выражение A^* задает совокупность размеченных путей, которые получаются n-кратным прохождением путей совокупность {t}, при всяком n ³ 0. Поэтому каждый путь совокупности {t} есть цикл, который начинается и заканчивается вершиной Р₁. Тем самым выражение A^* представляет совокупность циклических вычислений программы, и выход из этих циклов возможен только по (1-s₁)-дуге вершины Р₁. Но это возможно лишь в случае, когда непосредственно после выражения A^* располагается автоматная буква, начинающаяся с предиката P₁^1-s1.

Рассмотрены все случаи. Лемма доказана.

Следствие. Программа, которая реализует всюду определенную функцию, определяет регулярное выражение, не содержащее подвыражений вида ((Р^s А)* Р^1-s В)*. (В данном случае выражение (Р^s А)* Р^1-s В следует понимать так: заключенное в скобках регулярное выражение Р^s А  имеет первой автоматную букву, которая начинается с предиката Р^s, а непосредственно после выражения (Р^s А)* следует выражение, первая автоматная буква которого начинается с предиката Р^1-s.)

Доказательство. Действительно, выражение ((Р^s А)* Р^1-s В)* определяет бесконечный цикл, проходящий через логическую вершину Р. Если путь начинается в Р и проходит через ее s-последователь, то он включает размеченный путь, определяемый выражением Р^s А и возвращается вновь в логическую вершину Р. Если же путь начинается в Р и проходит через ее (1-s)-последователь, то он включает размеченный путь, определяемый выражением Р^1-s В и возвращается вновь в логическую вершину Р. Противоречие с тем, что программа реализует всюду определенную функцию.

Следствие доказано.

Исходя из этого Следствия и того, что мы рассматриваем программы без фиктивных вершин, мы ограничимся лишь такими программами, для которых регулярные выражения не содержат подвыражений вида ((Р^s А)* Р^1-s В)*.

В последующем будем полагать, что число шагов, осуществляемое программой p при любом вычислении, ограничено некоторой конечной величиной, определяемой значениями входных переменных. В частности ограничимся рассмотрением вычислений программы над некоторым множеством входных значений, длина которых ограничена конечным числом p.

Исходя из этого, по выражению R_p построим так называемое параметрическое выражение R_p¢. Для этого представим каждое регулярное выражение R_i в параметрическом виде R¢_i так, что при указанном ограничении на вычисления программы параметрическое выражение R_p¢ задает то же множество полных путей, что и исходное R_p. Выражение R¢_i строим индукцией по выражению R_i. Для этого введем понятие текущего параметра, которое определяется следующим образом.

0.                      Полагаем, что текущий параметр каждого выражения R_i равен p, i = 1, 2, …, m. После этого просматриваем каждое выражение R_i слева направо, анализируя его подвыражения и определяя текущий параметр для каждого из них.

1.                      Если рассматриваемый оператор арифметический a_i или логический P_j, то записываем его в виде соответственно (a_i)¹или (P_j)¹, одновременно уменьшая текущий параметр на 1.

2.                      Если рассматриваемый оператор A^*, то ставим ему в соответствие выражение  (A)^r, где r –текущий параметр. При этом текущий параметр не меняется.

3.                      После очередного просмотра выражений R_i, i = 1, 2, …, m, мы переходим к рассмотрению выражений вида (A)^r, где A - его собственное регулярное подвыражение, для которого текущим параметром является r.

4.                      Разбор выражения R_i, i = 1, 2, …, m, происходит до тех пор, пока не будут просмотрены все арифметические и логические операторы.

Сформулируем некоторые свойства параметрических выражений. Справедливы следующие леммы.

Лемма 7. Параметрическое выражение R_p¢ определяет множество всех полных путей программы p при введенном  ограничении p на число шагов вычисления.

Доказательство. Число вхождений каждого слова в событие, представимое регулярным выражением R_p¢, совпадает с числом вхождений каждого слова в событие, представимое исходным регулярным выражением. Это вытекает из того, что мы рассматриваем множество входов программы, для которых число шагов программы ограничено значением p.

Лемма доказана.

Тем самым, параметрическое выражение R_p¢ для рассматриваемого множества входов определяет ту же функцию, что и регулярное выражение R_p.

Теперь из леммы 5 следует

Лемма 8. Если в регулярном выражении R_p встречается выражение (A B* C)*, а в параметрическом R_p¢ ему  соответствует выражение (A B^m₁ C) ^m₂, то m₁ < m₂.

3. Представление программ обобщенными формулами.  Расширим булевский язык над обычным базисом {Ú, Ù, Ø} путем введения обобщений дизъюнкции и конъюнкции для не более, чем счетного множества аргументов. Для обобщенных дизъюнкции и конъюнкции будем использовать выражения соответственно È_{i=k, h} и Ç_{i=k, h}, где i называется индексом этой связки, k- нижней границей, а h – верхней. k и h – это либо константы, либо символ бесконечности - , либо функции, зависящие от других индексов.

Для дальнейшего нам потребуется следующее соглашение. Всякой двоичной переменной y программы будем сопоставлять счетную последовательность y₀y₁…y_i… логических переменных. Когда y принимает двоичное значение, то i-ая логическая переменная означивается i-м разрядом этого числа, i = 0, 1, … . Напомним, что мы изображаем двоичные числа, младшие разряды которых располагаются левее. Таким образом, логические переменные y₀y₁…y_i… будут имеет слева некоторый конечный отрезок переменных, означенных в соответствии с двоичным числом, справа от которого будет располагать бесконечная последовательность переменных, означенных нулями. 

Будем говорить, что логическая формула F(x, y), где x = x₀x₁ … x_i…, y = y₀y₁ … y_i…  суть последовательности логических переменных, представляет двоичную функцию y = (x), если при означивании переменных x бинарным вектором  таким, что   Def , формула F(,) истинна тогда и только тогда, когда () = .

Пример 1. Обозначим x, y, u наборы двоичных переменных соответственно: x₀, x₁, …, x_n,… ; y₀, y₁, …, y_n,… и u₀, u₁, …, u_n,… . Нетрудно увидеть, что формула

S(x, y): (y₀ `x₀) Ù Ç_{i=1, w} (y_i  x_i + Ç_{j=0, i-1} x_i)

представляет функцию s(x) прибавления единицы двоичной арифметики. Подформула Ç_{j=0, i-1} x_i  представляет перенос в i-ый разряд, он равен 1 тогда и только тогда, когда все разряды до (i - 1)-го включительно равны 1.

В точности так же и формула

S(x, u, y): u₀  x₀ Ù Ç_i=0,w (u_i+1  u_i Ù x_i) Ù (y₀ `x₀) Ù Ç_i=1,w (y_i  x_i + u_i)

представляет функцию прибавления единицы. Легко увидеть, что новая переменная u_i определяет перенос в i-ый разряд, который вычисляется после прибавления 1 к вектору с разрядами от нулевого до (i – 1)-го включительно. Перенос в нулевой разряд совпадает с нулевым разрядом самого числа.

Базисная функция 0(x) представима формулой Ç_i=0,w`x_i .

Предикат x = y представим формулой E(x, y) = Ç_i=0,w (x_i  y_i).

Предикат x  y представим формулой (x, y) = È_i=0,w (x_i  y_i).

Теорема 9. Пусть формулы F(x, y) и G(y, z) представляют функции соответственно y = f(x) и z = G(y) двоичной арифметики.  Тогда конъюнкция F(x, y) Ù G(y, z) представляет суперпозицию z = f(G(y)).

Доказательство. Пусть бинарные векторы s_x, s_y, s_z предствляют двоичные числа, такие, что s_y = f(s_x) и s_z = G(s_y). Для тех же бинарных векторов логические функции F(s_x, s_y) и G(s_y, s_z) истинны. Но тогда истинна и конъюнкция F(s_x, s_y) Ù G(s_y, s_z).

В обратную сторону. Пусть для бинарных векторов s_x, s_z предствляющих двоичные числа, имеет место равенство s_z = G(f(s_x)). Из того, что f  есть функция двоичной арифметики следует, что существует единственный бинарный вектор s_y, представляющий двоичное число, для которого имеет место равенство s_y = f(s_x). Но тогда конъюнкция F(s_x, s_y) Ù G(s_y, s_z) истинна в силу того, что формулы F(x, y) и G(y, z) представляют функции соответственно y = f(x) и z = G(y).

Разобраны все случаи. Теорема доказана.

Пример 2. Используя последнюю теорему о суперпозиции функций, легко показать, что при фиксированном целом l > 0 функция y = x + l представима обобщенной формулой (обозначим ее S^l(x, y)). Приведем ряд формул, представляющих арифметические функции прибавления некоторых констант.

Не всякая двоичная арифметическая функция представима обобщенной формулой. В частности, не представимо умножение.

Базисные операторы программ представимы обобщенными формулами. Поэтому возникает вопрос о представлении функции, вычисляемой программой p, обобщенной логической формулой. Исходя из этого, построим по параметрическому выражению R_p¢ обобщенную формулу, определив вначале соответствующую формулу для его каждого дизъюнктивного члена, а затем дизъюнктивно объединив их. Поэтому наши построения будут касаться каждого параметрического выражения R¢_i, i = 1, 2, …, m.

Во-первых, несколько преобразуем каждое выражение R¢_i, сделав его более удобным для последующего построения. Если в выражении R¢_i оператор s(y) встречается подряд l раз, где у – рабочая переменная, то заменим его на оператор s^l(y). Аналогично, если в выражении R¢_i оператор 0(y) встречается подряд l раз, где у – рабочая переменная, то заменим эту последовательность одним оператором 0(y).

Дальнейшее построение логической формулы заключается в замене арифметических и логических операторов, из которых состоят автоматные буквы регулярного выражения, на представляющие их обобщенные формулы. В качестве переменных используемых при этом логических формул будем использовать так называемые метапеременные. С этой целью вначале заменим все рабочие переменные y₁, y₂, …, y_m в параметрическом выражении на метапеременные соответственно a₁, a₂, …, a_m. Считаем, что эти метапеременные порождены рабочими переменными и поэтому назовем их рабочими. Входные переменные мы не заменяем, для единообразия считая их также метапеременными, которые назовем входными. Если необходимо подчеркнуть, что метапеременная есть входная переменная, это будет оговорено специально.

Отметим следующее.

Регулярное выражение R_p включает в качестве компонентов арифметические и логические операторы, содержащие переменные, областью определения которых являются не отрицательные целые числа.

В точности так же, как мы представляем двоичные переменные счетными последовательностями булевских переменных, считаем, что каждая метапеременная a представима в виде последовательности a₁a₂ … a_i … логических метапеременных.  

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

Введем следующие соглашения.

1. Пусть a есть метапеременная и ее булевское представление выглядит так: a₀a₁a₂ … a_m … . Тогда 0(a)обозначим обобщенную формулу Ç_i=0,w`a<sub>i</sub>. Очевидно, что формула Ç<sub>i=0,w</sub>`a_i представляет арифметический оператор 0(a). В последующем, если это необходимо, будем оговаривать особо, когда 0(a) понимается как арифметический оператор, а когда как обобщенная формула.

2. Если a = a₀a₁a₂ … a_i … ., b = b₀b₁b₂ … b_i … . - это метапеременные, то обозначим E(a, b) бесконечную конъюнкцию Ç_{i=0, w} a_i  b_i, а (a, b) - дизъюнкцию È_{i=0, w} (a_i  b_i). 

Просматриваем каждое параметрическое выражение R¢_i, i = 1, 2, …, m слева направо. При первом просмотре мы игнорируем параметры, которыми был заменен оператор ^*. В зависимости от вида очередного подвыражения осуществляем следующие действия.

Пусть таким выражением является автоматная буква P^s, v₁, …, v_l. В этом случае анализируем по очереди вид логического и арифметических операторов и ставим им в соответствие определенные логические формулы.

1. Предикат P^s(a, b) заменяем формулой Е^s(a, b).

2. Оператор s^l(a) заменяем формулой S^l(a, b), где b - это новая рабочая метапеременная, которая не использовалась ранее. Затем везде в этом выражении правее оператора s^l(a) заменяем все вхождения метапеременной a на b. Назовем a – входной метапеременной формулы S^l(a, b), а b – выходной. При этом b назовем последователем a, а a - предшественником b.

3. Всякий установочный оператор 0(a) заменяем формулой 0(a). Если 0(a) не установочный арифметический оператор, то заменяем его на формулу 0(b), где b - это новая рабочая метапеременная, которая не использовалась ранее. Затем везде правее этого оператора заменяем все вхождения метапеременной a на b.

Замечание. Арифметический оператор 0(y) в программе устанавливает нулевое значение рабочей переменной y не зависимо от ее предыдущего значения. Прежнее значение этой переменной как бы забывается и его восстановление невозможно. Поэтому не установочный оператор 0(a) заменяем на формулу 0(b), где b - новая рабочая метапеременная. Последняя также считается порожденной той же рабочей переменной, которая порождала метапеременную a. При этом b назовем последователем a, которую в свою очередь назовем предшественником b.

Полагаем, что оба отношения «быть последователем» и «быть предшественником», определенные в двух последних пунктах, – транзитивные.

Из определения отношения «быть последователем» вытекает, что если метапеременная b есть последователь a, то в выражении R_p¢ они порождены одной рабочей переменной. То же относится к отношению «быть предшественником».

Введем следующее определение. Пусть в результирующем выражении R¢, полученном из исходного, метапеременная b есть последователь метапеременной a. Назовем b - тупиковым последователем метапеременной a в R¢, если b не имеет в нем последователя. Аналогично, a назовем тупиковым предшественником метапеременной b в R¢, если a не имеет предшественника в R¢. Напомним, что R¢ есть подобие регулярного выражения, в котором арифметические и логические операторы заменены представляющими их обобщенными формулами.

В результате описанных преобразований параметрическое выражение R_p¢ преобразуется в конструкцию R_p², которая вместо арифметических и логических операторов содержит представляющие их логические формулы, а вместо входных и рабочих переменных – соответственно рабочие и входные метапеременные. Каждая формула S^l обладает входными и выходными метапеременными, между которыми установлены отношения последовательности и предшествования. При этом входная метапеременная формулы S^l не встречается правее нее. Несколько раз могут встретиться лишь входные переменные программы и метапеременные, которые встречаются в формулах, представляющих логические операторы программы.

Пусть P^s, v₁, …, v_l – это автоматная буква рассматриваемого параметрического выражения, которая задает размеченный путь t. Этот путь, в свою очередь, определяет совокупность f_ti , i = 1, 2, …, m  частичных функций, каждая из которых определяет значение одной рабочей переменной в зависимости от значений переменных перед выполнением логического оператора Р. Пусть рабочие переменные у₁, у₂, …, у_m этой автоматной буквы порождают некоторое множество метапеременных, из которого выделим тупиковые предшественники a₁, a₂, …, a_m и соответственно тупиковые последователи b₁, b₂, …, b_m относительно буквы P^s, v₁, …, v_l.

В соответствии с первым этапом нашего построения в результирующем выражении R_p²  отдельным компонентам буквы P^s, v₁, …, v_l соответствуют представляющие их формулы E^s(a, b), W₁, …, W_l. Поставим в соответствие автоматной букве P^s, v₁, …, v_l формулу

F = E^s(a,b) Ù W₁ Ù …Ù W_l.

Справедливо утверждение.

Лемма 10. Формула F представляет все функции, определяемые автоматной буквой P^s, v₁, …, v_l с точностью до переименования рабочих переменных порожденными ими метапеременными.

Доказательство. Напомним, что если логическая функция F(x, y) представляет вычисляемую функцию y = f(x), функция G(z, w) - функцию w = G(z), то суперпозиция функций y = f(G(x)) представляется конъюнкций F(w, y) Ù G(х, w).

Если при выполнении  программы p предикат P^s принимает значение истина, то значения рабочих переменных определяются этим путем следующим образом. Если рабочая переменная y встречается в операторах v₁, …, v_l и не обнуляется, то ее новое значение есть сумма ее входного значения и некоторой константы, определяемой присутствующими в этом пути операторами прибавления единицы. Если же эта рабочая переменная y обнуляется, то ее значение равно некоторой константе, которая совпадает с числом единиц, прибавляемых к этой переменной после последнего ее обнуления в рассматриваемом пути. Но в точности так же вычисляется значение соответствующей тупиковой метапеременной b функцией, представимой конъюнкцией

E^s(a, b)  W₁  … W_l.

Лемма доказана.

Таким образом, для автоматной буквы P^s, v₁, …, v_l , которая входит в исследуемое параметрическое выражение, верны следующие утверждения:

буква P^s, v₁, …, v_l определяет совокупность f_ti, i = 1, 2, …, m,  частичных функций, задающих значения рабочих переменных;

все эти функции представляются формулой F при введенном соответствии рабочих переменных и метапеременных.

Для подслова a₁a₂…a_q рассматриваемого параметрического выражения, которое состоит из нескольких автоматных букв, имеет место

Лемма 11. Пусть F_a1, F_a2, …, F_aq – формулы, поставленные в соответствие автоматным буквам соответственно a₁, a₂, …, a_q. Тогда формула F = F_a1 Ù F_a2 Ù …Ù F_aq представляет все частичные функции, которые определяются регулярным выражением a₁a₂…a_q.

Доказательство вытекает из того, что тупиковые выходные метапеременные каждого выражения, определяемого буквой a_i, i = 1, 2, …, q -1, совпадает с соответствующими тупиковыми входными метапеременными выражения, определяемого буквой a_i+1. Тем самым, если буква a_i определяет совокупность из m частичных функций (по числу рабочих переменных), то слово a₁, a₂, …, a_q определяет частичные функции, полученные определенной суперпозицией из указанных, а формула F представляет все эти функции.

Лемма доказана.

Дальнейшее преобразование параметрического выражения в логическую формулу носит индуктивный характер. Из описанных ранее свойств параметрического выражения R_p¢ вытекает, что каждое его подвыражение вида В^h можно представить следующим образом: (Р^sА)^h, где Р есть логический оператор программы и A – оставшаяся часть выражения B. В простейшем случае выражение А является последовательностью арифметических операторов.

Базис индукции. Пусть выражение В не имеет вложенных параметрических выражений, построенных по регулярным выражениям вида Q^*. Поэтому оно определяет единственный размеченный путь t, начинающийся в логической вершине Р и включающий ее s–последователя. Будем полагать, что выражение Р^sА уже представляет формула F.

Пусть a и b– это последовательности соответственно тупиковых входных и выходных метапеременных выражения В. Поэтому формулу F обозначим следующим образом: Е^s(a) Ù F(a, b). Последовательность a входных метапеременных может состоять из входных переменных программы и метапеременных, которые порождены рабочими переменными. Следовательно, длина последовательности a не превосходит n + m. Представим a в виде объединения двух последовательностей a^w и a^I. Здесь a^w есть метапеременные, полученные по рабочим переменным, а a^I - входные переменные.

Последовательность b выходных метапеременных может состоять только из метапеременных, которыми были заменены рабочие переменные, и ее размерность не превосходит m. Для простоты полагаем, что последовательность a имеет n + m метапеременных, включает входные переменные и метапеременные, полученные по рабочим переменным, а последовательность b состоит только из m метапеременных, полученных по рабочим переменным. Тогда отношения последовательности и предшествования для этих последовательностях устанавливаются просто. Полагаем, что a^w = a₁, a₂, …, a_m и b = b₁, b₂, …, b_m.

Образуем h различных множеств метапеременных: b¹, b², …, b^h, каждое мощности m и между каждой парой множеств b, b¹, …, b^h определено изоморфное соответствие j. Назовем соответствующими следующие метапеременные: в множествах a и b – это метапеременные между которыми  установлено отношение быть последователем, а между каждой парой множеств из b, b¹, …, b^h соответствие определяется отображением j. Таким образом, для каждой входной метапеременной из множества a в каждом множестве из b, b¹, …, b^h можно выделить единственную метапеременную, которую также назовем выходной. И таких метапеременных в каждом из множеств b, b¹, …, b^h в точности m. Поэтому bⁱ = b ⁱ₁, b ⁱ₂, …, b ⁱ_m.

Итак, для каждой входной метапеременной из a, полученной по рабочей переменной, в любом множестве bⁱ всегда имеется в точности одна соответствующая выходная метапеременная. Обозначим a¹, a², …, a^h множества метапеременных, которые получены добавлением к входным переменным множеств соответственно b¹, b², …, b^h. Полагаем, что множества a и a¹, a², …, a^h упорядочены так, что сохраняется одинаковый порядок на соответствующих метапеременных.

Введем такое соглашение. Пусть выражение a^w = b обозначает m конъюнкций Ç_{i=1, m} E(a_i^w, b_i), где E(a_i^w, b_i) – обобщенная формула, представляющая равенство a_i^w = b_i метапеременных. Аналогично b^j = b обозначает конъюнкцию Ç_{i=1, m} E(b_i ^j, b_i), где E(b_i ^j, b_i) обобщенная формула, представляющая равенство b_i ^j = b_i , i = 1, 2, …, m.

Теперь выражению В^h ставим в соответствие логическую формулу

F^h = Е^1-s (a)(a^w = b) Ú Е^s(a) F(a, b¹) Е^1-s(a¹) (b¹ = b) Ú

Е^s(a)  F(a, b¹) Е^s(a¹) F(a¹, b²) Е^1-s(a²) (b² = b) Ú

                                    . . .

Е^s(a)F(a, b¹) Е^s(a¹) F(a¹, b²) …Е^s(a^h-1) F(a^h-1, b^h) Е^1-s(a^h)(b^h = b).

В этой формуле Е^s(aⁱ) есть формула, представляющая предикат Р^s(aⁱ), в которой вместо метапеременных из a подставлены соответствующие метапеременные из aⁱ, i = 1, 2, …, h.

Покажем, что верна

Лемма 12. Формула F^h представляет все функции, определяемые параметрическим подвыражением В^h.

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

1.                      Конъюнкция Е^1-s(a) Ù (a = b) истинна тогда и только тогда, когда формула Е^1-s(a) истинна и выходные переменные набора b совпадают с соответствующими входными набора a. Среди функций, определяемых выражением В^h, имеются функции, которые порождены нулевым прохождением пути t, что происходит, когда значения аргументов предиката Р^s превращают его в ложь. В этом случае рабочие переменные после перехода в (1-s)-последователя вершины Р не меняются. Следовательно такой переход по дуге из вершины Р в 1 - s последователя соответствует тождественной функции. Но именно такую функцию представляет рассматриваемая конъюнкция.

2.                      Рассмотрим теперь i-кратное прохождение (0 < i £ h) размеченного пути t, завершающееся прохождением дуги d, ведущей в (1-s)-последователя вершины Р. Такой путь порождает частичные функции, которые суть суперпозиции глубины i функций, порождаемых самим путем t. При этом последний переход по дуге, ведущее в (1-s)-последователя вершины Р не меняет значений рабочих переменных, которые были получены после последнего прохождения вершины Р. 

Отсюда видно, что конъюнкция 

Е^s(a) Ù F(a, b¹) Ù Е^s(a¹) Ù F(a¹, b²) Ù … Ù Е^s(a^{i -1}) Ù F(a^{i -1}, bⁱ) Ù Е^1-s(aⁱ) (bⁱ = b)

представляет все функции, определяемые i-кратным прохождением размеченного пути t, завершающееся прохождением дуги d, ведущей в (1-s)-последователя вершины Р. Действительно, всякая формула

Е^s(a) Ù F(a, b¹) Ù Е^s(a¹) Ù F(a¹, b²) Ù … Ù Е^s(a^j) Ù F(a^j, b^j+1)

представляет все функции, определяемые j-кратным прохождением пути t, в результате заданным способом совмещения входных и выходных метапеременных. После j-кратного прохождения пути t выход из цикла происходит лишь в том случае, когда предикат Р^1-s истинен. Этот предикат представляется  формулой Е^1-s(aⁱ). Поэтому выходные метапеременные из b принимают те значения, которые принимают соответствующие метапеременные набора bⁱ. 

Вся построенная дизъюнкция представляет объединение функций, которые представляются каждым из ее членов. Отсюда вытекает искомое утверждение.

Индуктивные рассуждения. Если параметрическое выражение А = А₁А₂, и для выражений А₁ и А₂ построены логические функции соответственно F₁ и F₂, представляющие все функции порождаемые выражениями А₁ и А₂, то конъюнкция F₁ Ù F₂ представляет все функции, порождаемые выражением А. Это вытекает из того, что конструируемая формула имеет в заключительных частях своих конъюнкций метапеременные, совпадающие с тупиковыми выходными метапеременными выражений, по которым они строятся. Для выражения B = A₁ A₂ … A_n рассуждения аналогичны.

Если выражение В имеет вложенные выражения, полученных из регулярных выражений вида Q^*, то В определяет конечное семейство {t} размеченных путей, начинающихся в логической вершине Р и включающих ее s–последователя. Но тогда выражение В^h определяет все функции, которые определяются размеченными путями, полученными из {t} не более, чем h-кратными конкатенациями. В этом случае в силу конечности числа путей, участвующих в конкатенациях, наличие представляющей логической формулы для функций, порождаемых выражением В^h, следует из предыдущего абзаца индуктивных рассуждений.

Лемма доказана.

Из этих рассуждений вытекает, что при любом означивании метапеременных a формулы F^h истинным является в точности один из дизъюнктивных членов, в точности при одном означивании оставшихся метапеременных. Таким образом, все значения метапеременной a формулы F^h разбиваются на h + 1 классов эквивалентности.

3. О некоторых свойствах формул, порожденных программами. Пусть формула G представляет параметрическое выражение R¢_p и программа p обладает ограничением p(|x|) на длину вычисления в зависимости от входных значений. Величину p(|x|) назовем длиной формулы G. Нашей задачей будет описание зависимости минимальной длины вычислений программы и, следовательно, длины формулы G от вида функции, которую вычисляет программа.

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

1. Если в формуле G встречается формула 0(a), где a = a₀, …, a_m … , то a₀ = … = a_m = … = 0. Очевидно, это единственное означивание логических метапеременных, при котором формула 0(a) истинная.

2. Если в формуле G встречается формула S^l(a, b), a = a₀, …, a_m , …, b = b₀,  …, b_m , … , и логические метапеременные a₀, …, a_m , … уже означены, то означивание логических метапеременных b₀,  …, b_m , … получается из двоичного представления числа |a| + l. Здесь |a| - это двоичное число, полученное из бесконечной последовательности значений метапеременных a₀, …, a_m , … отбрасыванием правой бесконечной нулевой части, расположенной правее последнего единичного компонента. Очевидно, что при таком означивании метапеременных a, b формула S^l истинная. При любом другом означивании логических метапеременных b₀,  …, b_m , … она ложна.