Что такое алгоритм?
Первоначальной целью теории алгоритмов является классификация всех задач на
алгоритмически разрешимые и неразрешимые, т.е. на те, для которых
существуют решающие их алгоритмы, и те, для которых таких алгоритмов нет.
Неформально под алгоритмом $$\mathcal{A}$$ можно понимать выраженный
в некотором языке набор правил (предписание, рецепт, способ),
позволяющий применить к исходным (входным) данным x из некоторого
множества допустимых данных X последовательность дискретных действий
(операций, команд), приводящую к определенному результату - выходным данным $$y= \mathcal{A(x)$$ из некоторого множества Y.
В этом случае говорят, что алгоритм $$\mathcal{A}$$ вычисляет функцию $$F(x)= \mathcal{A}(x)$$ типа X -> Y.
Это нестрогое определение вполне подходит в тех
случаях, когда для некоторой функции нам предъявляется "объект",
называемый алгоритмом ее вычисления (например, алгоритм Эвклида
для вычисления наибольшего общего делителя двух целых чисел),
и можно легко проверить, позволяет ли он действительно вычислить требуемую
функцию. Однако оно совершенно не годится для доказательства того, что
для заданной функции никакого алгоритма нет.
Начиная с тридцатых годов ХХ века, был предпринят ряд исследований для
формализации понятия алгоритма. Перечислим некоторые из предложенных
разными авторами в разное время формальных
моделей: машины Тьюринга-Поста, частично-рекурсивные функции (Гедель, Клини), $$\lambda$$ -исчисление (Черч, Клини), итеративные автоматы Неймана,
нормальные алгорифмы Маркова,
счетчиковые автоматы Минского, автоматы на графах Колмогорова-Барздиня и др.
Заложенные в них идеи в значительной степени повлияли затем на архитектуру и
языки программирования реальных компьютеров (например, на базе $$\lambda$$ -исчисления
построен широко применяемый в задачах искусственного интеллекта язык ЛИСП,
а из нормальных алгорифмов Маркова произошел хорошо подходящий для
текстовой обработки язык РЕФАЛ). Каждый из многочисленных языков
программирования также
задает некоторую формальную модель алгоритмов. Мы вначале рассмотрим один из
простейших таких языков - простые структурированные программы.
А затем сравним их с двумя
другими моделями алгоритмов: описаниями частично рекурсивных функций и машинами Тьюринга.
Хотя алгоритмы в разных прикладных областях имеют дело с дискретными
объектами различных видов: целыми и рациональными числами, строками,
формулами, разного рода выражениями, графами, матрицами, таблицами,
точечными изображениями и др., мы в этой части курса будем
рассматривать только задачи вычисления
функций от натуральных аргументов, принимающих натуральные
значения. Такие функции часто называют арифметическими.
Дело в том, что для любого естественного множества
дискретных объектов (в частности, для всех перечисленных выше) имеется
простое кодирование его элементов целыми числами. Поэтому задачи
вычисления функций на этих множествах превращаются в задачи вычисления арифметических функций.
Напомним, что через N обозначается
множество натуральных чисел, т.е. N={0,1,2,...}.
Для частичной n - местной арифметической функции f: Nn -> N через $$\Delta _{f}$$ обозначим область ее определения. Чтобы указать, что f не определена
на некотором наборе чисел a1,..., an будем писать $$f(a_{1},\dots , a_{n})=\infty$$,
а если f на этом наборе определена, то будем писать $$f(a_{1},\dots , a_{n}) < \infty$$.
Таким образом, $$\delta _{f} =\{ (a_{1},\dots , a_{n}) | f(a_{1},\dots , a_{n}) < \infty \}$$.
Структурированные программы
В этом разделе рассмотрим в качестве средства описания алгоритмов структурированные
программы. Они вычисляют функции, используя минимальные средства:
элементарные присваивания, условные операторы и циклы.
Определим вначале синтаксис структурированных программ.
Зафиксируем для этого некоторое счетное множество имен переменных Var, которые
будут использоваться в программах. Как обычно, будем считать, что оно включает
имена x, x1,x2,..., y, y1,..., z,z1,... и т.п.
В последующих определениях x, y, z - это произвольные переменные из Var.
Определение 7.1. Оператор присваивания. Присваивание - это выражение одного из следующих трех видов:
x := x+1
x := 0
x := y.
Определение 7.2. Условия. Условие - это выражение одного из двух видов:
а) x = y или б) x < y.
Структурированные программы определяются индуктивно.
Определение 7.3. Структурированные программы.
Каждое присваивание - это структурированная программа.
Если $$\Pi _{1}$$ и $$\Pi _{2}$$ - структурированные программы, то и $$\Pi = \Pi _{1} ; \Pi _{2}$$ - это структурированная программа.
Если $$\Pi _{1}$$ и $$\Pi _{2}$$ - структурированные программы, а $$\Phi$$ - это условие, то
$$\Pi= \mbox{ если } \Phi \mbox{ то } \Pi_1 \mbox{ иначе } \Pi_2 \mbox{ конец }$$
является структурированной программой.
Если $$\Pi _{1}$$ - структурированная программа, а $$\Phi$$ - это условие, то
$$\Pi= \mbox{ пока } \Phi \mbox{ делай }\Pi_1$$
все является структурированной программой.
Других структурированных программ нет.
Конструкция в п. (б) называется последовательным применением или композицией программ $$\Pi _{1}$$ и $$\Pi _{2}$$, конструкция в п. (в)
называется условным оператором ; конструкция в п.
(г) - это оператор цикла, $$\Phi$$ - условие цикла, а $$\Pi _{1}$$ - тело цикла.
С помощью структурированных программ (далее называемых просто программами)
вычисляются (частичные) функции от натуральных аргументов, принимающие натуральные
значения. С каждой программой $$\Pi$$ свяжем естественным образом
множество входящих в нее переменных $$Var_{\Pi }$$
(определите это множество индукцией по построению программы).
В процессе работы программа изменяет значения этих переменных. Операционная семантика задает правила такого изменения.
Определение 7.4. Состояние - это отображение $$\sigma$$ из множества переменных Var во множество N.
Для $$x \in Var$$ через $$\sigma (x)$$ обозначим значение переменной x в состоянии $$\sigma.$$ Через S обозначим множество всех состояний.
Разумеется, при рассмотрении конкретной программы $$\Pi$$
нас будут интересовать значения переменных из $$Var_{\Pi }$$.
Определение 7.5. Операционная семантика программы $$\Pi$$ - это отбражение (вообще говоря, частичное) типа S -> S, которое программа $$\Pi$$ индуцирует на множестве всех состояний. Через $$\Pi (\sigma )$$ обозначим состояние - результат применения программы $$\Pi$$ к состоянию $$\sigma$$ .
Оно определяется индукцией по построению программы.
$$( x := x+1)(\sigma ) = \sigma _{1}$$, где $$\sigma _{1}(y)=\sigma (y)$$ при $$y \ne x$$, и $$\sigma _{1}(x)=\sigma (x)+1$$.
$$( x := 0)(\sigma ) = \sigma _{1}$$, где $$\sigma _{1}(y)=\sigma (y)$$ при $$y \ne x$$, и $$\sigma _{1}(x)=0$$.
$$( x := y)(\sigma ) = \sigma _{1}$$, где $$\sigma _{1}(z)=\sigma (z)$$ при $$z \ne x$$, и $$\sigma _{1}(x)=\sigma (y)$$
Пусть $$\Pi =\Pi _{1};\Pi _{2}$$. Тогда $$\Pi (\sigma )=(\Pi _{1};\Pi _{2})(\sigma )=\Pi _{2}(\Pi _{1}(\sigma ))$$, при этом, если $$\Pi _{1}(\sigma )=\infty$$ или $$\sigma _{1}=\Pi _{1}(\sigma )$$ и $$\Pi _{2}(\sigma _{1})=\infty$$, то и $$\Pi (\sigma )=\infty$$.
Пусть $$\Pi =$$ если x = y то $$\Pi _{1}$$ иначе $$\Pi _{2}$$ конец. Тогда
$$\Pi(\sigma)= \left\{\begin{array}{ll}
\Pi_1(\sigma), \textit{если}\ \Pi_1(\sigma)< \infty \ \textit{ и }\ \sigma(x)=\sigma(y)\\
\Pi_2(\sigma), \textit{если}\ \Pi_2(\sigma)< \infty \ \textit{ и }\ \sigma(x)\neq \sigma(y)\\
\infty \textit{в остальных случаях}
\end{array}
\right.$$
Пусть $$\Pi =$$ если x < y то $$\Pi _{1}$$ иначе $$\Pi _{2}$$ конец. Тогда
$$\Pi(\sigma)= \left\{\begin{array}{ll}
\Pi_1(\sigma), \textit{если}\ \Pi_1(\sigma)< \infty \ \textit{ и }\ \sigma(x)<\sigma(y)\\
\Pi_2(\sigma), \textit{если}\ \Pi_2(\sigma)< \infty \ \textit{ и }\ \sigma(x)\geq \sigma(y)\\
\infty \textit{в остальных случаях}
\end{array}
\right.$$
Пусть $$\Pi =$$ пока x = y делай $$\Pi _{1}$$ все. Тогда при $$\sigma (x) \ne \sigma (y)$$ $$\Pi (\sigma )= \sigma$$, а при $$\sigma (x) = \sigma (y) \Pi (\sigma )$$ - это первое такое состояние $$\sigma _{m}$$ в последовательности состояний $$\sigma _{0}=\sigma , \sigma _{1}=\Pi (\sigma _{0}),\dots , \sigma _{i+1}=\Pi (\sigma _{i}),..$$., что при i <= m все состояния $$\sigma _{i}$$ определены, при i <m имеет место $$\sigma _{i}(x) = \sigma _{i}(y)$$, и $$\sigma _{m}(x) \ne \sigma _{m}(y)$$.
Семантику для цикла с условием x < y определите самостоятельно (см. задачу 7.1).
Пусть $$\Pi$$ - программа, $$Var_{\Pi }$$ - множество ее переменных. Выделим среди эти переменных некоторое подмножество входных переменных x1,..., xn и одну результирующую (выходную) переменную y (она может быть одной из входных). Переменные из $$Var_{\Pi }$$, не являющиеся входными,
будем называть вспомогательными.
Определение 7.6.
Программа $$\Pi$$ с входными переменными x1,..., xn и результирующей переменной y вычисляет частичную функцию F: n -> ,
если для любого набора значений аргументов $$a_{1},\dots ,a_{n} (a_{i} \in )$$,
она переводит начальное состояние $$\sigma,$$ в котором $$\sigma (x_{i})=a_{i}$$ при 1<= i<= n и $$\sigma (z) = 0$$ при $$z \in Var \setminus \{ x_{1},\dots ,x_{n}\}$$,
в состояние $$\sigma _{1}=\Pi (\sigma )$$ тогда и только тогда, когда $$(a_{1},\dots , a_{n}) \in delta_{F}$$ и $$F(a_{1},\dots , a_{n})= \sigma _{1}(y)$$.
Функцию, вычисляемую программой $$\Pi$$ с входными переменными x1,..., xn в (результирующей) переменной y, обозначим $$\Phi _{\Pi ,y}(x_{1}, \dots , x_{n})$$.
Арифметическая функция F(x1, ..., xn) программно вычислима, если
она вычислима некоторой программой $$\Pi$$ в некоторой переменной y
при некотором разбиении переменных $$Var_{\Pi }$$ на входные: x1,..., xn
и вспомогательные.
Заметим, что в нашем языке нет понятия процедуры (подпрограммы).
Для сокращения записи мы будем иногда использовать имя одной
ранее написанной программы внутри текста другой: $$\Pi = \dots \Pi _{1} ..$$. Такая запись будет означать текстовую (in-line) подстановку текста (кода) программы $$\Pi _{1}$$ в соответствующее место программы $$\Pi.$$
Подчеркнем, что при этом переменные $$\Pi _{1}$$ не переименовываются и программист сам должен заботиться о правильной инициализации переменных из $$Var_{\Pi 1}$$.
Например, если $$\Pi$$ использует отдельно написанную программу $$\Pi _{+}$$
из приведенного ниже примера 7.3 для сложения переменных a и b и получения результата в t, то "безопасный" и корректный способ
сделать это может выглядеть так:
$$\Pi: \ldots; x':=x; y':=y; z':=z; x:=a; y:=b;\Pi_+; t:=x; \\ x:=x'; y:=y'; z:=z'; \ldots$$
т.е. вначале сохраняются текущие значения переменных x,y,z,
используемых в $$\Pi _{+}$$, затем входным переменным x и y присваиваются
нужные значения a и b и вызывается $$\Pi _{+}$$, ее результат передается в t,
затем восстанавливаются значения x,y,z.
Рассмотрим несколько примеров программ.
Пример 7.1.
$$\Pi _{0}: x := 0$$
Ясно, что $$\Phi _{\Pi 0,x} (x)$$ тождественно равна 0.
Пример 7.2.
$$\Pi _{1}: x := x+1$$
А здесь $$\Phi _{\Pi 1,x}(x)= x+1$$ для любого x.
Пример 7.3.
$$\Pi _{+}: пока \ z < y \ делай \ z:=z+1; x := x+1 \ все$$
Зафиксируем входные переменные x, y и выходную переменную x
( z - рабочая переменная ). Легко показать, что $$\Phi _{\Pi +,x}(x,y)= x+y$$.
Действительно, при y=0 тело цикла не выполняется и выход равен x=x+0. При y >= 1 тело цикла выполняется y раз и при каждом его выполнении x увеличивается на 1.
Пример 7.4.
$$\Pi_4(n,i):\\
x_1 := x_1;\ldots ; x_n:= x_n; x_1:= x_i$$
$$\Pi _{4}(n,i)$$ вычисляет в x1 функцию
выбора i-го аргумента: $$\Phi_{\Pi 4}(n,i), x_1(x_1, ... , x_n)= x_i$$.
Пример 7.5.
$$\Pi_5(n):\\
x_1 := x_1;\ldots ; x_n:= x_n; \mbox{пока}\ x_1=x_1\ \mbox{делай}\ x_1:=x_1 \mbox{все}$$
Нетрудно понять, что $$\Pi _{5}(n)$$ вычисляет нигде не определенную
функцию от n переменных: $$\Phi_{\Pi 5}(n), x_1(x_1, ... , x_n)= \infty$$.
Задачи
Задача 7.1.
Определите (по аналогии с п. (ж)) определения 7.5 семантику для программ вида
$$\Pi =$$ пока x < y делай $$\Pi _{1}$$ все.
Задача 7.2.Построить структурированные программы, вычисляющие
в z следующие функции, и доказать их корректность:
f{x}(x,y)= x*y;
ffact(x)= x!;
f-1(x)= x $$dot{-}$$ 1, где 0 $$dot{-}$$ 1 = 0 и (x+1) $$dot{-}$$ 1 = x ;
f-(x,y)= x $$dot{-}$$ y, где x $$dot{-}$$ y = x-y, если x >= y и x $$dot{-}$$ y=0, если x < y ;
fsqr(x)= [sqrt x];
fexp(x)= 2x;
flog(x)= [log2x];
f/(x,y)= [x/y].
Задача 7.3.
Пусть $$\Pi$$ - структурированная программа и $$|Var_{\Pi }| = m$$. Из определений
следует, что при различной фиксации входных переменных и выходной переменной
программа может вычислять различные функции.
Каково максимальное число функций от n <= m переменных, которое может вычислять $$\Pi?$$ Сколько всего разных функций может вычислить $$\Pi?$$
Постройте программу $$\Pi (m,n)$$, которая вычисляет максимальное число различных функций от n <= m переменных.
Постройте программу $$\Pi (m)$$ с $$|Var_{\Pi }| = m$$, которая для каждого n <= m вычисляет максимальное число различных функций от n переменных.
Задача 7.4.Построить структурированные программы, вычисляющие
в z следующие функции:
$$\begin{array}{lll}
f_1(x, y) = \left \{\begin{array}{ll}
x^2y^3, \text{ если $x < y$ } \\
\text{}
[ (x+y)/2 ] , \text{ в противном случае}
\end{array} \right. \\
\end{array}$$
$$\begin{array}{lll}
f_2(x, y) = \left \{\begin{array}{ll}
3^y, \text{ если $\log_2 (x+1) \geq y$ }\\
|x -y|, \mbox{ в противном случае}
\end{array} \right.\\
\end{array}$$
$$\begin{array}{lll}
f_3(x, y) = \left \{\begin{array}{ll}
[x*y/2], \text{ если $\log_2 x \leq y+2$ }\\
x^{[y/2], \mbox{ в противном случае}
\end{array} \right. \\
\end{array}$$
$$\begin{array}{lll}
p(x) = \left \{\begin{array}{ll}
1, \ \ \ \mbox{ если $x$ --- простое число}\\
0, \ \ \ \mbox{ в противном случае}
\end{array} \right.
\end{array}$$
Задача 7.5.
Пусть структурированная программа $$\Pi$$ вычисляет в переменной y некоторую всюду определенную взаимно однозначную функцию f(x), область значений которой
совпадает с множеством всех натуральных чисел N. Пусть $$Var_{\Pi }=\{ x, y, z_{1},\dots , z_{m}\}$$.
Постройте структурированную программу, которая вычисляет
обратную функцию f-1(x) = { z | f(z)=x}.
Задача 7.6. Пусть F(x) задана соотношениями F(0)=1, F(1)=1, F(x+2)= F(x)+F(x+1) (элементы последовательности F(x) называются числами Фибоначчи). Постройте структурированную программу, которая вычисляет функцию F(x).
Что такое алгоритм?
Первоначальной целью теории алгоритмов является классификация всех задач на
алгоритмически разрешимые и неразрешимые, т.е. на те, для которых
существуют решающие их алгоритмы, и те, для которых таких алгоритмов нет.
Неформально под алгоритмом $$\mathcal{A}$$ можно понимать выраженный
в некотором языке набор правил (предписание, рецепт, способ),
позволяющий применить к исходным (входным) данным x из некоторого
множества допустимых данных X последовательность дискретных действий
(операций, команд), приводящую к определенному результату - выходным данным $$y= \mathcal{A(x)$$ из некоторого множества Y.
В этом случае говорят, что алгоритм $$\mathcal{A}$$ вычисляет функцию $$F(x)= \mathcal{A}(x)$$ типа X -> Y.
Это нестрогое определение вполне подходит в тех
случаях, когда для некоторой функции нам предъявляется "объект",
называемый алгоритмом ее вычисления (например, алгоритм Эвклида
для вычисления наибольшего общего делителя двух целых чисел),
и можно легко проверить, позволяет ли он действительно вычислить требуемую
функцию. Однако оно совершенно не годится для доказательства того, что
для заданной функции никакого алгоритма нет.
Начиная с тридцатых годов ХХ века, был предпринят ряд исследований для
формализации понятия алгоритма. Перечислим некоторые из предложенных
разными авторами в разное время формальных
моделей: машины Тьюринга-Поста, частично-рекурсивные функции (Гедель, Клини), $$\lambda$$ -исчисление (Черч, Клини), итеративные автоматы Неймана,
нормальные алгорифмы Маркова,
счетчиковые автоматы Минского, автоматы на графах Колмогорова-Барздиня и др.
Заложенные в них идеи в значительной степени повлияли затем на архитектуру и
языки программирования реальных компьютеров (например, на базе $$\lambda$$ -исчисления
построен широко применяемый в задачах искусственного интеллекта язык ЛИСП,
а из нормальных алгорифмов Маркова произошел хорошо подходящий для
текстовой обработки язык РЕФАЛ). Каждый из многочисленных языков
программирования также
задает некоторую формальную модель алгоритмов. Мы вначале рассмотрим один из
простейших таких языков - простые структурированные программы.
А затем сравним их с двумя
другими моделями алгоритмов: описаниями частично рекурсивных функций и машинами Тьюринга.
Хотя алгоритмы в разных прикладных областях имеют дело с дискретными
объектами различных видов: целыми и рациональными числами, строками,
формулами, разного рода выражениями, графами, матрицами, таблицами,
точечными изображениями и др., мы в этой части курса будем
рассматривать только задачи вычисления
функций от натуральных аргументов, принимающих натуральные
значения. Такие функции часто называют арифметическими.
Дело в том, что для любого естественного множества
дискретных объектов (в частности, для всех перечисленных выше) имеется
простое кодирование его элементов целыми числами. Поэтому задачи
вычисления функций на этих множествах превращаются в задачи вычисления арифметических функций.
Напомним, что через N обозначается
множество натуральных чисел, т.е. N={0,1,2,...}.
Для частичной n - местной арифметической функции f: Nn -> N через $$\Delta _{f}$$ обозначим область ее определения. Чтобы указать, что f не определена
на некотором наборе чисел a1,..., an будем писать $$f(a_{1},\dots , a_{n})=\infty$$,
а если f на этом наборе определена, то будем писать $$f(a_{1},\dots , a_{n}) < \infty$$.
Таким образом, $$\delta _{f} =\{ (a_{1},\dots , a_{n}) | f(a_{1},\dots , a_{n}) < \infty \}$$.
Структурированные программы
В этом разделе рассмотрим в качестве средства описания алгоритмов структурированные
программы. Они вычисляют функции, используя минимальные средства:
элементарные присваивания, условные операторы и циклы.
Определим вначале синтаксис структурированных программ.
Зафиксируем для этого некоторое счетное множество имен переменных Var, которые
будут использоваться в программах. Как обычно, будем считать, что оно включает
имена x, x1,x2,..., y, y1,..., z,z1,... и т.п.
В последующих определениях x, y, z - это произвольные переменные из Var.
Определение 7.1. Оператор присваивания. Присваивание - это выражение одного из следующих трех видов:
x := x+1
x := 0
x := y.
Определение 7.2. Условия. Условие - это выражение одного из двух видов:
а) x = y или б) x < y.
Структурированные программы определяются индуктивно.
Определение 7.3. Структурированные программы.
Каждое присваивание - это структурированная программа.
Если $$\Pi _{1}$$ и $$\Pi _{2}$$ - структурированные программы, то и $$\Pi = \Pi _{1} ; \Pi _{2}$$ - это структурированная программа.
Если $$\Pi _{1}$$ и $$\Pi _{2}$$ - структурированные программы, а $$\Phi$$ - это условие, то
$$\Pi= \mbox{ если } \Phi \mbox{ то } \Pi_1 \mbox{ иначе } \Pi_2 \mbox{ конец }$$
является структурированной программой.
Если $$\Pi _{1}$$ - структурированная программа, а $$\Phi$$ - это условие, то
$$\Pi= \mbox{ пока } \Phi \mbox{ делай }\Pi_1$$
все является структурированной программой.
Других структурированных программ нет.
Конструкция в п. (б) называется последовательным применением или композицией программ $$\Pi _{1}$$ и $$\Pi _{2}$$, конструкция в п. (в)
называется условным оператором ; конструкция в п.
(г) - это оператор цикла, $$\Phi$$ - условие цикла, а $$\Pi _{1}$$ - тело цикла.
С помощью структурированных программ (далее называемых просто программами)
вычисляются (частичные) функции от натуральных аргументов, принимающие натуральные
значения. С каждой программой $$\Pi$$ свяжем естественным образом
множество входящих в нее переменных $$Var_{\Pi }$$
(определите это множество индукцией по построению программы).
В процессе работы программа изменяет значения этих переменных. Операционная семантика задает правила такого изменения.
Определение 7.4. Состояние - это отображение $$\sigma$$ из множества переменных Var во множество N.
Для $$x \in Var$$ через $$\sigma (x)$$ обозначим значение переменной x в состоянии $$\sigma.$$ Через S обозначим множество всех состояний.
Разумеется, при рассмотрении конкретной программы $$\Pi$$
нас будут интересовать значения переменных из $$Var_{\Pi }$$.
Определение 7.5. Операционная семантика программы $$\Pi$$ - это отбражение (вообще говоря, частичное) типа S -> S, которое программа $$\Pi$$ индуцирует на множестве всех состояний. Через $$\Pi (\sigma )$$ обозначим состояние - результат применения программы $$\Pi$$ к состоянию $$\sigma$$ .
Оно определяется индукцией по построению программы.
$$( x := x+1)(\sigma ) = \sigma _{1}$$, где $$\sigma _{1}(y)=\sigma (y)$$ при $$y \ne x$$, и $$\sigma _{1}(x)=\sigma (x)+1$$.
$$( x := 0)(\sigma ) = \sigma _{1}$$, где $$\sigma _{1}(y)=\sigma (y)$$ при $$y \ne x$$, и $$\sigma _{1}(x)=0$$.
$$( x := y)(\sigma ) = \sigma _{1}$$, где $$\sigma _{1}(z)=\sigma (z)$$ при $$z \ne x$$, и $$\sigma _{1}(x)=\sigma (y)$$
Пусть $$\Pi =\Pi _{1};\Pi _{2}$$. Тогда $$\Pi (\sigma )=(\Pi _{1};\Pi _{2})(\sigma )=\Pi _{2}(\Pi _{1}(\sigma ))$$, при этом, если $$\Pi _{1}(\sigma )=\infty$$ или $$\sigma _{1}=\Pi _{1}(\sigma )$$ и $$\Pi _{2}(\sigma _{1})=\infty$$, то и $$\Pi (\sigma )=\infty$$.
Пусть $$\Pi =$$ если x = y то $$\Pi _{1}$$ иначе $$\Pi _{2}$$ конец. Тогда
$$\Pi(\sigma)= \left\{\begin{array}{ll}
\Pi_1(\sigma), \textit{если}\ \Pi_1(\sigma)< \infty \ \textit{ и }\ \sigma(x)=\sigma(y)\\
\Pi_2(\sigma), \textit{если}\ \Pi_2(\sigma)< \infty \ \textit{ и }\ \sigma(x)\neq \sigma(y)\\
\infty \textit{в остальных случаях}
\end{array}
\right.$$
Пусть $$\Pi =$$ если x < y то $$\Pi _{1}$$ иначе $$\Pi _{2}$$ конец. Тогда
$$\Pi(\sigma)= \left\{\begin{array}{ll}
\Pi_1(\sigma), \textit{если}\ \Pi_1(\sigma)< \infty \ \textit{ и }\ \sigma(x)<\sigma(y)\\
\Pi_2(\sigma), \textit{если}\ \Pi_2(\sigma)< \infty \ \textit{ и }\ \sigma(x)\geq \sigma(y)\\
\infty \textit{в остальных случаях}
\end{array}
\right.$$
Пусть $$\Pi =$$ пока x = y делай $$\Pi _{1}$$ все. Тогда при $$\sigma (x) \ne \sigma (y)$$ $$\Pi (\sigma )= \sigma$$, а при $$\sigma (x) = \sigma (y) \Pi (\sigma )$$ - это первое такое состояние $$\sigma _{m}$$ в последовательности состояний $$\sigma _{0}=\sigma , \sigma _{1}=\Pi (\sigma _{0}),\dots , \sigma _{i+1}=\Pi (\sigma _{i}),..$$., что при i <= m все состояния $$\sigma _{i}$$ определены, при i <m имеет место $$\sigma _{i}(x) = \sigma _{i}(y)$$, и $$\sigma _{m}(x) \ne \sigma _{m}(y)$$.
Семантику для цикла с условием x < y определите самостоятельно (см. задачу 7.1).
Пусть $$\Pi$$ - программа, $$Var_{\Pi }$$ - множество ее переменных. Выделим среди эти переменных некоторое подмножество входных переменных x1,..., xn и одну результирующую (выходную) переменную y (она может быть одной из входных). Переменные из $$Var_{\Pi }$$, не являющиеся входными,
будем называть вспомогательными.
Определение 7.6.
Программа $$\Pi$$ с входными переменными x1,..., xn и результирующей переменной y вычисляет частичную функцию F: n -> ,
если для любого набора значений аргументов $$a_{1},\dots ,a_{n} (a_{i} \in )$$,
она переводит начальное состояние $$\sigma,$$ в котором $$\sigma (x_{i})=a_{i}$$ при 1<= i<= n и $$\sigma (z) = 0$$ при $$z \in Var \setminus \{ x_{1},\dots ,x_{n}\}$$,
в состояние $$\sigma _{1}=\Pi (\sigma )$$ тогда и только тогда, когда $$(a_{1},\dots , a_{n}) \in delta_{F}$$ и $$F(a_{1},\dots , a_{n})= \sigma _{1}(y)$$.
Функцию, вычисляемую программой $$\Pi$$ с входными переменными x1,..., xn в (результирующей) переменной y, обозначим $$\Phi _{\Pi ,y}(x_{1}, \dots , x_{n})$$.
Арифметическая функция F(x1, ..., xn) программно вычислима, если
она вычислима некоторой программой $$\Pi$$ в некоторой переменной y
при некотором разбиении переменных $$Var_{\Pi }$$ на входные: x1,..., xn
и вспомогательные.
Заметим, что в нашем языке нет понятия процедуры (подпрограммы).
Для сокращения записи мы будем иногда использовать имя одной
ранее написанной программы внутри текста другой: $$\Pi = \dots \Pi _{1} ..$$. Такая запись будет означать текстовую (in-line) подстановку текста (кода) программы $$\Pi _{1}$$ в соответствующее место программы $$\Pi.$$
Подчеркнем, что при этом переменные $$\Pi _{1}$$ не переименовываются и программист сам должен заботиться о правильной инициализации переменных из $$Var_{\Pi 1}$$.
Например, если $$\Pi$$ использует отдельно написанную программу $$\Pi _{+}$$
из приведенного ниже примера 7.3 для сложения переменных a и b и получения результата в t, то "безопасный" и корректный способ
сделать это может выглядеть так:
$$\Pi: \ldots; x':=x; y':=y; z':=z; x:=a; y:=b;\Pi_+; t:=x; \\ x:=x'; y:=y'; z:=z'; \ldots$$
т.е. вначале сохраняются текущие значения переменных x,y,z,
используемых в $$\Pi _{+}$$, затем входным переменным x и y присваиваются
нужные значения a и b и вызывается $$\Pi _{+}$$, ее результат передается в t,
затем восстанавливаются значения x,y,z.
Рассмотрим несколько примеров программ.
Пример 7.1.
$$\Pi _{0}: x := 0$$
Ясно, что $$\Phi _{\Pi 0,x} (x)$$ тождественно равна 0.
Пример 7.2.
$$\Pi _{1}: x := x+1$$
А здесь $$\Phi _{\Pi 1,x}(x)= x+1$$ для любого x.
Пример 7.3.
$$\Pi _{+}: пока \ z < y \ делай \ z:=z+1; x := x+1 \ все$$
Зафиксируем входные переменные x, y и выходную переменную x
( z - рабочая переменная ). Легко показать, что $$\Phi _{\Pi +,x}(x,y)= x+y$$.
Действительно, при y=0 тело цикла не выполняется и выход равен x=x+0. При y >= 1 тело цикла выполняется y раз и при каждом его выполнении x увеличивается на 1.
Пример 7.4.
$$\Pi_4(n,i):\\
x_1 := x_1;\ldots ; x_n:= x_n; x_1:= x_i$$
$$\Pi _{4}(n,i)$$ вычисляет в x1 функцию
выбора i-го аргумента: $$\Phi_{\Pi 4}(n,i), x_1(x_1, ... , x_n)= x_i$$.
Пример 7.5.
$$\Pi_5(n):\\
x_1 := x_1;\ldots ; x_n:= x_n; \mbox{пока}\ x_1=x_1\ \mbox{делай}\ x_1:=x_1 \mbox{все}$$
Нетрудно понять, что $$\Pi _{5}(n)$$ вычисляет нигде не определенную
функцию от n переменных: $$\Phi_{\Pi 5}(n), x_1(x_1, ... , x_n)= \infty$$.
Задачи
Задача 7.1.
Определите (по аналогии с п. (ж)) определения 7.5 семантику для программ вида
$$\Pi =$$ пока x < y делай $$\Pi _{1}$$ все.
Задача 7.2.Построить структурированные программы, вычисляющие
в z следующие функции, и доказать их корректность:
f{x}(x,y)= x*y;
ffact(x)= x!;
f-1(x)= x $$dot{-}$$ 1, где 0 $$dot{-}$$ 1 = 0 и (x+1) $$dot{-}$$ 1 = x ;
f-(x,y)= x $$dot{-}$$ y, где x $$dot{-}$$ y = x-y, если x >= y и x $$dot{-}$$ y=0, если x < y ;
fsqr(x)= [sqrt x];
fexp(x)= 2x;
flog(x)= [log2x];
f/(x,y)= [x/y].
Задача 7.3.
Пусть $$\Pi$$ - структурированная программа и $$|Var_{\Pi }| = m$$. Из определений
следует, что при различной фиксации входных переменных и выходной переменной
программа может вычислять различные функции.
Каково максимальное число функций от n <= m переменных, которое может вычислять $$\Pi?$$ Сколько всего разных функций может вычислить $$\Pi?$$
Постройте программу $$\Pi (m,n)$$, которая вычисляет максимальное число различных функций от n <= m переменных.
Постройте программу $$\Pi (m)$$ с $$|Var_{\Pi }| = m$$, которая для каждого n <= m вычисляет максимальное число различных функций от n переменных.
Задача 7.4.Построить структурированные программы, вычисляющие
в z следующие функции:
$$\begin{array}{lll}
f_1(x, y) = \left \{\begin{array}{ll}
x^2y^3, \text{ если $x < y$ } \\
\text{}
[ (x+y)/2 ] , \text{ в противном случае}
\end{array} \right. \\
\end{array}$$
$$\begin{array}{lll}
f_2(x, y) = \left \{\begin{array}{ll}
3^y, \text{ если $\log_2 (x+1) \geq y$ }\\
|x -y|, \mbox{ в противном случае}
\end{array} \right.\\
\end{array}$$
$$\begin{array}{lll}
f_3(x, y) = \left \{\begin{array}{ll}
[x*y/2], \text{ если $\log_2 x \leq y+2$ }\\
x^{[y/2], \mbox{ в противном случае}
\end{array} \right. \\
\end{array}$$
$$\begin{array}{lll}
p(x) = \left \{\begin{array}{ll}
1, \ \ \ \mbox{ если $x$ --- простое число}\\
0, \ \ \ \mbox{ в противном случае}
\end{array} \right.
\end{array}$$
Задача 7.5.
Пусть структурированная программа $$\Pi$$ вычисляет в переменной y некоторую всюду определенную взаимно однозначную функцию f(x), область значений которой
совпадает с множеством всех натуральных чисел N. Пусть $$Var_{\Pi }=\{ x, y, z_{1},\dots , z_{m}\}$$.
Постройте структурированную программу, которая вычисляет
обратную функцию f-1(x) = { z | f(z)=x}.
Задача 7.6. Пусть F(x) задана соотношениями F(0)=1, F(1)=1, F(x+2)= F(x)+F(x+1) (элементы последовательности F(x) называются числами Фибоначчи). Постройте структурированную программу, которая вычисляет функцию F(x).
