Индуктивные функции на пространстве последовательностей

В первом параграфе данной главы мы уже познакомились с индуктивными функциями и даже рассмотрели простейшую программу, написанную с помощью применения схемы вычисления индуктивной функции — программу вычисления значения многочлена (см. решение задачи 7.6 лекция 7). К сожалению, подавляющее большинство функций на пространстве последовательностей индуктивными не являются, что требует дальнейшего развития теории.

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

Критерий индуктивности и стационарные значения

Напомним основное определение.

Функция $$f\colon X^* \rightarrow Y$$ называется индуктивной, если $$f(\omega\circ x)$$ можно вычислить, зная $$f(\omega)$$ и $$x$$, т.е. если $$\exists G\colon Y \times X\rightarrow Y$$ такое, что $$\forall \omega\in X^* \ \forall x\in X\ f(\omega\circ x) = G(f(\omega),x)$$.

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

Теорема 9.1. Критерий индуктивности. $$f\colon X^* \rightarrow Y$$ индуктивна $$\Longleftrightarrow \big(\forall a, b \in X^*\ \forall x \in X\ f(a) = f(b) \Rightarrow f(a\circ x) = f(b\circ x)\big)$$.

Теорема утверждает, что $$f$$ индуктивна тогда и только тогда, когда из равенства значений $$f$$ на последовательностях $$a$$ и $$b$$ следует равенство значений $$f$$ на любых одинаково удлиненных последовательностях $$a\circ x$$ и $$b\circ x$$.

Доказательство Необходимость сформулированного в критерии условия немедленно следует из определения индуктивности. Если $$f$$ — индуктивна, то $$\forall a, b \in X^*\ \forall x \in X f(a\circ x) = G(f(a),x) = G(f(b),x) = f(b\circ x)$$.

Для доказательства достаточности построим требуемое отображение $$G\colon Y \times X\rightarrow Y$$ такое, что $$\forall \omega\in X^* \ \forall x\in X\ f(\omega\circ x) = G(f(\omega),x)$$. Зададим это отображение формулой

$$G(y,x)=\begin{cases} f(\omega\circ x), \text{если существует $\omega\in X^*$ такая, что $f(\omega)=y$},\\ y, \text{иначе}. \end{cases}$$

Корректность этого определения вытекает из заданного в условии теоремы свойства функции $$f$$. В самом деле, пусть найдутся две различные цепочки $$a$$ и $$b$$ такие, что $$f(a) = f(b)$$. Тогда можно гарантировать, что $$f(a\circ x) = f(b\circ x)$$, что и доказывает корректность определения отображения $$G$$, ибо $$G(y,x)$$ действительно не зависит от выбора конкретного прообраза элемента $$y$$.

Так как $$\forall \omega\in X^* \ \forall x\in X\ f(\omega\circ x) = G(f(\omega),x)$$ для построенного отображения $$G$$, то теорема полностью доказана.

В качестве примера использования критерия индуктивности докажем, что функция $$f\colon \mathbb{Z}^*\rightarrow \mathbb{Z}$$ количество максимальных элементов последовательности целых чисел не является индуктивной. Возьмем $$a=1$$, $$b=2$$, $$x=2$$. Тогда $$f(a)=f(b)=1$$, но $$f(a\circ x) = 1 \ne 2 = f(b\circ x)$$.

Схема вычисления индуктивной функции, приведенная в лекции 7, может быть несколько упрощена при условии наличия у функции так называемых стационарных значений.

Определение 9.1. Значение $$y \in Y$$ индуктивной функции $$f\colon X^* \rightarrow Y$$ называется стационарным, если $$\forall \omega\in X^*\ \forall x \in X \ f(\omega) = y \Rightarrow f(\omega\circ x)=y$$.

Так, например, для функции $$f\colon \{0,1\}^*\rightarrow \{T,F\}$$ все элементы цепочки равны нулю значение $$F$$ является стационарным.

В том случае, если индуктивная функция определена только на $$X^*_k$$ для $$k>0$$, ее вычисление может начинаться не с пустой, a с одноэлементной или даже более длинной цепочки. Это, однако, приводит к более сложной программе, чего можно иногда избежать, доопределяя исходную функцию.

Индуктивную функцию $$f\colon \mathbb{Z}^*_1\rightarrow \mathbb{Z}$$ произведение элементов числовой последовательности можно доопределить с сохранением функции $$G$$ следующим образом: $$f(\varepsilon)=1$$.

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

Индуктивные расширения

Определение 9.2. Функция $$F\colon X^* \rightarrow \widetilde Y$$ называется индуктивным расширением функции $$f\colon X^* \rightarrow Y$$, если

1) $$F$$ индуктивна,

2) $$\exists \pi\colon \widetilde Y\rightarrow Y$$ такое, что $$\forall \omega \in X^* \ f(\omega) = \pi(F(\omega))$$.

Рассмотрим функцию $$f\colon \mathbb{R}^*_1 \rightarrow \mathbb{R}$$ среднее арифметическое элементов последовательности, которая не является индуктивной. Тогда функция $$F\colon \mathbb{R}^*_1 \rightarrow \mathbb{R}\times \mathbb{N}$$, определенная по формуле $$F(\omega)=((s(\omega), n(\omega)))$$, где $$\omega = a_1a_2\ldots a_n$$, $$\displaystyle s(\omega)=\sum_{i=1}^{n} a_i$$, а $$n=|\omega|$$, является индуктивным расширением исходной функции $$f$$, и $$\pi(s,n) = s/n$$.

Для вычисления значения $$f(\omega)$$ не являющейся индуктивной функции $$f$$ на цепочке $$\omega$$ применяется следующая обобщенная схема.

Обобщенная схема вычисления индуктивной функции. Строится индуктивное расширение $$F$$ исходной функции, которое позволяет ценой увеличения запоминаемой информации о цепочке $$\omega$$ (в $$F(\omega)$$ информации больше, чем в $$f(\omega)$$ ) применить схему вычисления индуктивной функции к $$F(\omega)$$ , а затем просто найти $$f(\omega)=\pi(F(\omega))$$.

Пусть $$F_1\colon X^* \rightarrow \widetilde Y_1$$ и $$F_2\colon X^* \rightarrow \widetilde Y_2$$ — два индуктивных расширения функции $$f\colon X^* \rightarrow Y$$. Будем говорить, что $$F_1 \geqslant F_2$$, если $$\exists \pi\colon \widetilde Y_1 \rightarrow \widetilde Y_2$$ такое, что $$\forall \omega \in X^*\ F_2(\omega) = \pi(F_1(\omega))$$.

Определение 9.3. Минимальным индуктивным расширением функции $$f\colon X^* \rightarrow Y$$ называется индуктивное расширение $$\widehat F\colon X^* \rightarrow \widehat Y$$ такое, что

1) $$\widehat F(X^*) = \widehat Y \qquad (\widehat F$$ — сюръективно);

2) для любого индуктивного расширения $$F$$ функции $$f$$ выполнено

$$F \geqslant \widehat F$$.

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

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

Теорема 9.2. Минимальное индуктивное расширение любой функции $$f\colon X^* \rightarrow Y$$ единственно с точностью до изоморфизма.

Доказательство Пусть для функции $$f\colon X^* \rightarrow Y$$ существуют два минимальных индуктивных расширения $$F_1\colon X^* \rightarrow \widetilde Y_1$$ и $$F_2\colon X^* \rightarrow \widetilde Y_2$$. Тогда в силу их минимальности имеем $$F_1(X^*) = \widetilde Y_1$$ и $$F_2(X^*) = \widetilde Y_2$$.

Так как $$F_1 \geqslant F_2$$ (ибо $$F_2$$ — минимально), то $$\exists p_{12}\colon \widetilde Y_1 \rightarrow \widetilde Y_2$$ такое, что $$\forall \omega \in X^*\ F_2(\omega) = p_{12}(F_1(\omega))$$. С другой стороны, $$F_2 \geqslant F_1$$ и $$\exists p_{21}\colon \widetilde Y_2 \rightarrow \widetilde Y_1$$ такое, что $$\forall \omega \in X^*\ F_1(\omega) = p_{21}(F_2(\omega))$$. Для доказательства теоремы нужно показать, что отображения $$p_{12}$$ и $$p_{21}$$ биективны. Рассмотрим композиции этих отображений $$p_{12}\circ p_{21}$$ и $$p_{21}\circ p_{12}$$ и докажем, что они являются тождественными отображениями множеств $$\widetilde Y_2$$ и $$\widetilde Y_1$$ соответственно (из этого и следует биективность отображений $$p_{12}$$ и $$p_{21}$$ ).

Возьмем произвольный элемент $$y_1\in\widetilde Y_1$$. Из сюръективности $$F_1$$ следует, что найдется цепочка $$\omega \in X^*$$, такая что $$F_1(\omega)=y_1$$ и поэтому $$\forall y_1\ y_1=F_1(\omega)= p_{21}(F_2(\omega)) = p_{21}(p_{12}(F_1(\omega)))=p_{21}(p_{12}(y_1))=(p_{21}\circ p_{12})(y_1)$$. Полученное равенство показывает, что $$p_{21}\circ p_{12} = Id_{\widetilde Y_1}$$ — тождественное отображение. Рассматривая произвольный элемент $$y_2\in\widetilde Y_2$$, аналогично получаем, что $$p_{12}\circ p_{21} = Id_{\widetilde Y_2}$$, что и завершает доказательство теоремы.

Критерий минимальности

Перед тем, как сформулировать критерий минимальности, докажем существование минимального индуктивного расширения.

Теорема 9.3. Минимальное индуктивное расширение для любой функции $$f\colon X^* \rightarrow Y$$ существует.

Доказательство Для доказательства теоремы построим в три этапа каноническое минимальное индуктивное расширение $$\widehat F\colon X^* \rightarrow \widehat Y$$ заданной функции $$f$$.

Первый этап. Рассмотрим на множестве цепочек $$X^*$$ бинарное отношение $$\approx$$, задаваемое формулой $$a\approx b \Longleftrightarrow (\forall \omega \in X^* \ f(a\circ \omega) = f(b\circ \omega))$$, и покажем, что

1) $$\approx$$ — отношение эквивалентности на $$X^*$$ ;

2) $$\forall a,b\in X^*\ \forall x\in X\ a\approx b \Rightarrow a\circ x\approx b\circ x$$ ;

3) $$\forall a,b\in X^*\ a\approx b \Rightarrow f(a)=f(b)$$.

Рефлексивность, симметричность и транзитивность отношения $$\approx$$ вытекают соответственно из рефлексивности, симметричности и транзитивности отношения равенства.

Так как $$a\circ x\approx b\circ x\Longleftrightarrow (\forall \omega_1 \in X^* \ f(a\circ x\circ \omega_1) = f(b\circ x\circ \omega_1))$$, то взяв в качестве цепочки $$\omega$$, фигурирующей в определении отношения $$\approx$$, $$\omega=x\circ \omega_1$$, убеждаемся в истинности второго свойства.

Свойство 3) немедленно следует из определения отношения $$\approx$$, если в качестве $$\omega$$ взять пустую цепочку $$\varepsilon$$.

Второй этап. Построим пространство $$\widehat Y$$ и отображение $$\widehat F\colon X^* \rightarrow \widehat Y$$. В качестве $$\widehat Y$$ возьмем фактормножество (множество классов эквивалентности) $$X^*/\approx$$, что можно сделать в силу свойства 1). Договоримся обозначать класс эквивалентности, содержащий цепочку $$\omega$$ через $$[\omega]$$ и определим отображение $$\widehat F\colon X^* \rightarrow \widehat Y$$ формулой $$\widehat F(\omega)= [\omega]$$.

Переписав свойство 2) в эквивалентном виде $$\forall a,b\in X^*\ \forall x\in X\ \widehat F(a)= \widehat F(b) \Rightarrow \widehat F(a\circ x) = \widehat F(b\circ x)$$, из критерия индуктивности заключаем, что отображение $$\widehat F$$ — индуктивно.

Покажем, что $$\widehat F$$ является индуктивным расширением исходной функции $$f\colon X^* \rightarrow Y$$. Определим проекцию $$\pi\colon \widehat Y \rightarrow Y$$ формулой $$\pi([\omega])=f(\omega)$$. Корректность этого определения следует из свойства 3) — если две цепочки $$\omega_1$$ и $$\omega_2$$ принадлежат одному классу эквивалентности, то значение функции $$f$$ на них совпадает. Так как $$f(\omega) = \pi(\widehat F(\omega))$$ для произвольной цепочки $$\omega\in X^*$$, то $$\widehat F$$ действительно является индуктивным расширением отображения $$f$$.

Третий этап. Нам осталось показать, что построенное каноническое индуктивное расширение является минимальным.

Сюръективность $$\widehat F$$ следует непосредственно из его построения, ибо каждый класс эквивалентности $$[\omega]$$ не пуст.

Предположим далее, что существует $$\widetilde F\colon X^* \rightarrow \widetilde Y$$ — иное индуктивное расширение исходной функции $$f$$, тогда для завершения доказательства теоремы нам необходимо показать, что $$\widetilde F \geqslant \widehat F$$.

Определим проекцию $$p \colon \widetilde Y \rightarrow \widehat Y$$ формулой $$p(y) = [\omega]$$, где $$\omega$$ — один из прообразов элемента $$y$$ при отображении $$\widetilde F$$. Проверим корректность данного определения.

Пусть $$\widetilde F(\omega_1) = \widetilde F(\omega_2) = y$$. Тогда в силу индуктивности $$\widetilde F$$ для произвольной цепочки $$\omega$$ справедливо равенство $$\widetilde F(\omega_1\circ\omega) = \widetilde F(\omega_2\circ\omega)$$, а так как $$\widetilde F$$ — индуктивное расширение функции $$f$$, то и $$f(\omega_1\circ\omega) = f(\omega_2\circ\omega)$$. Полученное равенство может быть переписано в виде $$[\omega_1]=[\omega_2]$$, показывающем корректность определения проекции $$p$$.

Равенство $$\widehat F(\omega) = [\omega] = p(\widetilde F(\omega))$$ для произвольной цепочки $$\omega\in X^*$$ показывает, что $$\widetilde F \geqslant \widehat F$$. Теорема полностью доказана.

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

Теорема 9.4. Критерий минимальности. Индуктивное расширение $$\widetilde F\colon X^* \rightarrow \widetilde Y \text{\ функции\ } f\colon X^* \rightarrow Y \text{ — минимально} \Longleftrightarrow ( (\widetilde F(X^*)=\widetilde Y) \land (\forall a,b\in X^*\ \widetilde F(a)\ne \widetilde F(b) \Rightarrow a\not\approx b) )$$.

Доказательство Необходимость первого условия критерия следует непосредственно из определения минимальности. Второе условие выполнено по построению для канонического минимального индуктивного расширения $$\widehat F\colon X^* \rightarrow \widehat Y$$, а так как по теореме единственности отображения $$\widehat F$$ и $$\widetilde F$$ изоморфны, то и для $$\widetilde F$$.

Для доказательства достаточности рассмотрим каноническое минимальное индуктивное расширение $$\widehat F\colon X^* \rightarrow \widehat Y$$ и покажем, что оно изоморфно нашему $$\widetilde F \colon X^* \rightarrow \widetilde Y$$. В силу минимальности $$\widehat F$$ существует отображение $$p \colon \widetilde Y \rightarrow \widehat Y$$, такое что $$\widehat F(\omega) = p(\widetilde F(\omega))$$ для произвольной цепочки $$\omega\in X^*$$. Критерий будет доказан, если мы покажем, что отображение $$p$$ — биекция.

Сюръективность $$p$$ вытекает из сюръективности $$\widehat F$$ и $$\widetilde F$$, а инъективность доказывается следующим рассуждением. Рассмотрим различные $$u$$ и $$v$$ из $$\widetilde Y$$ и, воспользовавшись сюръективностью $$\widetilde F$$, найдем цепочки $$a$$ и $$b$$ из $$X^*$$ такие, что $$\widetilde F(a) = u$$, а $$\widetilde F(b) = v$$. Так как $$\widetilde F(a)\ne \widetilde F(b)$$, то в силу данного нам условия $$a\not\approx b$$, что эквивалентно неравенству $$\widehat F(a)\ne \widehat F(b)$$.

Следовательно, отображение $$p$$ различные $$u$$ и $$v$$ преобразует в различные же $$p(u)=\widehat F(a)$$ и $$p(v)=\widehat F(b)$$, что и требовалось доказать.

Докажем, что функция $$F\colon \mathbb{R}^*_1 \rightarrow \mathbb{R}\times \mathbb{N}$$, определенная по формуле $$\displaystyle F(\omega)=\left(\sum_{i=1}^{n} a_i, n\right)$$, где $$\omega = a_1a_2\ldots a_n$$, $$n=|\omega|$$ и $$\pi(s,n) = s/n$$, является минимальным индуктивным расширением для $$f\colon \mathbb{R}^*_1 \rightarrow \mathbb{R}$$ среднее арифметическое элементов последовательности. Для доказательства сюръективности функции $$F$$ предъявим прообраз произвольного элемента $$(s,n) \in \mathbb{R}\times \mathbb{N}$$. Им будет цепочка из $$n$$ элементов, первый из которых равен $$s$$, а остальные — нулевые. Для того чтобы проверить второе условие критерия минимальности, необходимо убедиться в том, что $$\forall a,b\in X^*\ F(a)\ne F(b)\ \exists \omega \in X^*\ f(a\circ \omega) \ne f(b\circ \omega)$$. Пусть $$F(a)=(s_1,n_1)$$, $$F(b)=(s_2,n_2)$$ и либо $$s_1\ne s_2$$, либо $$n_1\ne n_2$$. Если для пустой цепочки $$\omega= \varepsilon$$ верно, что $$f(a\circ \omega) \ne f(b\circ \omega)$$, то все доказано. Иначе имеем $$s_1/n_1 = f(a) = f(b) = s_2/n_2$$. Возьмем теперь в качестве $$\omega$$ одноэлементную цепочку $$0$$. Предположив, что для нее $$f(a\circ \omega) = f(b\circ \omega)$$, из системы

$$\begin{cases} s_1/n_1 = s_2/n_2,\\ s_1/(n_1+1)=s_2/(n_2+1) \end{cases}$$

получим $$s_1=s_2$$, $$n_1=n_2$$, что противоречит предположению. Это завершает доказательство минимальности $$F$$.

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

Теорема 9.5. Для произвольной функции $$f$$ на пространстве последовательностей существует единственный с точностью до изоморфизма однопроходный алгоритм с минимальной емкостной сложностью.

Применение теории индуктивных функций

В качестве первого примера рассмотрим уже встречавшуюся нам ранее задачу.

Задача 9.1. Напишите программу, вводящую последовательность целых чисел, и печатающую количество ее максимальных элементов.

Решение В данной задаче $$X=\mathbb{Z}_M$$, $$Y=\mathbb{Z}_M^+$$, $$f\colon X^* \rightarrow Y$$. Взяв $$a=1$$, $$b=2$$, $$x=2$$, находим $$f(a)=f(b)=1$$, но $$f(a\circ x) = 1 \ne 2 = f(b\circ x)$$. Из отрицания критерия индуктивности заключаем, что $$f$$ не является индуктивной.

Для построения ее индуктивного расширения $$F$$ применим стандартный прием. Попробуем выразить значение функции $$f(\omega\circ x)$$ на удлиненной цепочке через ее значение $$f(\omega)$$ на исходной и элемент $$x$$. Известно, что это невозможно сделать ( $$f$$ — не является индуктивной), но наша цель — понять какой именно информации не хватает и, добавив ее, образовать функцию $$f_1$$. Рассмотрим теперь функцию $$F_1=(f, f_1)$$. В том случае, если она индуктивна, требуемое расширение построено. Иначе повторим предыдущие действия и попытаемся выразить $$f(\omega\circ x)$$ и $$f_1(\omega\circ x)$$ через $$f(\omega)$$, $$f_1(\omega)$$ и $$x$$ с использованием дополнительной информации $$f_2(\omega)$$. Получаем следующего кандидата на роль индуктивного расширения — функцию $$F_2=(f, f_1, f_2)$$. При необходимости данный процесс может быть продолжен и далее, а его завершение гарантируется теоремой о существовании индуктивного расширения. В данном случае имеем $$f(\varepsilon) = 0$$,

$$f(\omega\circ x)=\begin{cases} f(\omega), \text{если $x<\max(\omega)$},\\ f(\omega)+1, \text{если $x=\max(\omega)$},\\ 1, \text{если $x>\max(\omega)$}. \end{cases}$$

Мы видим, что в качестве $$f_1$$ следует взять функцию $$\max$$, вычисляющую максимальное значение элементов цепочки. Тогда для $$F=(f,f_1)$$ получаем

$$F(\omega\circ x)=\begin{cases} (f(\omega),f_1(\omega)) \text{если $x<f_1(\omega)$},\\ (f(\omega)+1,f_1(\omega)) \text{если $x=f_1(\omega)$},\\ (1,x) \text{если $x>f_1(\omega)$}. \end{cases}$$

Эта функция, однако, не определена на пустой цепочке, поэтому $$F=(f,f_1)\colon (\mathbb{Z}_M)^*_1 \rightarrow \mathbb{Z}_M^+\times \mathbb{Z}_M$$ также определена только на $$(\mathbb{Z}_M)^*_1$$. Воспользовавшись тем, что диапазон представления целых чисел на ЭВМ ограничен, в данном случае можно доопределить $$F$$ с сохранением функции перевычисления следующим образом: $$f_1(\varepsilon)=$$ "Integer.MIN\_VALUE" ( $$-2147483648$$ для языка Java). Действительно, если принять, что максимальным элементом пустой цепочки является минимально представимое на ЭВМ целое число, то $$F(\varepsilon) = (0, "Integer.MIN\_VALUE")$$, а функция $$G\colon \mathbb{Z}_M^+\times \mathbb{Z}_M\times \mathbb{Z}_M\rightarrow \mathbb{Z}_M^+\times \mathbb{Z}_M$$ определяется формулой

$$G((y_1,y_2),x) = \begin{cases} (y_1,y_2) \text{если $x<y_2$},\\ (y_1+1,y_2) \text{если $x=y_2$},\\ (1,x) \text{если $x>y_2$}. \end{cases}$$

Отображение $$\pi\colon \mathbb{Z}_M^+\times \mathbb{Z}_M\rightarrow \mathbb{Z}_M^+$$ тривиально: $$\pi(y_1,y_2)=y_1$$.

Докажем, что построенное нами расширение $$F$$ не является минимальным. Для этого достаточно предъявить значение $$(y_1,y_2)\in \mathbb{Z}_M^+\times \mathbb{Z}_M$$, которое не принимается ни на одной цепочке. Таковым будет, например, $$(0,1)$$. Докажите самостоятельно, что если вместо пространства $$\mathbb{Z}_M^+\times \mathbb{Z}_M$$ рассмотреть $$((\mathbb{N}_M\times \mathbb{Z}_M)\cup\{0,"Integer.MIN\_VALUE"\})$$, то построенное нами расширение окажется минимальным.

Теперь можно написать программу, реализующую построенный алгоритм.

Текст программы

public class NumMaxSeq2 {
    public static void main(String[] args) {    
        int y1 = 0, y2 = Integer.MIN_VALUE;
        try {
            while (true) {
                int x = Xterm.inputInt("x -> ");
                if (x == y2) {
                    y1 += 1;
                } else if(x > y2) {
                    y1 = 1;
                    y2 = x;
                } 
            }
        } catch (Exception e) {
            Xterm.println("\nn = " + y1);
        }	    
    }
}

Любая ошибка при вводе рассматривается здесь, как завершение последовательности чисел. Имена переменных, имеющихся в программе, совпадают с использованными при построении алгоритма, вычисление $$F(\varepsilon)$$ выполняется с помощью команд "int y1=0, y2=Integer.MIN\_VALUE;", функция $$G$$ реализована при помощи оператора if-else, в котором опущен случай $$x<y_2$$ (так как тогда не нужно изменять ни $$y_1$$, ни $$y_2$$ ), а применение отображения $$\pi$$ сводится к печати только значения $$y_1$$ из вычисленных $$y_1$$ и $$y_2$$.

Следующая задача нам тоже уже знакома.

Задача 9.2. Напишите программу, определяющую номер $$f$$ первого элемента, равного $$x_0$$, в последовательности целых чисел. В том случае, если число $$x_0$$ в последовательности не встречается, положите $$f$$ равным нулю.

Решение Имеем $$f\colon X^* \rightarrow Y$$, где $$X=\mathbb{Z}_M$$, а $$Y=\mathbb{Z}_M^+$$. Если $$x_0=0$$, $$a=\varepsilon$$, $$b=1$$, то $$f(a)=f(b)=0$$, но $$f(a\circ x_0) = 1 \ne 2 = f(b\circ x_0)$$, следовательно $$f$$ не является индуктивной.

Построим ее индуктивное расширение $$F$$. Заметим, что $$f(\varepsilon) = 0$$,

$$f(\omega\circ x)=\begin{cases} f(\omega), \text{если $f(\omega)\ne 0 \lor x\ne x_0$},\\ |\omega|+1, \text{если $f(\omega)= 0 \land x= x_0$}. \end{cases}$$

Следовательно, в качестве $$F(\omega)$$ можно взять пару $$(f(\omega), |\omega|)$$, где функция $$F\colon (\mathbb{Z}_M)^*\rightarrow\mathbb{Z}_M^+\times \mathbb{Z}_M^+$$. Эта функция уже индуктивна, так как $$F(\varepsilon) = (0,0)$$, а преобразование $$G\colon\mathbb{Z}_M^+\times \mathbb{Z}_M^+\times\mathbb{Z}_M \rightarrow\mathbb{Z}_M^+\times \mathbb{Z}_M^+$$ имеет вид

$$G((y_1,y_2),x) = \begin{cases} (y_1, y_2+1), \text{если $y_1\ne 0 \lor x\ne x_0$},\\ (y_2+1, y_2+1), \text{если $y_1= 0 \land x= x_0$}. \end{cases}$$

Заметим, что все значения функции $$f$$, отличные от нуля, являются стационарными, в то время как функция $$F$$ не имеет стационарных значений. Ясно, что отображение $$\pi\colon \mathbb{Z}_M^+\times \mathbb{Z}_M^+\rightarrow \mathbb{Z}_M^+$$ имеет вид $$\pi(y_1,y_2)=y_1$$.

Построенное нами расширение не является минимальным, так как значение $$(1,0)$$ не может быть принято функцией $$F$$ ни на одной цепочке.

Вот программа, не использующая наличия стационарных значений.

Текст программы

public class First1{
    public static void main(String[] args) throws Exception {
        int x0 = Xterm.inputInt("x0 ->");
        int y1 = 0, y2 = 0;
        try {
            while (true) {
                int x = Xterm.inputInt("x -> ");
                y2 += 1;
                if ( (y1 == 0)  (x == x0) )
                    y1 = y2;
            }
        } catch (Exception e) {
            Xterm.println("\nn = " + y1);
        }	    
    }
}

Имена программных переменных совпадают с использованными при построении алгоритма, вычисление $$F(\varepsilon)$$ выполняется с помощью команд "int y1=0, y2=0;", реализация функции $$G$$ очевидна, а применение отображения $$\pi$$ сводится к печати только значения $$y_1$$.

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

Текст программы

public class First2 {
    public static void main(String[] args) throws Exception {
        int x0 = Xterm.inputInt("x0 -> ");
        int y1 = 0, y2 = 0;
        try {
            while (y1 == 0) {
                int x = Xterm.inputInt("x -> ");
                y2 += 1;
                if (x == x0)
                    y1 = y2;
            }
        } catch(Exception e){
            System.exit(0);
        }	    
        Xterm.println("\nn = " + y1);
    }
}

По достижению конца вводимой последовательности эта программа не выполняет никаких специальных действий (оператор ";" в блоке "catch" ). В этой ситуации, как и в случае принятия функцией $$f$$ любого из стационарных значений ( $$y_1 \ne 0$$ ), управление просто передается на оператор печати.