ПОИСК Статьи Рисунки Таблицы Эквивалент комплекса j . 6. Эквивалентность комплексов из "Программирование " Последнее условие позволяет нам в качестве области задания п, т+/-оператора указывать не множество состояний всей памяти й, а множество состояний кортежа X (т. е. множество функций вида у = ф( ) определенных только для тех ячеек а, которые входят в X). В дальнейшем так и будем поступать, не оговаривая этого дополнительно. [c.135] Кортеж X называется входным, кортеж У—выходным, а кортеж Z — рабочим (или кортежем рабочих ячеек) для оператора Л(/). [c.135] Пример 5.2. При машинном истолковании понятий ячейки и состояния ячейки видно, что арифметические элементарные операторы программы являются п, т+/-операторами. Действительно, арифметический оператор программы имеет входной, выходной и рабочий кортежи ячеек. Являясь группой команд, он в зависимости от содержимого своих входных ячеек вырабатывает содержимое своих выходных и рабочих ячеек (условие 2). Содержи.мого ячеек, не принадлежащих его выходному или рабочему кортежам, он не меняет (условие 1). Его работа не зависит от содержимого ячеек, не являющихся для него входными (условие 3). При этом, конечно, сами ячейки, хранящие команды арифметического оператора, должны быть исключены из рассмотрения. [c.135] Определение п, -(-/-оператора не устанавливает различия между ячейками выходного и рабочего кортежей. Различие между ними будет установлено несколько ниже. [c.135] Нормальная последовательность с входным кортежем X и выходным кортежем К, рассматриваемая вместе с некоторым множеством О состояний кортежа X, называется комплексом, если произведение п, 14-0-операторов, изображением которого является нормальная последовательность, определено на О, т. е. если, как говорят, нормальная последовательность вычислима для любого входящего в О состояния кортежа X. Множество состояний О кортежа X называется областью задания комплекса. [c.137] Очевидно, комплекс является изображением некоторого т, Ж4-/-оператора, имеющего входной кортеж X, выходной кортеж У и рабочий кортеж Z= —У. [c.137] Пример 5.3. Арифметический оператор может быть записан в виде комплекса. При этом должно быть известно, в каких ячейках содержатся исходные данные для этого оператора и в каких ячейках будет получен результат. Областью задания, если она специально не указана, можно считать максимальное множество состояний входного кортежа, для которых нормальная последовательность комплекса вычислима. [c.137] Предположим, что исходные данные этого оператора размещены в ячейках 0040, 0041 и 0042, а результаты получаются в ячейках 0040 и 0062. [c.137] Областью задания комплекса можно считать множество тех состояний кортежа X, для которых выполнима операция 1 , присутствующая в предпоследней формуле нормальной последовательности. [c.138] Будем допускать комплексы, нормальные последовательности которых не содержат ни одной формулы. Для каждого такого комплекса должно выполняться условие У Х. При этом считается, что Л/=0 (где N—число формул в нормальной последовательности). [c.138] Выполним процесс, определяемый описанным ниже алгорифмом подстановок последовательно для к=1, 2,. .., М. Алгорифм подстановок 1°. Положить 2 = Л/. Перейти к п. 2°. [c.138] Легко видеть, что полученный столбец формул представляет собой нормальную последовательность с входным кортежем X и выходным кортежем V. [c.139] Нормальная последовательность (5.2) с входным кортежем X и выходным кортежем V, рассматриваемая вместе с О, представляет собой комплекс, который мы будем называть эквивалентом комплекса К и будем обозначать символом ЭК. [c.139] Предположим, кроме того, что пересечение Х -Х входных кортежей непусто и что для каждого состояния, принадлежащего одному из множества О и О , в другом из этих множеств найдется хотя бы одно состояние, совпадающее с ним на X X . [c.140] Выберем из правых частей формул нормальной последовательности (5.3) эквивалента ЭК все попарно между собой нетождественные функции О . Произведем аналогичный выбор функций Об, среди правых частей формул нормальной последовательности (5.4) эквивалента ЭК . [c.140] Прим ер 5. 4. Будем под ячейками понимать буквы, являющиеся обозначениями величин, а под состояниями ячеек — значения этих величин (т. е. числа). [c.141] Покажем, что KtК . [c.142] Вернуться к основной статье