$$\mathrm{len}\left(〈x_1,\mathrm{\dots },x_n〉\right)=n\text{.}$$

Поскольку добавление элемента в конец последовательности увеличивает длину на единицу, получаем $$\mathrm{len}\left(\omega ∟x\right)=\mathrm{len}\left(\omega \right)+1\text{,}$$ то есть $$F\left(f,x\right)=f+1\text{.}$$ Как видно, получившаяся функция $F$ фактически не зависит от $x$, но в этом нет никакого криминала. Существование функции $F$ доказывает индуктивность функции $\mathrm{len}$.

$$\mathrm{sum}\left(〈x_1,\mathrm{\dots },x_n〉\right)=x_1+\mathrm{\dots }+x_n=\sum _{i=1}^n{x}_i\text{.}$$

Добавление элемента $x$ к последовательности $\omega$ увеличивает сумму на величину добавляемого элемента: $$\mathrm{sum}\left(\omega ∟x\right)=\mathrm{sum}\left(\omega \right)+x\text{,}F\left(f,x\right)=f+x\text{.}$$

Сумма, таким образом, тоже оказалась индуктивной функцией. Однако есть одна проблема: что считать суммой пустой последовательности? Что-то подсказывает нам, что это ноль, но это лишь наше смутное ощущение. На самом деле мы можем обосновать этот ноль совершенно формально: $$\mathrm{sum}\left(〈〉∟x\right)=\mathrm{sum}\left(〈x〉\right)=x=\mathrm{sum}\left(〈〉\right)+x\text{,}$$ откуда $\mathrm{sum}\left(〈〉\right)=0$. Иными словами, единственный способ доопределить сумму для пустой последовательности, не нарушив индуктивности — положить её равной нулю.

Так выглядит реализация алгоритма вычисления суммы чисел из командной строки:

examples/perl/inductive-sum.plPerl
#!/usr/bin/perl

use warnings;

my $sum=0;

for my $x(@ARGV)
{
	$sum+=$x;
}

print "$sum\n";

Случай произведения элементов последовательности во всём похож на случай суммы: $$\mathrm{prod}\left(〈x_1,\mathrm{\dots },x_n〉\right)=x_1\cdot \mathrm{\dots }\cdot x_n=\prod _{i=1}^n{x}_i\text{.}$$

Точно так же, как и для суммы, устанавливается индуктивность: $$\mathrm{prod}\left(\omega ∟x\right)=\mathrm{prod}\left(\omega \right)\cdot x\text{,}F\left(f,x\right)=fx\text{.}$$

Уже знакомая нам проблема доопределения функции для пустой последовательности решается аналогично: $$\mathrm{prod}\left(〈〉∟x\right)=\mathrm{prod}\left(〈x〉\right)=x=\mathrm{prod}\left(〈〉\right)\cdot x\text{,}$$ и значит, $\mathrm{prod}\left(〈〉\right)=1$.

Программа:

examples/perl/inductive-prod.plPerl
#!/usr/bin/perl

use warnings;

my $prod=1;

for my $x(@ARGV)
{
	$prod*=$x;
}

print "$prod\n";

$$\mathrm{last}\left(〈x_1,\mathrm{\dots },x_n〉\right)=x_n\text{.}$$

Эта функция индуктивна, поскольку $$\mathrm{last}\left(\omega ∟x\right)=x\text{,}F\left(f,x\right)=x\text{.}$$

Очевидно, что для пустой последовательности функцию $\mathrm{last}$ можно доопределить как угодно, не нарушая индуктивности.

Программа:

examples/perl/inductive-last.plPerl
#!/usr/bin/perl

use warnings;

my $last=undef;

for my $x(@ARGV)
{
	$last=$x;
}

print "$last\n";

Пусть задано число $t$. Требуется вычислить значение многочлена $$p\left(t\right)=x_1{t}^{n-1}+x_2{t}^{n-2}+x_3{t}^{n-3}+\dots +x_{n-1}t+x_n\text{.}$$ Можно представлять себе искомое значение как значение функции на последовательности коэффициентов многочлена, расположенных по убыванию степеней $t$. Обозначим эту функцию как $\mathrm{horner}\left(\omega \right)$ (почему именно так, выяснится позже). Как и раньше, исследуем эту функцию на предмет её индуктивности.

Преобразуем выражение для многочлена: $$\mathrm{horner}\left(\omega \right)=\left(\dots \left(\left(\left(x_{1}t+x_2\right)t+x_3\right)t+x_4\right)t+\dots \right)t+x_n\text{.}$$ Теперь видно, что происходит со значением многочлена при добавлении в последовательность коэффициентов ещё одного: старое значение умножается на $t$, после чего прибавляется новый коэффициент: $$\mathrm{horner}\left(\omega ∟x\right)=\mathrm{horner}\left(\omega \right)\cdot t+x\text{,}F\left(f,x\right)=ft+x\text{.}$$

Легко видеть, что для пустой последовательности функция доопределяется, исходя из равенства $\mathrm{horner}\left(〈〉\right)\cdot t=0$, следовательно, $\mathrm{horner}\left(〈〉\right)=0$ при ненулевом $t$. При нулевом можно выбрать произвольное значение.

Следует заметить, что функция $\mathrm{horner}$ при $t=1$ превращается в $\mathrm{sum}$, а при $t=0$ — в $\mathrm{last}$.

Приведённый способ вычисления значения многочлена в точке $t$ называется схемой Горнера. Этот способ очень эффективный, поскольку требует, помимо сложения, лишь $n$ операций умножения, и вовсе не нуждается в возведениях в степень (мы полагаем, что возведение в степень, даже в натуральную, требует бо́льших вычислительных усилий, чем умножение).

Следующая программа вычисляет значение многочлена в заданной точке по схеме Горнера. Число $t$ и коэффициенты многочлена в порядке убывания степеней заданы, как обычно, в командной строке:

examples/perl/inductive-horner.plPerl
#!/usr/bin/perl

use warnings;

my $t=shift;
my $p=0;

for my $x(@ARGV)
{
	$p=$p*$t+$x;
}

print "$p\n";

По определению $$\min \left(〈x_1,\mathrm{\dots },x_n〉\right)=x_j\text{,}$$ где $\forall i\in \left\{1,\dots ,n\right\}\Rightarrow x_j⩽x_i$. Заметим, что таких $x_j$ может быть и несколько, однако, к счастью, все они равны между собой.

Эта функция индуктивна, поскольку $$\min \left(\omega ∟x\right)=\left\{\begin{array}{l}\text{если}x<\min \left(\omega \right)\text{, то}x\\ \text{иначе}\min \left(\omega \right)\text{.}\end{array}\right.$$ Таким образом, $$F\left(f,x\right)=\left\{\begin{array}{l}\text{если}x<f\text{, то}x\\ \text{иначе}f\end{array}\right\}=\min \left(f,x\right)\text{.}$$

Увы, функция $\min \left(\omega \right)$ не определена для пустой последовательности. Попытка доопределить функцию с сохранением индуктивности приводит к равенству $$\min \left(〈x〉\right)=x=\min \left(\min \left(〈〉\right),x\right)\text{,}$$ которое означает, что $\min \left(〈〉\right)$ должно быть не меньше любого $x$. Числа с таким свойством не существует, однако, если в последовательности могут встретиться числа лишь из ограниченного числового множества (на практике так обычно и бывает), то можно взять наибольшее число из этого множества в качестве $\min \left(〈〉\right)$. В теории, когда $x$ может принимать любое, сколь угодно большое значение, можно позволить индуктивной функции принимать, помимо числовых значений, ещё идеальное значение $+\infty$, от которого требуется лишь выполнение неравенства $x<+\infty$ для всех $x$.

Совершенно аналогично устанавливается индуктивность максимума, для которого $$\max \left(\omega ∟x\right)=\left\{\begin{array}{l}\text{если}x>\max \left(\omega \right)\text{, то}x\\ \text{иначе}\max \left(\omega \right)\text{.}\end{array}\right.$$ Для пустой последовательности максимум доопределяется значением $-\infty$.

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

examples/perl/inductive-minmax.plPerl
#!/usr/bin/perl

use warnings;

my $min=INFINITY;
my $max=-INFINITY;

for my $x(@ARGV)
{
	($min, $max)=($x<$min? $x: $min, $x>$max? $x: $max);
}

print "$min\t$max\n";

Функция $\mathrm{search}\left(〈x_1,\mathrm{\dots },x_n〉\right)$ принимает значения $\mathbf{да}$ или $\mathbf{нет}$ в зависимости от того, содержится ли значение $a$ среди элементов $x_1,\mathrm{\dots },x_n$.

Эта функция индуктивна: $$\mathrm{search}\left(\omega ∟x\right)=\left(\mathrm{search}\left(\omega \right)\vee \left(x=a\right)\right)\text{,}$$ её функция перевычисления равна $$F\left(f,x\right)=\left(f\vee \left(x=a\right)\right)\text{.}$$

Программа берёт $a$ и элементы последовательности из командной строки и печатает YES или NO:

examples/perl/inductive-search.plPerl
#!/usr/bin/perl

use warnings;

my $a=shift;
my $search=0;

for my $x(@ARGV)
{
	$search||=($x==$a);
}

print $search? 'YES': 'NO', "\n";

$$\mathrm{avg}\left(〈x_1,\mathrm{\dots },x_n〉\right)=\frac{x_1+\mathrm{\dots }+x_n}{n}\text{.}$$ У читателя уже могло сложиться впечатление, что все функции на пространстве последовательностей являются индуктивными. Это не так, и среднее арифметическое тому подтверждение. Для доказательства достаточно рассмотреть пример. Если бы существовала такая функция $F$, что $$\mathrm{avg}\left(\omega ∟x\right)=F\left(\mathrm{avg}\left(\omega \right),x\right)\text{,}$$ выполнялись бы равенства $$\begin{array}{l}\mathrm{avg}\left(〈0,1〉\right)=\frac{1}{2}=F\left(\mathrm{avg}\left(〈0〉\right),1\right)=F\left(0,1\right)\text{,}\\ \mathrm{avg}\left(〈0,0,1〉\right)=\frac{1}{3}=F\left(\mathrm{avg}\left(〈0,0〉\right),1\right)=F\left(0,1\right)\text{,}\end{array}$$ которые, очевидно, не могут выполняться одновременно.

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

С точки зрения поставленной задачи все символы делятся на две категории: пробельные и непробельные. Никакие другие свойства символов не важны, поэтому можно кодировать символы логическими значениями $\mathbf{нет}$ (пробелы) и $\mathbf{да}$ (непробелы). Так что будем иметь дело с последовательностями логических значений $\omega \in \Omega \left(\left\{\mathbf{нет},\mathbf{да}\right\}\right)$. Искомую функцию обозначим $\mathrm{wc}\left(\omega \right)$ (Word Count — счётчик слов).

Понятно, что знания $\mathrm{wc}\left(\omega \right)$ и $x$ недостаточно для вычисления $\mathrm{wc}\left(\omega ∟x\right)$: счётчик слов увеличивается в том и только в том случае, если добавляемый элемент — непробел, а последний элемент — пробел (то есть происходит смена пробела на непробел). В результате получим выражение $$\mathrm{wc}\left(\omega ∟x\right)=\left\{\begin{array}{l}\text{если}x\wedge \neg \mathrm{last}\left(\omega \right)\text{, то}\mathrm{wc}\left(\omega \right)+1\\ \text{иначе}\mathrm{wc}\left(\omega \right)\text{.}\end{array}\right.$$

Вывод: функция $\mathrm{wc}$ не индуктивна.

В некоторых случаях можно сократить вычисление значения индуктивной функции за счёт устранения ненужных действий. Такая ситуация наступает, если после обработки части последовательности вычисленное значение индуктивной функции окажется стационарным, то есть таким, что никакое дальнейшее перевычисление не может его изменить. Более строго, значение $y=f\left(\omega \right)$ называется стационарным, если $\forall x\in X\Rightarrow F\left(y,x\right)=y$. Если $f\left(\omega \right)=y$, то, очевидно, $f\left(\omega ∟x\right)=y$, и, как бы мы ни удлиняли в дальнейшем последовательность, значение функции останется тем же самым стационарным значением $y$. Это означает, что, получив стационарное значение, можно прервать цикл обработки последовательности.

С учётом сказанного, внесём в алгоритм вычисления индуктивной функции дополнение: $$\begin{array}{l}f\leftarrow f\left(〈〉\right)\\ \mathbf{\text{цикл пока}}\text{есть непрочитанные элементы в}\omega \\ x\leftarrow \text{следующий элемент}\omega \\ f\leftarrow F\left(f,x\right)\\ \mathbf{\text{если}}f\text{является стационарным,}\mathbf{\text{то}}\mathbf{\text{выход}}\\ \mathbf{\text{конец цикла}}\\ \mathbf{\text{вывод}}f\end{array}$$

Из разобранных к настоящему моменту примеров индуктивных функций стационарные значения имеются у функций $\mathrm{prod}$: $0$, $\min$: $-\infty$, $\max$: $\infty$ и $\mathrm{search}$: $\mathbf{да}$.

Ещё пара примеров функций на пространстве последовательностей логических значений. Для индуктивной функции $$\mathrm{and}\left(〈x_1,\dots ,x_n〉\right)=x_1\wedge \dots \wedge x_n=\underset{i=1}{\overset{n}{\bigwedge }}{x}_i$$ стационарным значением служит $\mathbf{нет}$, а для функции $$\mathrm{or}\left(〈x_1,\dots ,x_n〉\right)=x_1\vee \dots \vee x_n=\underset{i=1}{\overset{n}{\bigvee }}{x}_i$$ — $\mathbf{да}$.