0.1. Программа как формализованное описание процесса обработки данных
Целью программирования является описание процессов обработки данных (в дальнейшем - просто процессов). Данные - это представление фактов и идей в формализованном виде, пригодном для передачи и переработке в некоем процессе, а информация - это смысл, который придается данным при их представлении. Обработка данных - это выполнение систематической последовательности действий с данными. Данные представляются и хранятся на носителях данных. Совокупность носителей данных, используемых при какой-либо обработке данных, будем называть информационной средой. Набор данных, содержащихся в какой-либо момент в информационной среде, будем называть состоянием этой информационной среды. Процесс можно определить как последовательность сменяющих друг друга состояний некоторой информационной среды.
Описать процесс - значит определить последовательность состояний заданной информационной среды. Если мы хотим, чтобы по заданному описанию требуемый процесс порождался автоматически на компьютере, необходимо, чтобы это описание было формализованным. Такое описание называется программой. С другой стороны, программа должна быть понятной и человеку, так как и при разработке программ, и при их использовании часто приходится выяснять, какой именно процесс она порождает. Поэтому программа составляется на понятном человеку формализованном языке программирования, с которого она автоматически переводится на язык соответствующего компьютера с помощью другой программы, называемой транслятором. Программисту, прежде чем составить программу, приходится проделывать большую подготовительную работу по уточнению постановки задачи, выбору метода ее решения, выяснению специфики применения требуемой программы, прояснению общей организации разрабатываемой программы и многое другое.
0.2. Правильная программа и надежная программа 
Под «программой» часто понимают правильную программу, т.е. программу, не содержащую ошибок, соответствующую спецификации и дающую возможность формального вывода программы из формального набора предпосылок. Однако понятие ошибки в программе трактуется программистами неоднозначно. Будем считать, что в программе имеется ошибка, если она не выполняет того, что разумно ожидать от нее на основании документации по применению программы. Следовательно, правильнее говорить о несогласованности между программами и документацией по их применению.
В связи с тем, что задание на программу обычно формулируется не формально, а также из-за неформализованности понятия ошибки в программе, нельзя доказать формальными методами (математически) правильность программы. Нельзя доказать правильность программы и тестированием: как указал Дейкстра, тестирование может лишь продемонстрировать наличие в программе ошибки. 
Альтернативой правильной программы является надежная программа. Надежность программы - это ее способность безотказно выполнять определенные функции при заданных условиях в течение заданного периода времени с достаточно большой вероятностью. При этом под отказом в программе понимают проявление в нем ошибки. Таким образом, надежная программа не исключает наличия в ней ошибок - важно лишь, чтобы эти ошибки при практическом применении этой программы в заданных условиях проявлялись достаточно редко. Убедиться, что программа обладает таким свойством можно при его испытании путем тестирования, а также при практическом применении. Таким образом, фактически мы можем разрабатывать лишь надежные, а не правильные программы.
Разрабатываемая программа может обладать различной степенью надежности. Как измерять эту степень? Так же как в технике, степень надежности можно характеризовать вероятностью работы программы без отказа в течение определенного периода времени. Однако в силу специфических особенностей программ определение этой вероятности наталкивается на ряд трудностей по сравнению с решением этой задачи в технике.
При оценке степени надежности программ следует также учитывать последствия каждого отказа. Некоторые ошибки в программах могут вызывать лишь некоторые неудобства при его применении, тогда как другие ошибки могут иметь катастрофические последствия, например, угрожать человеческой жизни. Поэтому для оценки надежности программных средств иногда используют дополнительные  показатели, учитывающие стоимость (вред) для пользователя каждого отказа.
1. Схемы программ
1.1. Краткое математическое предисловие
1.1.1. Функции и графы
Ведем некоторые соглашения об обозначениях элементов теории множеств и логики.
Множество – есть набор несовпадающих объектов, которые мы будем задавать явным перечислением, и заключать в фигурные скобки. Например: D - множество дней недели: 
D = { Пн, Вт, Ср, Чт, Пт, Сб, Вс }, D1 = { Вт, Ср, Чт, Пн, Сб, Пт, Вс }. 
D и D1 эквивалентны, т.е. порядок элементов не важен.
Будем использовать обозначения:
x  A - x есть элемент и принадлежит множеству A; x  A - x не является элементом множества А.
Для бесконечных множеств метод перечисления элементов множества не применим, для этого используется характеристическое свойство А = {x | p(x)}, где х – переменная, значениями которой являются некоторые объекты, а р – свойство тех и только тех значений х, которые являются элементами задаваемого множества.
Пустое множество - множество, которое не содержит ни одного элемента, обозначается Ø или {}.
Если каждый элемент множества А является элементом множества В, то множество А является подмножеством множества В, будем писать A  B.
Если хотя бы один элемент множества А не является элементом множества В, то множество А не является подмножеством множества В и это записывается А  В.
Декартовым произведением А1  А2  …  Аn множеств А1, А2 … и Аn называется множество    {(a1, a2, …, an) | a1  A1, a2  A2,    , an  An}, а An обозначает А  А  …  А (n раз).
Функцией, отображающей множество Х во множество Y (обозначение F: X → Y), называется множество F  XY такое, что для любых пар (x, y)F и (x’ y’) F из x = x’ следует, что y = y’.
Множество {x | (x, y)  F} – область определения функции F (или множество значений ее аргумента); множество {y | (x, y)  F} – область значений функции F.
Функцию F: X → Y называют n-местной функцией над множеством А, если Y = A и X = An.
Предикатом называют функцию, областью значений которой является множество символов-цифр {0, 1}. При этом говорят, что предикат P: X → {0, 1} истинен для x  X, если P(x) = 1, и ложен, если     P(x) = 0. Отношение на множестве Х – это двухместный предикат P: X2 → {0, 1}.
Алфавитом называют непустое конечное множество символов. Например, V1 = {a, b}, V2 = {0, 1}, V3 = {a, +, 1, =} – алфавиты. Словом в алфавите V называется конечный объект, получаемый выписыванием одного за другим символов V, например, а + 1 = 1 + а – слово в алфавите V3, 101011 – слово в алфавите V2, abaab – слово в алфавите V1. Длина слова – число символов в нем, пустое слово не содержит ни одного символа.
Множество всех слов в алфавите V обозначается V*. 
n-местной словарной функцией над алфавитом V называют n-местную функцию над V*, т. е. функцию из V*  V*  …  V* (n раз) в V*.
Направленным графом называется тройка G = (V, E, Ф), где V - множество вершин, Е – множество дуг, а Ф – функция из Е в (V{ω})2 , ω  V. Дуга е называется входом графа, если Ф(е) = (, ), для             V{ω}; внутренней, если Ф(е) = (1, 2) для 1,2  V; выходом, если Ф(е) = (,), для   V{ω}. Дуга е, являющаяся одновременно и входом и выходом графа, называется висячей; для нее Ф(е) = (, ω). Дуги, не являющиеся внутренними, называются также свободными.
Говорят, что дуга е инцидентна вершине , если е выходит из  или ведет в . Две дуги смежны, если существует хотя бы одна инцидентная им обеим вершина. Вершина  называется наследником вершины ’, если в графе имеется хотя бы одна такая дуга, что Ф(е) = (’, ).
Рисунок 1.1.
Изображенный на рисунке 1.1 граф G1 содержит 4 вершины, 8 дуг. Дуга е1 – входная, дуга е6 – выходная, дуга е8 – висячая, остальные дуги внутренние; вершины 1 и 3 наследники вершины 1.
Путем в графе G называется последовательность …ieii+1… дуг и вершин, такая, что для всех i Ф(еi) = (i,i+1). Образом пути называется слово, составленное из пометок проходимых дуг и вершин.
Две вершины 1,2 графа G называются связанными, если 1 = 2 или существует маршрут е1, …,еn графа G такой, что дуга е1 инцидентна вершине 1, а дуга еn – вершине 2.
1.1.2. Вычислимость и разрешимость
Данное в п. 1.1.1. определение функции не содержит указаний о том, как для заданных значений аргументов получить соответствующие значения функции. Было бы практичнее переформулировать это определение таким образом, чтобы оно содержало конструктивную процедуру, или алгоритм, нахождения значений функции. Однако такое определение уже приведенного выше, т. е. определяет лишь некоторый подкласс функций, которые называют вычислимыми функциями. 
Тьюринг в середине 30-х годов формализовал способ получения значений вычислимой функции с помощью абстрактной «математической машины», вычисляющей значения функции по значениям ее аргументов. Конкретная машина Тьюринга задает конкретную вычислимую функцию и его гипотеза (тезис) состояла в том, что каждая функция, для которой существует алгоритм нахождения ее значений, представима некоторой машиной Тьюринга, т. е. является вычислимой. Тезис Тьюринга не может быть доказан, так как наряду с формальным понятием вычислимой функции он содержит эмпирическое понятие алгоритма. Однако интуиция, отсутствие опровергающих примеров и равносильность различных формализаций вычислимости убеждают в справедливости этого тезиса.
Машина Тьюринга Т задает словарную функцию над некоторым алфавитом V и представляет собой описание машины — набор (F, Q, q0, #, I) - и правило функционирования, общее для всех машин, где
V — алфавит машины;
Q — конечное непустое множество символов, называемых состояниями машины (Q  V =);
q0 — выделенный элемент множества Q, называемый начальным состоянием;
# — специальный «пустой» символ, не принадлежащий ни V, ни Q;
I — программа машины.
Программа машины — это конечное множество слов вида qa  q'a’d, называемых командами, где          q, q'  Q, a, a'  V  {#};  — вспомогательный символ-разделитель; d — элемент множества {l, r, р}, содержащего три специальных символа, которых нет ни в V, ни в Q. Предполагается также, что в программе I никакие две команды не могут иметь одинаковую пару первых двух символов.
Правило функционирования поясним неформально на распространенной «физической» модели машины Тьюринга. Машина состоит из потенциально бесконечной (в обе стороны) ленты, управления и головки, перемещаемой вдоль ленты (см. рисунок). Лента разбита на клетки, которые могут содержать символы из алфавита V или быть пустыми, т. е. содержать символ #. Управление на каждом шаге работы машины находится в одном из состояний из Q, расшифровывает программу, которая однозначно определяет поведение машины и управляет головкой. Головка в каждый момент расположена против некоторой клетки ленты и может считывать символы с ленты, записывать их на ленту и перемещаться в обе стороны вдоль ленты. Машина функционирует следующим образом. В начальный момент на ленте записано некоторое слово из V, а управление находится в начальном состоянии q0. Начальное слово, равно как и слова, появляющиеся в процессе работы машины, ограничено с двух сторон пустыми символами #. Головка обозревает крайний слева символ заданного слова.
Работа машины состоит в повторении следующего цикла элементарных действий:
1) считывание символа, находящегося против  головки;
2) поиск применимой команды, а именно той команды qa  q'a'd, в которой q — текущее состояние управления, а — считанный символ;
3) выполнение найденной команды, состоящее в переводе управления в новое состояние q', записи в обозреваемую головкой клетку символа а' (вместо стираемого символа а) и последующем перемещении головки вправо, если d = r, влево, если d = I, или сохранении ее в том же положении, если d = р.
Машина останавливается в том и только в том случае, если на очередном шаге ни одна из команд не применима. Результат работы остановившейся машины — заключительное слово на ленте.
Машина Тьюринга, перерабатывая начальные слова на ленте в заключительные, задает словарную функцию, для которой начальные слова - значения аргумента, заключительные - значения функции. (Для представления n-местной функции начальное слово на ленте имеет вид #a1 #a2 # … #an #, где подслова a1, a2,…, an не содержат символа #. При интерпретации заключительного слова на ленте как значения функции символ # игнорируется). Если машина не останавливается, начав работу с некоторым словом на ленте, то функция, задаваемая машиной, считается неопределенной для этого слова. Таким образом, машина Тьюринга Т задает частичную функцию FT и способ вычисления ее значений. Хотя машины Тьюринга оперируют со словами, они могут задавать и числовые функции в силу установленной выше связи между словами и числами.
По определению, функция F является (частично) вычислимой, если существует машина Тьюринга Т такая, что FT = F. Говорят также, что для функции F существует (частичный) алгоритм вычисления ее значений, задаваемый машиной Т.
Для машины Тьюринга, как и для всех других формальных способов задания алгоритмов, включая программы для ЭВМ, характерны следующие свойства:
1) конструктивность — машина Тьюринга представляет собой конечный объект, построенный по определенным правилам из базовых объектов;
2) конечность — процесс нахождения значений функции для тех значений аргументов, для которых она определена, состоит из конечного числа шагов;
3) однозначность — результат работы машины единственным образом определяется начальным словом;
4) массовость — машина работает с любым начальным словом на ленте, составленным из символов ее алфавита.
Машина Тьюринга однозначно задается своей программой. Если упорядочить ее команды и закодировать последовательность команд словом в алфавите машины Тьюринга, то можно получить ее описание в собственном алфавите. Заметим, что одной и той же машине Тьюринга соответствуют различные словарные представления в ее алфавите в зависимости от выбора упорядочений множеств Q, V, I, но по любому из этих представлений программа машины восстанавливается однозначно.
Изучая свойства программ и их математических абстракций – схем программ, мы ставим целью автоматизацию программирования, в том числе автоматический анализ свойств программ и их преобразования, осуществляемые с помощью других, специальных программ. Поэтому нас интересуют алгоритмы, которые могли бы по любой предъявленной программе установить, завершит ли она работу или будет «циклить», дают ли две программы, исходная и оптимизированная, один и тот же результат, является ли программа синтаксически правильной и т. д.
Массовые алгоритмические проблемы формулируются следующим образом. Необходимо указать алгоритм, который бы определял, обладает ли предъявленный объект из некоторого класса объектов интересующим нас свойством, принадлежит ли он множеству М всех объектов, обладающих этим свойством. Если существует такой частичный алгоритм, то говорят, что множество перечислимо, а поставленная массовая алгоритмическая проблема частично разрешима. Если этот алгоритм к тому же всюду определен, то множество М разрешимо и поставленная проблема также разрешима. Существуют неразрешимые проблемы и даже проблемы, которые не являются частично разрешимыми, что свидетельствует о существовании невычислимых функций.
Пусть V – алфавит, М  V – множество слов в V.
Характеристической функцией множества М называется предикат FM: V* → {0, 1}, всюду определенный на V*: FM (а) = 1, если а  М, и FM (а) = 0, если а  М.
Частичная характеристическая функция множества М – это функция НМ: V* → {1}, определенная только для слов из М и имеющая вид НM (а) = 1 для всех а  М.
Множество М называется разрешимым, если его характеристическая функция вычислима. Множество М перечислимо, если его частичная характеристическая функция вычислима. Разрешимость множества М означает, что существует всегда останавливающаяся (оканчивающая работу за конечное время) машина Тьюринга, позволяющая для любого слова в алфавите V через конечное число шагов установить, принадлежит ли это слово множеству М или нет. Перечислимость множества М означает, что существует машина Тьюринга, которая останавливается в том и только том случае, если предъявленное слово принадлежит множеству М.
Приведем без доказательства несколько важных теорем.
Теорема (Пост). Множество М  V* разрешимо тогда и только тогда, когда М и его дополнение     М’ = V*\M перечислимы. 
Машина Тьюринга, начав работу, или останавливается, или работает бесконечно. Проблема остановки формулируется так. Пусть М – множество всех пар слов в алфавите V, в каждой паре первое слово – словарное представление некоторой машины Тьюринга, второе – такое слово, что эта машина останавливается, начав работу над ним. Является ли множество М неразрешимым.
Теорема (Тьюринг). Проблема остановки машины Тьюринга неразрешима.
Последняя теорема демонстрирует существование невычислимых функций. Из тезиса Тьюринга следует, что для неразрешимых проблем нельзя построить алгоритм, который решал бы их, например, с помощью ЭВМ.
Проблема зацикливания состоит в следующем: существует ли алгоритм, хотя бы частный, который выясняет заранее для произвольной машины Тьюринга будет ли она работать бесконечно.
Теорема. Проблема зацикливания машины Тьюринга не является частично разрешимой.
1.1.3. Программы и схемы программ
Схемы программ - это математические модели программ, описывающие строение программы, или точнее строение множества программ, где конкретные операции и функции заменены абстрактными функциональными и предикатными символами. Следующий пример программ вычисления факториала n! и переворачивания слов поясняет различие между программами и их схемой S1.

begin integer x, y;			begin integer x, y;			begin
ввод(x);				ввод(x);				ввод(x);
	y:=1;					y:=ε;					y:=a;
L:	if  x=0 then goto L1;		L:	if  x=0 then goto L1;		L:	if p(x) then goto L1;
	y:=x*y;					y:=CONSCAR(x, y);			y:=g(x, y);
	x:=x-1;					x:=CDR(x);				x:=h(x);
	goto L;					goto L;					goto L;
L1:	вывод(y);			L1:	вывод(y);			L1:	вывод(y);
	end					end					end

Функция CONSCAR (суперпозиция функций CONS и CAR из языка Лисп) приписывает первую букву первого слова ко второму слову (т. е. CONSCAR(аб, в) = ав), а функция CAR стирает первую букву слова  (т. е. CAR(аб) = б).
1.2. Стандартные схемы программ
1.2.1. Базис класса стандартных схем программ
Стандартные схемы программ (ССП) характеризуются базисом и структурой схемы.
Базис класса фиксирует символы, из которых строятся схемы, указывает их роль (переменные, функциональные символы и др.), задает вид выражений и операторов схем.
Полный базис В класса стандартных схем состоит из 4-х непересекающихся, счетных множеств символов и множества операторов - слов, построенных из этих символов. 
Множества символов полного базиса:
1.	Х = x, х1, х2..., у, у1 у2..., z, z1, z2... - множество символов, называемых переменными;
2.	F = f(0), f(1), f(2)..., g(0), g(1), g(2)..., h(0), h(1), h(2)... - множество функциональных символов; верхний символ задает местность символа; нульместные символы называют константами и обозначают начальными буквами латинского алфавита a, b, c...;
3.	Р = р(0), р(1), р(2)...; q(0), q(1), q(2)...;  - множество предикатных символов; р(0), q(0) - ; нульместные символы называют логическими константами;
4.	start, stop, ...,:= и т. д. - множество специальных символов.
Термами (функциональными выражениями) называются слова, построенные из переменных, функциональных и специальных символов по следующим правилам:
1.	односимвольные слова, состоящие из переменных или констант, являются термами;
2.	слово τ вида f(n)(τ1, τ2...τn), где τ1, τ2...τn  - термы, является термом;
3.	те и только те слова, о которых говорится в п.п. 1,2, являются термами.
Примеры термов: х, f(0), а, f(1)(х), g(2)(x, h(3)(y, a)).
Тестами (логическими выражениями) называются логические константы и слова вида р(n)(τ1, τ2,...,τn). Примеры: p(0),  p(0)(х), g(3)(x, y, z),  p(2) (f(2(x, y)). Допускается в функциональных и логических выражениях опускать индексы местности, если это не приводит к двусмысленности или противоречию.
Множество операторов включает пять типов:
1.	начальный оператор - слово вида start(х1, х2...хк), где k ≥0, а х1, х2...хк - переменные, называемые результатом этого оператора;
2.	заключительный оператор - слово вида stop(τ1, τ2...τn), где n ≥0, а τ1, τ2...τn  - термы; вхождения переменных в термы τ называются аргументами этого оператора;
3.	оператор присваивания - слово вида х := τ, где х – переменная (результат оператора), а τ - терм; вхождения переменных в термы называются аргументами этого оператора;
4.	условный оператор (тест) - логическое выражение; вхождения переменных в логическое выражение называются аргументами этого оператора; 
5.	оператор петли - односимвольное слово loop.
Среди операторов присваивания выделим случаи: когда τ - переменная, то оператор называется пересылкой (х:=у) и когда τ -константа, то оператор называется засылкой (х:=а).
Подклассы используют ограниченные базисы. Так, например, подкласс У1 имеет базис: 
х1, х2, а, f(1), p(1), start, stop, (,),:=, ,и множество операторов start(х1, х2); х1:= f(x1), x2=f(x2), x1:=а, х2:= а, р(х1), р(х2), stop(х1,х2), т. е. схемы из этого подкласса используют две переменные, константу а, один одноместный функциональный символ, один предикатный символ и операторы указанного вида.
1.2.2. Графовая форма стандартной схемы
Представим стандартную схему программ как размеченный граф, вершинам которого приписаны операторы из некоторого базиса В.
Стандартной схемой  в базисе В называется конечный (размеченный ориентированный) граф без свободных дуг и с вершинами следующих пяти видов:
1.	Начальная вершина (ровно одна) помечена начальным о1ператором. Из нее выходит ровно одна дуга. Нет дуг, ведущих к начальной вершине.
2.	Заключительная вершина (может быть несколько). Помечена заключительным оператором. Из нее не выходит ни одной дуги.
3.	Вершина-преобразователь. Помечена оператором присваивания. Из нее выходит ровно одна дуга.
4.	Вершина-распознаватель. Помечена условным оператором (называемым условием данной вершины). Из нее выходит ровно две дуги, помеченные 1 (левая) и 0 (правая).
5.	Вершина-петля. Помечена оператором петли. Из нее не выходит ни одной дуги.
Конечное множество переменных схемы S составляют ее память ХS. 
Из определения следует, что один и тот же оператор может помечать несколько вершин схемы.
Вершины именуются (метки вершины) целым неотрицательным числом (0, 1, 2...). Начальная вершина всегда помечается меткой 0.
Схема S называется правильной, если на каждой дуге заданы все переменные.
Пример правильной ССП S1 в графовой форме приведен на рисунке 1.2, а.
Вершины изображены прямоугольниками, а вершина-распознаватель - овалом. Операторы записаны внутри вершины.
1.2.3. Линейная форма стандартной схемы
Для использования линейной формы СПП множество специальных символов расширим дополнительными символами :, goto, if, then, else. СПП в линейной форме представляет собой последовательность инструкций, которая строится следующим образом:
1.	если выходная дуга начальной вершины с оператором start(х1,..., хn) ведет к вершине с меткой L, то начальной вершине соответствует инструкция:
0: start(х1,..., хn) goto L;
2.	если вершина схемы S с меткой L - преобразователь с оператором присваивания х:=τ, выходная дуга которого ведет к вершине с меткой L1, то этому преобразователю соответствует инструкция: 
L: x: =τ goto L1;
3.	если вершина с меткой L - заключительная вершина с оператором stop(τ1,...τm), то ей соответствует инструкция
L: stop(τ1,..., τm);
4.	если вершина с меткой L - распознаватель с условием р(τ1,...τk), причем 1-дуга ведет к вершине с меткой L1, а 0-дуга - к вершине с меткой L0, то этому распознавателю соответствует инструкция 
L: if  р(τ1,...τk) then  L1 else L0;
5.	если вершина с меткой L - петля, то ей соответствует инструкция 
L: loop.
Обычно используется сокращенная запись (опускание меток). Полная и сокращенная линейные формы ССП (рисунок 1.2, а) приведены ниже
0:	start(х) goto 1,							start(х),
1:	у: = а goto 2,							у: = а,
2:	if  р(х) then 5 else 3,				2: 	if  р(х) then 5 else 3,
3:	у: = g(x,y) goto 4,						3: 	у: = g(x,y),
4:	х: = h(x) goto 2,							х: = h (x) goto 2,
5:	stop(у).						5:	stop(у).

x =0

x=ε

p(x)

а

б

Рисунок 1.2

start(x)

y:= a

y:=g(x,y)

x:= h(x)

stop(y)

1

start(x)

y:=1

stop(y)

y:=xy

x:=x-1

0

start(x)

y:=ε

stop(y)

y:=CONSCAR(x,y)

x:=CDR(x)

4

3

5

1

2

0

4

3

5

1

2

1

4

3

5

2

1

1.2.4. Интерпретация стандартных схем программ
ССП не является записью алгоритма, поэтому позволяет исследовать только структурные свойства программ, но не семантику вычислений. При построении «семантической» теории схем программ вводится понятие интерпретация ССП. Определим это понятие.
Пусть в некотором базисе В определен класс ССП. Интерпретацией базиса В в области интерпретации D называется функция I, которая сопоставляет:
1.	каждой переменной х из базиса В - некоторый элемент d = I(x) из области интерпретации D;
2.	каждой константе а из базиса В - некоторый элемент d = I(а) из области интерпретации D;
3.	каждому функциональному символу f(n) - всюду определенную функцию F(n)=I(f(n));
4.	каждой логической константе р(0) - один символ множества  0,1 ;
5.	каждому предикатному символу р(n) - всюду определенный предикат P(n) = I(p(n)).
Пара (S,I) называется интерпретированной стандартной схемой (ИСС), или стандартной программой (СП).
Определим понятие выполнения программы.
Состоянием памяти программы (S,I) называют функцию W: XS  D, которая каждой переменной x из памяти схемы S сопоставляет элемент W(x) из области интерпретации D. 
Значение терма τ при интерпретации I и состоянии памяти W (обозначим τI(W)) определяется следующим образом:
1) если τ=х, x – переменная, то τI(W) = W(x);
2) если τ=a, a – константа, то τI(W) = I(a);
3) если τ=f(n)(τ1, τ2..., τn), то τI(W)= I(f(n))(τ1I(W), τ2I(W),..., τnI(W)).
Аналогично определяется значение теста  при интерпретации I и состоянии памяти W или I(W):
если =р(n)(τ1, τ2..., τn), то  I(W)= I(p(n))(τ1I(W), τ2I(W),... τnI(W)), n ≥0.
Конфигурацией программы называют пару U=(L,W), где L - метка вершины схемы S, а W - состояние ее памяти. Выполнение программы описывается конечной или бесконечной последовательностей конфигураций, которую называют протоколом выполнения программы (ПВП).
Протокол (U0, U1,..., Ui, Ui+1,...) выполнения программы (S,I) определяем следующим образом (ниже ki  означает метку вершины, а  Wi - состояние памяти в i-й конфигурации протокола, Ui=(ki,Wi)):
U0=(0, W0), W0 – начальное состояние памяти схемы S при интерпретации I.
Пусть Ui=(ki, Wi) - i-я конфигурация ПВП, а О - оператор схемы S в вершине с меткой ki. Если О - заключительный оператор stop(τ1, τ2... τn), то Ui - последняя конфигурация, так что протокол конечен. В этом случае считают, что, программа (S,I) останавливается, а последовательность значений τ1I(W), τ2I(W),..., τnI(W) объявляют результатом val(S,I) выполнения программы (S,I). В противном случае, т. е. когда О - не заключительный оператор, в протоколе имеется следующая, (i+1)-я конфигурация             Ui+1 = (ki+1, Wi+1), причем
а) если О - начальный оператор, а выходящая из него дуга ведет к вершине с меткой L, то ki+1 = L и Wi+1 = Wi;
б) если О - оператор присваивания х:=τ, а выходящая из него дуга ведет к вершине с меткой L, то ki+1 = L, Wi+1 = Wi, Wi+1(х) = τ1(Wi);
в) если О - условный оператор  и I(Wi) = Δ, где Δ 0,1, а выходящая из него дуга ведет к вершине с меткой L, то ki+1 = L и Wi+1 = Wi;
г) если О - оператор петли, то ki+1 = L и Wi+1 = Wi, так что протокол бесконечен.
Таким образом, программа останавливается тогда и только тогда, когда протокол ее выполнения конечен. В противном случае программа зацикливается и результат ее выполнения не определен.
Рассмотрим две интерпретации СПП S1 (рисунок 1.2, а). Интерпретация (S1, I1) задана так:
•	область интерпретации D1  Nat - подмножество множества Nat целых неотрицательных чисел;
•	I1(x)=4; I1(y)=0; I1(a)=1;
•	I1(g)=G, где G - функция умножения чисел, т. е. G(d1,d2)= d1*d2;
•	I1(h)=H, где H - функция вычитания единицы, т. е. H(d)= d-1;
•	I1(p)=P1, где P1 - предикат «равно 0», т.е. P1(d)=1, если d=0. 
Программа (S1, I1) вычисляет 4!   (рисунок 1.2,б).
Интерпретация (S1, I2) задана следующим образом:
•	область интерпретации D2=V*, где V=a,b,c, V* - множество всех возможных слов в алфавите V.
•	I2(x)=abc;
•	I2(y)=, где  - пустое слово;
•	I2(a)= ;
•	I2(g)=CONSTAR;
•	I2(h)=CDR;
•	I2(p)=P2, где P2 - предикат «равное », т.е. P2()=1, если =.
Программа (S1, I2) преобразует слово abc в слово cba (рисунок 1.2, в).
ПВП (S1, I1) и (S1, I2) конечен, результат - 24 и - cba (таблица 1.1 и 1.2).
Таблица 1.1
Конфигурация	U0	U1	U2	U3	U4	U5	U6	U7	U8	U9	U10	U11	U12	U13	
Метка	0	1	2	3	4	2	3	4	2	3	4	2	3		
Значения	х	4	4	4	4	3	3	3	2	2	2	1	1	1	0	
	у	0	1	1	4	4	4	12	12	12	24	24	24	24	24	
   Таблица 1.2
Конфигурация	U0	U1	U2	U3	U4	U5	U6	U7	U8	U9	U10	U11	U12	
Метка	0	1	2	3	4	2	3	4	2	3	4	2	5	
Значения	x	abc	abc	abc	abc	bc	bc	bc	c	c	c				
	у				a	a	a	ba	ba	ba	cba	cba	cba	cba	
1.3. Свойства и виды стандартных схем программ
1.3.1. Эквивалентность, тотальность, пустота, свобода
ССП S в базисе В тотальна (пуста), если для любой интерпретации I базиса В программа (S, I) останавливается (зацикливается).
Стандартные схемы S1 и S2 в базисе В функционально эквивалентны (S1  S2), если либо обе зацикливаются, либо обе останавливаются с одинаковым результатом, т. е. val (S1, I)  val (S2, I).
Примеры тотальных, пустых и эквивалентных схем S2, S3, S4, S5 приведены на рисунке 1.3.

x:=(x)

x:=(x)

start(x)

y:=(x)

p(y)

stop (y)

stop (y)

y:=(y)

p(x)

p(y)

0

1

1

4

1

8

5

8

2

3

1

0

0

7

6

б

1

stop (y)

start(x)

y:=(x)

p(y)

x:=(y)

x:=(x)

p(y)

p(x)

1

6

0

1

4

3

2

1

0

0

5

а

в

г

stop (y)

x:=(x)

x:=(x)

x:=(x)

start(x)

y:=(x)

p(y)

stop (y)

y:=(y)

p(x)

p(y)

p(x)

1

4

0

1

8

5

2

1

1

0

0

6

7

10

0

1

9

7

1

4

0

1

8

5

2

3

1

1

0

0

x:=(x)

x:=(x)

start(x)

y:=(x)

P(y)

stop (y)

y:=(y)

P(x)

P(y)

6

Рисунок 1.3
Цепочкой стандартной схемы (ЦСС) называют:
1. конечный путь по вершинам схемы, ведущий от начальной вершины к заключительной;
2. бесконечный путь по вершинам, начинающийся начальной вершиной схемы.
В случае, когда вершина-распознаватель (v), то дополнительно указывается верхний индекс (1 или 0), определяющий 1-дугу или 0-дугу, исходящую из вершины.

Примеры цепочек схемы S1 (рисунок 1.2,а):
(0, 1, 21, 5); (0, 1, 20, 3, 4, 20,3,4,21,5) и т. д.
Цепочкой операторов (ЦО) называется последовательность операторов, метящих вершины некоторой цепочки схемы. 
Например для S1: (start(х), у:=a, р1(x), stop(у)) или (start(х), у:=a, р0(x), y:=g(x, y), x:=h(x), р0(x), y:=g(x, y), x:=h(x), р0(x), y:=g(x, y), x:=h(x), …)) и т. д.
Предикатные символы ЦО обозначаются так же, как вершины распознавателей в ЦСС.
Пусть S - ССП в базисе В, I - некоторая его интерпретация, (0, 1, к2, к3,…) - последовательность меток инструкций S, выписанных в том порядке, в котором эти метки входят в конфигурации протокола выполнения программы (S, I). Ясно, что эта последовательность – цепочка схемы S. Считают, что интерпретация I подтверждает (порождает) эту цепочку.
ЦСС в базисе В называют допустимой, если она подтверждается хотя бы одной интерпретацией этого базиса. 
Не всякая ЦСС является допустимой. В схеме S2 (рисунок 1.3,а) цепочки (0, 1, 20, 5, 61, 7), (0, 1, 21, 3, 40, 7) и все другие конечные цепочки не подтверждаются ни одной интерпретацией.
Свойство допустимости цепочек играет чрезвычайно важную роль в анализе ССП. В частности оно определяет те случаи, когда стандартная схема свободна.
ССП свободна, если все ее цепочки допустимы.
Допустимая цепочка операторов - это цепочка операторов, соответствующая допустимой цепочке схемы. В тотальной схеме все допустимые цепочки (и допустимые цепочки операторов) конечны. В пустой схеме - бесконечны.
Рассмотренные свойства распространяются на все другие классы стандартных схем и образуют опорные пункты схематологии программирования.
1.3.2. Свободные интерпретации
Множество всех интерпретаций очень велико и поэтому вводится класс свободных интерпретаций (СИ), который образует ядро класса всех интерпретаций в том смысле, что справедливость высказываний о семантических свойствах ССП достаточно продемонстрировать для программ, получаемых только с помощью СИ.
Все СИ базиса В имеют одну и ту же область интерпретации, которая совпадает со множеством Т всех термов базиса В. Все СИ одинаково интерпретируют переменные и функциональные символы, а именно:
а) для любой переменной х из базиса В и для любой СИ Ih этого базиса Ih(x)=x;
б) для любой константы a из базиса В  Ih(a)=a;
в) для любого функционального символа f(n) из базиса В, где n1, Ih(f(n))=F(n): TnT, где F(n) - словарная функция такая, что
F(n)(1, 2, ..., n)= f(n) (1, 2, ... n), 
т. е. функция F(n) по термам 1, 2, ...n  из Т строит новый терм, используя функциональный смысл символа f(n).
Что касается интерпретации предикатных символов, то она полностью свободна, т.е. разные СИ различаются лишь интерпретаций предикатных символов.
Таким образом, после введения СИ термы используются в двух разных качествах, как функциональные выражения в схемах и как значения переменных и выражений. В дальнейшем термы-значения будем заключать в апострофы. Например, если где 1=`f(x,a)` - терм-значение переменной x, а где 2 = `g(y)` - терм-значение переменной y, то значение свободно интерпретированного терма        3=f(x, h(y)) равно терму-значению `f(f(x,a), h(g(y)))`.
Пример 1.1. Пусть Ih -СИ базиса, в котором определена схема S1 (рисунок 1.2, а), и в этой интерпретации предикат Р=Ih(р) задан так: P() = 1, если число функциональных символов в  больше двух; P() = 0, в противном случае.
Тогда ПВП (S1,Ih) можно представить таблицей 1.3.
Таблица 1.3
Конфигурация	Метка	Значения	
		X	у	
U0	0	`x`	`y`	
U1	1	`x`	`a`	
U2	2	`x`	`a`	
U3	3	`x`	`g(x,a)`	
U4	4	`h(x)`	`g(x,a)`	
U5	2	`h(x)`	`g(x,a)`	
U6	3	`h(x)`	`g(h(x),g(x,a))`	
U7	4	`h(h(x))`	`g(h(x),g(x,a))`	
U8	2	`h(h(x))` 	`g(h(x),g(x,a))`	
U9	3	`h(h(x))`	`g(h(h(x)),g(h(x),g(x,a)))`	
U10	4	`h(h(h(x)))`	`g(h(h(x)),g(h(x),g(x,a)))`	
U11	2	`h(h(h(x)))`	`g(h(h(x)),g(h(x),g(x,a)))`	
U12	5	`h(h(h(x)))`	`g(h(h(x)),g(h(x),g(x,a)))`	
Обратим внимание на следующую особенность термов. Если из терма удалить все скобки и запятые, то получим слово (назовем его бесскобочным термом), по которому можно однозначно восстановить первоначальный вид терма (при условии, что отмечена или известна местность функциональных символов). Например, терму g(2)(h(1)(x), g(2)(x,y)) соответствует бесскобочный терм ghxgxy. Правила восстановления терма по бесскобочной записи аналогичны правилам восстановления арифметических по их прямой польской записи, которая просто и точно указывает порядок выполнения операций.
В этой записи, впервые примененной польским логиком Я. Лукашевичем, операторы следуют непосредственно за операндами. Поэтому ее иногда называют постфиксной записью. Классическая форма записи, как мы обычно пишем, называется инфиксной. Например:
A*B => AB*	A*B+C =>AB*C+	A*(B+C/D) =>ABCD/+*		A*B+C*D =>AB*CD*+
Правила представления в польской записи:
1)	Идентификаторы следуют в том же порядке, что и в инфиксной записи
2)	Операторы следуют в том же порядке, в каком они должны вычисляться (слева направо)
3)	3) Операторы располагаются непосредственно за своими операндами.
Бесскобочная запись термов короче и она будет использоваться далее наряду с обычной записью.
1.3.3. Согласованные свободные интерпретации
Полагают, что интерпретация I и СИ Ih (того же базиса В) согласованы, если для любого логического выражения  справедливо Ih()=I().
Пусть, например, =`g(h(h(x)), g(h(x), g(x,a)))`, а интерпретация I3 совпадает с интерпретацией I1 из п. 1.2.4 за исключением лишь того, что I(x)=3. Так как I3(a) = 1; I3(g) - функция умножения; I3(h) - функция вычитания 1; получаем I3() = ((3-1)-1)*((3-1)*(3*1)) = 6.
В этом случае Ih  примера из п. 1.3.2. согласована с только что рассмотренной интерпретацией I3, а так же с I2 (рисунок 1.2, в), но не согласована с I1 (рисунок 1.2, б).
Справедливы прямое и обратное утверждения, что для каждой интерпретации I базиса В существует согласованная с ней СИ этого базиса.
Так, например, выше было сказано, что Ih рассмотренного примера не согласована с I1. Что бы сделать Ih согласованной, необходимо условие Р() видоизменить: P() = 1, если число функциональных символов в  больше трех; P() = 0, в противном случае.
Можно  поступить и по другому. Оставить Ih без изменения и согласовать с ней I1. Для этого необходимо будет заменить I1(x) = 4, на I1(x) = 3.
Введем важное вспомогательное понятие подстановки термов, используемое в дальнейшем. Если x1, …, xn (n ≥ 0) – попарно различные переменные, 1, ..., n – термы из Т, а  - функциональное или логическое выражение, то через [1/x1, ..., n/xn] будем обозначать выражение, получающееся из выражения  одновременной заменой каждого из вхождений переменной xi на терм I (i = 1, …, n). Например: a[y/x]=a, f(x, y)[y/x, x/y]=f(y, x), g(x)[g(x)/x]=g(g(x)), p(x)[a/x]=p(a).
Приведем без доказательства несколько важных утверждений:
Если интерпретация I и свободная интерпретация Ih согласованы, то программы (S, I) и (S, Ih) либо зацикливаются, либо обе останавливаются и I(val(S,Ih))= val(S,I), т.е. каждой конкретной программе можно поставить во взаимно-однозначное соответствие свободно интерпретированную (стандартную) согласованную программу.
Если интерпретация и свободная интерпретация согласованы, они порождают одну и ту же цепочку операторов схемы.
Теорема Лакхэма – Парка – Паттерсона. Стандартные схемы S1 и S2 в базисе В функционально эквивалентны тогда и только тогда, когда они функционально эквивалентны на множестве всех свободных интерпретаций базиса В, т.е. когда для любой свободной интерпретации Ih программы (S1,Ih) и (S2,Ih) либо обе зацикливаются, либо обе останавливаются и									 val(S1,I) = {I(val(S1 Ih)) = I(val(S2 Ih))} = val(S2,I).
Стандартная схема S в базисе В пуста (тотальна, свободна) тогда и только тогда, когда она пуста (тотальна, свободна) на множестве всех свободных интерпретаций этого базиса, т.е. если для любой свободной интерпретации Ih программа (S, Ih) зацикливается (останавливается). 
Стандартная схема S в базисе В свободна тогда и только тогда, когда она свободна на множестве всех свободных интерпретаций этого базиса, т. е. когда каждая цепочка схемы подтверждается хотя бы одной свободной интерпретацией.
1.3.4. Логико-термальная эквивалентность
Отношение эквивалентности Е, заданное на парах стандартных схем, называют корректным, если для любой пары схем S1 и S2 из S1 Е S2 следует, что S1 S2, т. е. S1 и S2 функционально эквивалентны.
Поиск разрешимых корректных отношений эквивалентности представляет значительный интерес с точки зрения практической оптимизации преобразования программ, поскольку в общем виде функциональная эквивалентность стандартных схем алгоритмически неразрешима. 
Идея построения таких (корректных и разрешимых) отношений связанна с введением понятия истории цепочки схем. В истории с той или иной степенью детальности фиксируются промежуточные результаты выполнения операторов рассматриваемой цепочки. Эквивалентными объявляются схемы, у которых совпадают множества историй всех конечных цепочек. 
Одним из отношений эквивалентности является логико-термальная эквивалентность (ЛТЭ). 
Определим термальное значение переменной х для конечного пути ω схемы S как терм t(ω, x), который строится следующим образом.
1.	Если путь ω содержит только один оператор А, то: t(ω, x) = , если А – оператор присваивания, t(ω, x) = х, в остальных случаях.
2.	Если ω = ω’Ае, где А – оператор, е – выходящая из него дуга, ω’ – непустой путь, ведущий к А, а x1, …, xn – все переменные терма t(Ае, x), то t(ω, x) = t(Ае, x)[ t(ω’, x1)/x1, …, t(ω’, xn)/xn].
Понятие термального значения распространим на произвольные термы :				t(ω, x) =  [ t(ω, x1)/x1, …, t(ω, xn)/xn].
Например, пути
start(х); y:=x; p1(x); x:=f(x); p0(y); y:=x; p1(x); x:=f(x) в схеме на рисунке 1.4, а соответствует термальное значение f(f(x)) переменной х.

1

а

stop (х)

start(x)

y:=x

p(х)

x:=(х)

1

0

p(y)

0

б

loop

start(x)

p(х)

stop ((х))

1

0

Рисунок 1.4.
Для пути ω в стандартной схеме S определим ее логико-термальную историю (ЛТИ) lt(S, ω) как слово, которое строится следующим образом.
1.	Если путь ω не содержит распознавателей и заключительной вершины, то lt(S, ω) – пустое слово.
2.	Если ω = ω’vе, где v – распознаватель с тестом p(1, ..., k), а е – выходящая из него Δ-дуга,      Δ 0,1, то lt(S, ω) = lt(S, ω’) pΔ(t(ω’, 1), …, t(ω’, k)).
3.	Если ω = ω’v, где v – заключительная вершина с оператором stop(1, ..., k), то 
lt(S, ω) = lt(S, ω’) t(ω’, 1) … t(ω’, k).
Например, логико-термальной историей пути, упомянутого в приведенном выше примере, будет p1(x) p0(x) p1(f(x)).
Детерминантом (обозначение: det(S)) стандартной схемы S называют множество ЛТИ всех ее цепочек, завершающихся заключительным оператором. 
Схемы S1 и S2 называют ЛТЭ (лт - эквивалентными) S1 ЛТ S2, если их детерминанты совпадают. 
Приведем без доказательства следующие утверждение:
Логико-терминальная эквивалентность корректна, т. е. из ЛТЭ следует функциональная эквивалентность (S1 ЛТ S2  S1  S2). Обратное утверждение как видно из рисунка 1.4 не верно. 
ЛТ–эквивалентность допускает меньше сохраняющих ее преобразований, чем функциональная эквивалентность.
1.4. Моделирование стандартных схем программ
1.4.1. Одноленточные автоматы
Конечный одноленточный (детерминированный, односторонний) автомат обнаруживают ряд полезных качеств, используемых в теории схем программ для установления разрешимости свойств ССП.
Одноленточный конечный автомат (ОКА) над алфавитом V задается набором
A = { V, Q, R, q0, #, I } и правилом функционирования, общим для всех таких автоматов. В наборе А
V - алфавит;
Q - конечное непустое множество состояний (QV=);
R - множество выделенных заключительных состояний (RQ);
q0 - выделенное начальное состояние;
I - программа автомата;  
# - «пустой» символ.
Программа автомата I представляет собой множество команд вида qаq', в которой q,q'Q, aV и для любой пары (q, a) существует единственная команда, начинающаяся этими символами. 
Неформально ОКА можно представить как абстрактную машину, похожую на машину Тьюринга, но имеющую следующие особенности:
1) выделены заключительные состояния;
2) машина считывает символы с ленты, ничего не записывая на нее;
3) на каждом шаге головка автомата, считав символ с ленты и перейдя согласно программе в новое состояние, обязательно передвигается вправо на одну клетку;
4) автомат останавливается в том и только в том случае, когда головка достигнет конца слова, т.е. символа .

q0

b

a

a

b

а

b

b

q1

q2

q3

а

Рисунок 1.5

Говорят, что автомат допускает слово  в алфавите V, если, начав работать с лентой, содержащей это слово, он останавливается в заключительном состоянии. Автомат A задает характеристическую функцию множества MA допускаемых им слов в алфавите V, т. е. он распознает, принадлежит ли заданное слово множеству MA если связать с остановкой в заключительном состоянии символ 1, а с остановкой в незаключительном состоянии – 0. 
Наглядным способом задания ОКА служат графы автоматов. Автомат А представляется графом, множество вершин которого – множество состояний Q, и из вершины q в вершину q’ ведет дуга, помеченная символом а, тогда и только тогда, когда программа автомата содержит команду  qаq'. Работе автомата над заданным словом соответствует путь из начальной вершины q. Последовательность проходимых вершин этого пути – это последовательность принимаемых автоматом состояний, образ пути по дугам – читаемое слово. Любой путь в графе автомата, начинающийся в вершине q0 и заканчивающийся в вершине q,R, порождает слово, допустимое автоматом.
Пример 1.2.  ОКА A = ({a, b}, {q0, q1, q2, q3}, {q2}, q0, , I), допускающего слова {an bm | n=1,2, ...; m=1,2, ...}, задается графом (рисунок 1.5). Программа I содержит команды: 
q0aq1; q0bq3; q1aq1; q1bq2; q2aq3; q2bq2; q3aq3; q3bq3.
Автомат называется пустым, если МА = , Автоматы А1 и А2 эквивалентны, если МА1 = МА2. Для машины Тьюринга проблемы пустоты и эквивалентности неразрешимы, более того, они не являются частично разрешимыми. Ситуация меняется для конечных автоматов.
Для ОКА доказано:
1) Проблема пустоты ОКА разрешима.
Доказательство основано на проверке допустимости конечного множества всех слов, длина которых не превышает числа состояний ОКА - n. Если ни одно слово из этого множества не допускается, то ОКА «пуст».
2) Предположение о том, что минимальная длина допускаемого слова больше n отвергается на том основании, что оно может быть сведено к слову меньшей длины, путем выбрасывания участков между двумя повторяющимися в пути узлами.
3) Проблема эквивалентности ОКА разрешима. 
Доказательство основано на использовании отношения эквивалентности двух состояний q и q': если состояния q и q' эквивалентны, то для всех aA состояния (q, a) и '(q', a) также эквивалентны. Формируемые пары не должны входить одновременно заключительное и незаключительное состояния.

1.4.2. Многоленточные автоматы 
Многоленточный (детерминированный, односторонний) конечный автомат (МКА) задается так же, как ОКА. Отличие состоит в том, что множество состояний Q разбивается на n  2 подмножеств (непересекающихся) Q1, ..., Qn. «Физическая» интерпретация n - ленточного автомата отличается тем, что он имеет n лент и n головок, по головке на ленту. Если автомат находится в состоянии qQi, то i-я головка читает i-ю ленту так же, как это делает ОКА. При переходе МКА в состояние q'Qj (ij) i-я головка останавливается, а j-я начинает читать свою ленту. МКА останавливается, когда головка на одной из лент прочитает символ .

q10

q22

q21

1

0

1

0

0

1

0

1

q23

Рисунок 1.6

Рассмотрим функционирование МКА с n=2 (рисунок 1.6) на примере сравнения пар слов в алфавите {1, 0} и допуске только совпадающих слов. 
Здесь Q=Q1UQ2, где Q1={q01}; Q2={q12, q22, q32}; R={q01}; V={0, 1}, начальное состояние - q01. МКА обрабатывает наборы слов (U1, U2), где слово U1 записано на первой ленте, а U2 - на второй. Допустимое множество наборов MA -это все возможные пары одинаковых слов, т.е. наборы, где U1 = U2. Например, набор может быть (1101, 1101) и т.п.
В том случае, когда слова совпадают, МКА остановится в заключительном состоянии q01 (именно в этом состоянии поступит символ ) и набор будет допущен. Если слова не совпадут хотя бы в одном символе, МКА перейдет в состояние q32, из которого не выйдет до появления символа , который и зафиксирует отсутствие совпадения слов, т.е. не допустит искаженный набор.
Доказывается разрешимость проблемы эквивалентности двухленточных автоматов.
1.4.3. Двухголовочные автоматы
Несмотря на то, что двухленточные и двухголовочные автоматы похожи друг на друга, их свойства сильно отличаются. Так, проблема пустоты разрешима для многоленточных автоматов и неразрешима для многоголовочных. Более того, в последнем случае она не является даже частично разрешимой. Проблема эквивалентности также не является частично разрешимой для многоголовочных автоматов. Однако проблема эквивалентности разрешима для двухленточных автоматов, и остается пока открытой для многоленточных автоматов с тремя и более лентами.
Двухголовочный конечный автомат (ДКА) имеет одну ленту и две головки, которые могут независимо перемещаться вдоль ленты в одном направлении. Множество состояний Q разбито на два непересекающихся множества. В состояниях Q1 активна первая головка, а в состояниях Q2 - вторая.
Двухголовочный автомат можно рассматривать как такой двухленточный автомат, который работает с идентичными словами на обеих лентах. 
Приведем пример ДКА, который проверяет равенство двух последовательно записанных слов в алфавите V = {0, 1}. Признаком окончания каждого из слов сделаем вспомогательный символ *, не входящий в V. Автомат должен допускать только слова вида а * а *, где а  V*. Мы возьмем A = (V  {*}, Q1  Q2, R, q01, #, I), где               Q1 = {q01, q11, q21, q71} - множество состояний, в которых активна первая головка; Q1 = {q32, q42, q52, q62} - множество состояний, в которых активна вторая головка; R = { q71} - множество, содержащее единственное заключительное состояние. Граф автомата показан на рисунке 1.7, на котором вместо многих «параллельных» дуг с разными 
	Рисунок 1.7.		        пометками нарисована одна дуга со всеми этими пометками.
Находясь в состоянии g01, автомат передвигает первую головку к началу второго слова и, обнаружив его, переходит в состояние q11. Если конец ленты # встречается раньше символа *, автомат переходит в незаключительное состояние q62. Если же автомат приходит к состоянию q11, он считывает поочередно символы второго слова первой головкой (состояние q11), а символы первого слова — второй головкой (состояния q32 и q52), сравнивая эти символы. Автомат возвращается каждый раз в состояние q11, если символы одинаковы. Если же обнаружится несовпадение символов или первая головка встречает конец слова раньше символа *, автомат уходит в состояние q62. Попав в это состояние, автомат не может выйти из него; перемещая вторую головку к концу слова на ленте, он достигает #, находясь в незаключительном состоянии, так что слово на ленте отвергается. Если первая головка достигнет конца второго слова, а вторая головка обнаружит, что первое слово тоже просмотрено до конца, то автомат перейдет в заключительное состояние q71. В противном случае автомат перейдет в состояние q62, отвергая слово.
Этот пример легко обобщить на случай произвольного алфавита V, увеличивая количество состояний множества Q.
Проблемы пустоты и эквивалентности. 
Будем говорить, что ДКА моделирует работу машины Тьюринга над некоторым начальным словом, если автомат допускает единственное слово — конечный протокол paботы машины над ним.
Лемма (Розенберг). Существует алгоритм, который для любой машины Тьюринга и для любого начального слова строит двухголовочный автомат, моделирующий ее работу над этим словом.
Теорема. Проблема пустоты ДКА не является частично разрешимой.
Теорема. Проблема эквивалентности ДКА не является частично разрешимой.
Из неразрешимости проблемы пустоты немедленно следует неразрешимость проблемы эквивалентности, так как пустоту можно рассматривать как частный случай эквивалентности (например, эквивалентность фиксированному пустому автомату, пустой машине Тьюринга и т. д.). Если же проблема пустоты разрешима (частично разрешима), то проблема эквивалентности должна исследоваться независимо, так как в общем случае из разрешимости (частичной разрешимости) пустоты не следует разрешимость (частичная разрешимость) проблемы эквивалентности. Например, проблема пустоты разрешима для многоленточных автоматов, но проблема их эквивалентности открыта (для случая трех и более лент).
1.4.4. Двоичный двухголовочный автомат
Cтандартные схемы могут моделировать (в уточненном ниже смысле) двухголовочные автоматы, что позволяет свести проблему пустоты этих автоматов к проблеме пустоты схем. Такое моделирование можно осуществить более простым способом, если использовать специальный класс двухголовочных автоматов, а именно класс двоичных автоматов, работающих со словами над алфавитом {0, 1}. Следующая лемма устанавливает связь между классом всех двухголовочных автоматов и подклассом двоичных автоматов специального вида.

qj2

qjn

qj1

qkj

...

...

...

a1

a2

an

a

.

..

...

0

0

1

Sa , Sr

1

0

1

1

0

qjk

Sj1i

Sj2i

qj1

qj2

Sjni

qjn

r11

б

.

.

.

Sr

...

...

0

0

0

0

r11

r21

1

1

от Sjni 

в

Sa

...

от не заключительных старых состояний 

от заключительных старых состояний 

0

0

Рисунок 1.8

г

Лемма. Существует алгоритм преобразования двухголовочных автоматов в двоичные двухголовочные автоматы (ДДКА), сохраняющий пустоту автоматов (построенный двоичный автомат Аb пуст тогда и только тогда, когда пуст исходный автомат А).
Доказательство. Пусть ДКА  А над алфавитом V = {a1, a2, ...an} имеет множество состояний  QА={q1k, q2k, …, qkk}, где верхний индекс (k = 1, 2) определяет номер активной головки. Преобразование этого автомата в двоичный начнем с кодировки символов и слов из V* словами в алфавите {0, 1} по следующему правилу:
код () = 0;
код (ai) = 11....10 (i = 1, …, n);
код (ai) = код () код (ai).
Так как символ  кодируется нулем, то любому непустому слову на ленте автомата А соответствует двоичное слово на ленте автомата Аb, оканчивающееся двумя нулями. Автомат останавливается, прочитав два нуля подряд (или 0, означающий пустое слово).
Автомат A преобразуется в двоичный автомат Ab так, как показано на графах рисунка 1.8. Каждый фрагмент графа А (рисунок 1.8, а) заменяется фрагментом (рисунок 1.8, б) для Аb.
После замены добавляются фрагменты (рисунок 1.8 в, г).
Множество состояний автомата Аb включает:
а) все старые состояния из QА;
б) для каждого старого состояния qjk  n новых состояний, n - число символов алфавита V;
в) два новых состояния r11 и r21.
Заключительными состояниями автомата А являются заключительные состояния автомата Аb.
Вершины Sa (останов допускающий) и Sr (останов отвергающий) носят на графе вспомогательный характер в графе Аb. Они отмечают тот факт, что автомат прочитал два нуля подряд и остановился в заключительном состоянии (случай Sa) или в незаключительном состоянии (случай Sr).
Легко убедиться, что автомат Аь допускает двоичное слово р тогда и только тогда, когда оно является двоичным кодом слова из V*, допускаемого автоматом А. Таким образом, из пустоты автомата А следует пустота автомата Аь, и наоборот. 

a

q01

b

q12

a

a

c

b

Sa

0

0

0

0

0

0

0

0

0

0

1

1

1

q01

S011

S021

1

r11

q12

r21

1

1

1

1

1

S112

S122

S132

Sr

б

S031

Рисунок 1.9

с

На рисунке 1.9, а приведен граф ДКА  A допускающий только те слова в алфавите V = {a, b, c}, в которых символ a встречается не меньшее число раз, чем символы b и c, вместе взятые. Заключительное состояние R={q01}. На рисунке 1.9, б приведен граф ДДКА, построенный по автомату А (10 – код символа a, 110 – код b, 1110 – код c).
По заданному ДДКА возможно построить ССП и наоборот, что позволяет решить задачу разрешимости (не разрешимости) свойств ССП, так как эта задача для ДДКА решена.
1.4.5. Построение схемы, моделирующей автомат
Двоичное слово b1b2 … bn согласовано со свободной интерпретацией базиса B, если для любого i, 1 i  n, I(p) (‘fia’) = bi, где p - единственный предикатный символ базиса B.
Пример 1.3. Слово 101010100 согласовано с любой свободной интерпретацией I такой, что для всех i  9  I(p) (‘fia’) = 1 если i нечетно и меньше 9, и  I(p) (‘fia’) = 0, если i четно или равно 9. Свободная интерпретация I такая, что для всех i  I(p) (‘fia’) = 0, согласована с любым словом, не содержащим 1.
Для того чтобы свести проблему пустоты ДДКА к проблеме пустоты стандартных схем покажем, что для любого двоичного автомата А можно построить схему S, которая моделирует автомат А в следующем смысле. Если на ленту автомата А подано произвольное двоичное слово а, то программа  (S, I), где I — любая свободная интерпретация базиса В, согласованная с а, останавливается в том и только в том случае, когда автомат допускает слово а.
Лемма. ДДКА пуст в том и только в том случае, если пуста моделирующая его стандартная схема.
Лемма. Для любого ДДКА можно построить моделирующую его стандартную схему.
Теорема (Лакхэм - Парк - Патерсон). Проблема пустоты, стандартных схем не является частично разрешимой.
Теорема (Лакхэм - Парк - Патерсон, Летичевекай). Проблема функциональной эквивалентности стандартных схем не является частично разрешимой.
Теорема (Лакхэм - Парк - Патерсон). Проблема тотальности стандартных схем частично разрешима.
Теорема (Патерсон). Проблема свободы, стандартных схем не является частично разрешимой.
1.5. Рекурсивные схемы
1.5.1. Рекурсивное программирование
Среди упомянутых выше методов формализации понятия вычислимой функции метод Тьюринга — Поста основан на уточнении понятия процесса вычислений, для чего используются абстрактные «машины», описанные в точных математических терминах. Другой подход (метод Черча — Клини) основан на понятии рекурсивной функции, рекурсивная функция задается с помощью рекурсивных определений. Рекурсивное определение позволяет связать искомое значение функции для заданных аргументов с известными значениями той же функции при некоторых других аргументах. Эта связь устанавливается с помощью универсального механизма рекурсии, дающего механическую процедуру поиска значений функции. Двум подходам к определению вычислимых функций соответствуют два метода программирования этих функций — операторное и рекурсивное программирование. При операторном методе программа представляет собой явно выписанную последовательность, описаний действий гипотетической вычислительной машины (последовательность операторов, команд и т. п.).
Язык Фортран — типичный представитель операторных языков. С другой стороны, рекурсивная программа — это   совокупность рекурсивных определений, задающих рекурсивную функцию, для которой аргументами служат начальные данные программы, а значением — результат выполнения программы. Известный язык рекурсивного программирования — язык Лисп — предназначен для обработки символьной информации. В других зыках комбинируют оба метода программирования. Так, Паскаль — операторный язык с возможностью рекурсивного программирования, предоставляемой механизмом рекурсивных процедур и функций.
Примером рекурсивно определяемой функции является факториальная функция FACT: Nat → Nat:
FACT(х) = 1,если  х = 0,  FACT(х) =  х  FACT(х — 1),  если х > 0.
Операторные программы, вычисляющие значения этой функции, приведены в п. 1.1.3. Эту же функцию можно запрограммировать в некотором рекурсивном языке, базирующемся на механизме рекурсивных функций языка Паскаль:
FACT(a),
FACT(х) = if  х = 0 then  1 else х  FACT(х - 1),
где а — некоторое целое неотрицательное число.
Выполнение этой программы для некоторого значения а (пусть а = 4) может быть осуществлено следующим образом. В обе части рекурсивного определения вместо х подставляется 4, после чего вычисляется правая часть определения. Вычисление правой части начинается с вычисления логического выражения. Если его значение 1 (истина), то вычисляется левое функциональное выражение (стоящее после то), а если его значение 0 (ложь) — вычисляется правое выражение (стоящее после else). Вычисление функционального выражения сводится к его упрощению, т. е. выполнению всех возможных вычислений. Если в упрощенном выражения остается вхождение символа определяемой функции FACT, то осуществляется переход к новому шагу выполнения программы. На этом шаге вхождение FACT(m), где m — значение внутри скобок после упрощения, заменяется левым (т = 0) или правым (m > 0) функциональным выражением, в котором все вхождения х заменены на m. Упрощения продолжаются до тех пор, пока не будет получено выражение, не содержащее FACT (в нашем случае это выражение — число).
Вычисление рекурсивной программы может завершиться за конечное число шагов с результатом, равным значению запрограммированной функции для заданных аргументов (начальных значений переменных), но может и продолжаться бесконечно. В последнем случае значение функции не определено.
1.5.2. Определение рекурсивной схемы
Рекурсивная схема (РС) так же, как СПП определяется в некотором базисе. Полный базис РС, как и базис ССП, включает четыре счетных множества символов: переменные, функциональные символы, предикатные символы, специальные символы.
Множества переменных и предикатных символов ничем не отличаются от ССП. Множество специальных символов - другое, а именно: {if, то, else, (, ), ,}. Отличие множества функциональных символов состоит в том, что оно разбито на два непересекающиеся подмножества: множество базовых функциональных символов и множество определяемых функциональных символов (обозначаются для отличия прописными буквами, например, F(1),G(2), и т.д.).
В базисе РС нет множества операторов, вместо него – множество логических выражений и множество термов.
Простые термы определяются так же, как термы–выражения в СПП. Среди простых термов выделим базовые термы, которые не содержат определяемых функциональных символов, а также вызовы-термы вида F(n)(1,2,…n), где 1,2,… n - простые термы, F(n) - определяемый функциональный символ.
Логическое выражение - слово вида 
p(n)(1,2,…n), 
где p(n) - предикатный символ, а 1,2,…n - базовые термы.
Терм - это простой терм, или условный терм, т.е. слово вида if   then  1 else 2, 
где  - логическое выражение, 1, 2 - простые термы, называемые левой и соответственно правой альтернативой.
Примеры термов:
−	f(x, g(x, y)); h(h(a)) - базовые термы;
−	f(F(x), g(x, F(y))); H(H(a)) - простые термы;
−	F(x); H(H(a)) - вызовы;
−	if   p(x, y) then h(h(a))  else  F(x) - условный терм.
Используется бесскобочная форма представления:
if   pxy then  hha  else  Fx - условный терм.
Расширим в базисе В множество специальных символов символом "=".
Рекурсивным уравнением, или определением функции F назовем слово вида
F(n)(x1,x2,…xn) = (x1,x2,…xn),
где (x1,x2,…xn) - терм, содержащий переменные, называемые формальными параметрами функции F.
Рекурсивной схемой называется пара (, М), где  - терм, называемый главным термом схемы (или ее входом). М - такое множество рекурсивных уравнений, что все определяемые функциональные символы в левых частях уравнений  различны и всякий определяемый символ, встречающийся в правой части некоторого уравнения или в главном терме схемы, входит в левую часть некоторого уравнения. Другими словами, в РС имеется определение всякой вызываемой в ней функции, причем ровно одно. 
Примеры РС:
RS1:	F(x); F(x) = if   p(x) then  a  else  g(x, F(h(x))).
RS2:	A(b, c); A(x, y) = if   p(x) then  f(x)  else  B(x, y);
B(x, y) = if   p(y) then  A(g(x), a) else  C(x, y);
C(x, y) = A(g(x), A(x, g(y))).
RS3:	F(x); F(x) = if   p(x) then  x  else  f(F(g(x)), F(h(x))).
Пара (RS, I), где RS - PC в базисе В, а I - интерпретация этого базиса, называется рекурсивной программой. При этом заметим, что определяемые функциональные символы не интерпретируются.
Протоколы выполнения программы (RS1, I1) и (RS1, I2), где I1 и I2 - интерпретации из п. 1.2.3 (рисунок 1.2, б, в), выглядят следующим образом:
№ п/п	Значение терма для (RS1, I1)	Значение термадля (RS1, I2)	
1
2
3
4
5
6	F(4)
4*F(3)
4*(3*F(2))
4*(3*(2*F(1)))
4*(3*(2*(1*F(0))))
4*(3*(2*(1*1)))=24	F(a,b,c)
CONSCAR(abc, F(b,c))
CONSCAR(abc, CONSCAR(bc, F(c)))
CONSCAR(abc, CONSCAR(bc, CONSCAR(c, F(ε))))
CONSCAR(abc, CONSCAR(bc, CONSCAR(c, ε)))=abc

1.6. Трансляция схем программ
1.6.1. О сравнении класс сов схем. 
Программы для ЭВМ, будь-то программы, записанные на операторном языке, или программы на рекурсивном языке, универсальны в том смысле, что любую вычислимую функцию можно запрограммировать и найти ее значения для заданных значений аргументов. При этом не требуется богатого набора программных примитивов и базовых операций: достаточно тех средств, которые моделируются стандартными схемами. Это значит, что различные классы программ не имеет смысла сравнивать способности реализовать различные алгоритмы,— все они оказываются универсальными. В то же время программисты знают, что одни программные примитивы являются «более выразительными», чем другие, что запись алгоритмов с привлечением рекурсии короче, чем итерационное представление, но вычисления по такой программе могут потребовать больше времени, и т. д. При переходе к схемам программ возникает возможность поставить и исследовать проблему выражения одних наборов примитивов через другие в более чистом виде. Задачи такого типа образуют сравнительную схематологию, основу которой составляют теоремы о возможности или невозможности преобразования схем из одного класса в схемы другого. При этом наряду с основной задачей — выяснением соотношений между различными средствами программирования — решается и другая, внутренняя задача схематологии. Действительно, если мы умеем трансформировать один класс схем в другой, то сможем переносить результаты, полученные для некоторого класса схем, на другие классы.
Мы будем сравнивать классы схем, у которых базисы согласованны в том смысле, что множества переменных, базовых функциональных символов и предикатных символов одинаковы в данных базисах. Это дает возможность превращать в программы схемы из разных классов с помощью одной и той же интерпретации базисов. Например, полные базисы стандартных и рекурсивных схем согласованны, т. е. определение функциональной эквивалентности может быть обобщено на схемы из разных классов.
Схема S1 из класса W и схема S2 из класса W’ функционально эквивалентны, если для любой интерпретации I согласованных базисов классов W и W’ программы (S1, I), (S2, I) или обе зацикливаются, или обе останавливаются с одним и тем же результатом.
Говорят, что класс схем W мощнее класса схем W’, или класс W’ транслируем в класс W, если для любой схемы из W’ существует эквивалентная ей схема в классе W. Классы W и W’ равномощны, если W’ мощнее W и W мощнее W’.
Доказано, что класс ССП транслируем в класс РС и класс РС не транслируем в класс ССП.
Рассмотренные примеры подтверждают первое утверждение для одинаковых интерпретаций I базисов. В этом случае РС RS1 эквивалентна ССП S1. При разных интерпретациях ССП и РС результаты будут различаться и следовательно программы (RS1, I1) и (S1, I2) будут различны.
Второе утверждение подкрепляется РС RS3. Причина не транслируемости этой схемы обусловлена тем, что при варьировании интерпретаций возникает необходимость запомнить сколь угодно большое число промежуточных значений, в то время как память любой стандартной схемы ограничена.
Существуют некоторые классы РС, транслируемые в ССП. К ним относится класс линейных унарных РС, имеющих базис с единственной переменной x и одноместными функциональными и предикатными символами. Например, линейная унарная РС 
RS4:	F(x); F(x)=if  p(x) then x else  f(x, F(g(x))) транслируема в ССП.
1.6.2. Схемы с процедурами
Схемы с процедурами строятся в объединенном базисе классов стандартных и рекурсивных схем. Она состоит из двух частей - главной схемы и множества схем процедур. Главная схема - это стандартная схема, в которой имеются операторы присваивания специального вида x:= F(n)(y1,y2,…yn), называемые операторами вызова процедур. Схема процедуры состоит из заголовка и тела процедуры, разделенных символом равенства. Заголовок имеет тот же вид, что и левая часть рекурсивных уравнений. Тело процедуры - это стандартная схема того же вида, что и главная схема. Заключительный оператор тела процедуры всегда одноместен (stop(х)). Ниже приведен пример схемы с процедурами.
Главная схема	Множество схем процедур	
(start(x),
1:  z:=x,
2:  u:=a,
3:  x:=F(x, z, u),
4:  u:=b,
5:  z:=F(z, x, u)
6:  stop(z))	F(y, v, w) = start, 
1:  if  p(y)  then  2  else  4,
2:  y:=h(y),
3:  v:=G(v, w) goto 1,
4:  if  q(w)  then  5  else  6,
5:  y:= v,
6:  stop(y))
G(t, r) = (start,
1:  if  q(r)  then  2  else  3,
2: t := f(t),
3:  stop(t);	
Доказано, что класс РС транслируем в класс схем с процедурами и наоборот.
1.7 Обогащенные и структурированные схемы
1.7.1 Классы обогащенных схем 
Выделяют следующие классы обогащенных схем: класс счетчиковых схем, класс магазинных схем, класс схем с массивами.
Классы счетчиковых и магазинных схем образован добавлением в базис ССП счетного множества счетчиков и магазинов с их интерпретированными операторами.
Счетчик — интерпретированная переменная, у которой областью значений является множество Nat; начальное значение счетчика равно 0.
Интерпретированные операторы имеют следующий вид:
c := c + 1 — оператор прибавления единицы;
c := c - 1  — оператор вычитания единицы;
c = 0 — условный оператор проверки равенства счетчика нулю.
При значении счетчика равном 0 оператор вычитания единицы не изменяет его, оно остается равным 0.
К интерпретированным операторам может быть добавлен оператор пересылки значения счетчика с2 := с1, который может быть получен при помощи стандартных операторов.

c2=0

0

1

0

0

1

б

start(x)

z:=x

p(x)

x:=g(z)
c1:=c1+1

y:=z
c1:=c1-1

stop(x)

x:=f(y,x)

y:=g(y)
c2:=c2-1

c2:=c1

1

0

0

1

1

0

start(x)

w:=x
v:=x

p(x)

x:=g(x)

y:=v
w:=g(w)
z:=w

stop(x)

x:=f(y,x)

p(z)

y:=g(y)
z:=g(z)

a

start(x)

p(x)

c=0

А[c]:=x
c:=c+1
x:=g(x)

c:=c-1
y:=А[c]
x:=f(y,x)

1

0

0

stop(x)

1

г

start(x)

p(x)

M=

M:=x
x:=g(x)

y:=M
x:=f(y,x)

1

0

0

stop(x)

1

в

p(w)

c1=0

1

Рисунок 1.10
Магазин — неинтерпретированная переменная сложной структуры. В процессе выполнения интерпретированной схемы состояние магазина — это конечный набор элементов (d1,d2,…,dn) из области интерпретации, где dn — верхушка магазина.
Интерпретированные операторы имеют следующий вид:
М := x — запись в магазин;
х := М — выборка из магазина;
М =  — условный оператор проверки пустоты магазина,
где М – магазин, х — обычная переменная. Первый оператор меняет состояние (d1,d2,…,dn) магазина М на состояние (d1,d2,…,dn+1), где dn+1 — значение переменной х. После выполнения этого оператора элемент dn+1 становится новой верхушкой магазина. Второй оператор присваивает переменной х значение, равное верхушке магазина, состояние которого меняется с (d1,d2,…,dn-1,dn) на (d1,d2,…,dn-1), при этом dn.1 становится новой верхушкой магазина. Если магазин М пуст, то применение второго оператора оставляет его пустым, а переменная х не меняет своего значения. Третий оператор— предикат проверки магазина на пустоту; если магазин пуст, то значение предиката М = 0 равно 1, в противном случае — 0.
Класс схем с массивами — это расширение класса счетчиковых схем за счет добавления счетного множества массивов и операторов над ними.
Массив — неинтерпретированная переменная сложной структуры. При выполнении интерпретированной схемы состояние массива — бесконечная последовательность (d1,d2,…,di,…) элементов из области интерпретациии.
Интерпретированные операторы имеют следующий вид:
А[c]:= x — запись в магазин;
х:= А[c] — выборка из магазина,
где А — массив, [c] — целое число, равное текущему значению счетчика с.
На рисунке 1.10. приведены четыре схемы: стандартная (а), счетчиковая (б), магазинная (в) и схема с массивами (г). Все они эквивалентны друг другу и рекурсивной схеме:
F(x), F(x)=if  p(x) then  x else f(x, F(g(x))).
1.7.2 Трансляция обогащенных схем
Диаграмма на рисунке 1.11 дает полную информацию о возможности трансляции одного класса схем в другой, классы имеют следующие обозначения:
Y — стандартные схемы;	Y(М) — магазинные схемы;	
Y(R) — рекурсивные схемы;	Y(А) — схемы с массивами;	
Y(с) — счетчиковые схемы;	Y(P) — схемы с процедурами.	

Y(M)

Y(R)

Y(P)

Y

Y(c)

Y(A)

Рисунок 1.11

Диаграмма показывает, что классы Y(М) и Y(А) являются универсальными в том смысле, что схемы всех других классов транслируемы в них. В то же время, в класс Y не транслируются схемы ни одного другого класса. Следует отметить, что класс Y(с) достигает полной мощности при количестве счетчиков не менее 2, т.е. класс Y(с) с одним счетчиком равномощен классу Y.
1.7.3. Структурированные схемы
Возрастающая сложность программ привлекает все большее внимание к проблемам технологии программирования. Технологические соображения заставили, в первую очередь, пересмотреть принципы организации программ, их структуру. Дейкстра первым высказался против неупорядоченного использования переходов на метки, которое может привести и фактически приводит к переусложнению структуры программы, затрудняющему ее понимание и декомпозицию на более простые фрагменты. Реализуя концепцию так называемого структурированного программирования, он предложил, в частности, отказаться от использования переходов и ограничиться более дисциплинирующими средствами управления вычислениями, такими, как условные операторы и операторы цикла. 
Класс cтруктурированных схем Y(S) определяется в том же (полном) базисе В, который был введен для ССП Y.
Различие между Y и Y(S) проявляется на уровне структур схем. Вместо специальных символов Y вводятся специальные символы: if , then, else, while, do, end. Вместо инструкций с метками вводятся три типа схемных оператора в базисе В: простой оператор, условный оператор и оператор цикла.
Простой оператор — это начальный (заключительный) оператор и оператор присваивания.
Условный оператор — это оператор вида
if   then  1 else 0 end,
где  — логическое выражение, 1 ,0 — последовательности (может быть, пустые) схемных операторов, среди которых нет ни начального, ни заключительного.
Операторы цикла имеют вид
while  do  end или until  do  end,
где , имеют тот же смысл, что и выше.
Ниже приведен пример эквивалентных схем Y и Y(S).
Стандартная схема программ
Y	Структурированная схема программ
Y(S)	
start(х),
1: y := f(x),
2: if  p(y) then  7 else 3,
3: y := f(y),
4: if  p(y) then 5 else 7,
5: if  p(x) then 6 else 7,
6: x := h(x) goto 5,
7: stop(х, y).	start(х),
y := f(x),
if  p(y) then  else
                      y := f(y),
                      if  p(x) then
                                  while p(x)
                                            do x := h(x) end
                     else 
                     end
end,
stop(х, y).	
Доказано, что класс Y мощнее класса Y(S), т.е. схемы Y(S) транслируемы в Y, но не наоборот.
Усилить класс Y(S) можно за счет усложнения логических выражений в условных операторах и операторах цикла Y(SL), введением символов логических операций NOT, OR, AND и атомарных формул, которыми являются логические выражения в старом смысле, например:
NOT p(x) AND q(y,x);
p(g(x, t)) OR q(h(x), x).
В этом случае справедлива 
Теорема (Ашкрофт - Манн) Класс стандартных схем Y транслируем в класс схем с логическими операциями Y(SL).