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

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

Задача 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 \] ), управление просто передается на оператор печати.