Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Непейвода Н.Н. -> "Основания программирования " -> 292

Основания программирования - Непейвода Н.Н.

Непейвода Н.Н., Скопин И.Н. Основания программирования — Институт компьютерных исследований , 2002. — 919 c.
Скачать (прямая ссылка): osnovanprogramm2002.pdf
Предыдущая << 1 .. 286 287 288 289 290 291 < 292 > 293 294 295 296 297 298 .. 316 >> Следующая

о2, о2 + 1,..., о2 + к, ... о2 + о, о2 + о + 1,..., о2 + о + к, ... о2 + 2 • о, ... о2 + n • о ... 2 • о2.
За всеми к • о2 + l • о + n стоит о3.
пять-таки продолая по всем натуральным числам, получаем всевозможные ординалы вида
кп • оо" + кп_і • оо"-1 + • • • + кіо + ко.
За ними идет ординал, обозначаемый ош .А за ним опять-таки цепочка его "сумм" со всеми предыдущими ординалами:
ош + кп • оо" + кп-1 • о"-1 + • • • + к1о + к0.
Аналогично, мы приходим к 2 • шш, и далее к n • шш. Законы сложения степеней сохраняются, и дальше идет оо"+1. Таким образом приходим к ординалам вида
Im • оГ+™ + 1m-1 • оГ+(т-1) + • • • + +
к" • оо" + к"_1 • о"-1 +-----+ к1 • о + ко.
А за ними идет ординал, который естественно обозначить о2ш. Продолжая данный процесс, мы приходим к ординалам вида
UJ
Lu'''
о n раз.
А за всеми этими башнями стоит ординал, который Г. Кантор назвал є0 и определил как наименьшее решение уравнения оа = а.
A.2. ВЫЧИСЛИТЕЛЬНЫЕ ИНТЕРПРЕТАЦИИ
839
орядок ундирован, если лбое линейно упорядоченное подмно ество чума является вполне упорядоченным. С конструктивной точки зрения важнее всего следующая особенность полных порядков.
Любая убывающая последовательность через конечное число
шагов стабилизируется.
§ A.2. ВЫЧИСЛИТЕЛЬНЫЕ ИНТЕРПРЕТАЦИИ
ля рассмотрения вычислительных интерпретаций программы абстрагируются до схем программ. Схема отличается от программы тем, что все конкретные понятия заменяются на абстрактные, например, вместо операции сложения x + y пишется двухместная функция f (x, y). Это позволяет сосредоточиться на обих аспектах того, что такое исполнение, что такое удача или неудача исполнения, что необходимо знать для того, чтобы исполнить программу. Заодно это позволяет исследовать общие свойства программ, не зависящие от примененных конкретных понятий, и общие их преобразования, что является самым ценным вкладом лбой теории в практику.
реде всего, мы видим, что кадая схема содерит некоторый набор переменных, функций и предикатов, которые в ней встреча тся. В соответствии с этим определим
Определение A.2.1. Словарь (сигнатура) а — тройка конечных множеств (X, F, P), где X — непустое множество, элементы которого называются переменными, F — множество функций (функциональных символов), P — множество предикатов (предикатных символов). Каждой функции и каждому предикату сопоставлено натуральное число n ^ 0, называемое их арностью. Если нужно явно указать арность функции, мы записываем fn, аналогично для предиката.
Термы задаются следующим индуктивным определением.
a) Переменная — терм.
b) Если fn — функция, U1, ..., tn — термы, то f (U1,..., Un) — терм.
Элементарная формула — выражение вида P (t1,..., tn), где Pn — предикат, U — термы.
Конец определения A.2.1.
Определение A.2.2. Схема программ словаря а — оснащенный ориентированный граф с вершинами пяти типов.
840
ПРИЛОЖЕНИЕ A. МАТЕМАТИЧЕСКИЕ МОДЕЛИ
1) Входная вершина помечена списком переменных, называемых входными данными схемы программ. Входная вершина в схеме одна. В нее не входит дуг.
2) Выходная вершина помечена списком переменных, называемых результатами схемы программ. Выходная вершина в схеме одна. Из нее не выходит дуг.
3) Функциональные вершины помечены присваиваниями вида
x t,
где x — переменная, t — терм.
4) Предикаты (называемые еще проверки, распознаватели или разветвления2) помечены элементарной формулой. Из предиката выходит две дуги, помеченные символами + и —.
5) В соединения входит несколько дуг. Соединения ничем не помечены.
6) Если количество входящих или выходящих дуг для вершины некоторого типа не указано, то оно равно 1.
Конец определения A.2.2.
Пример схемы программ можно посмотреть на рис. 3.3.
Определение A.2.3. Интерпретационная модель сигнатуры а — тройка m = (S, f, p), где
• S — непустое множество, называемоеуниверсом.ЪАы считаем, что оно обязательно содержит элемент ±, интерпретируемый как ошибка.
• f — отображение, сопоставляющее каждому функциональному символу fn Є F настоящую функцию f Lf J Є (Sn — S); функция должна удовлетворять условию корректности относительно ошибки: она равна ± тогда и только тогда, когда хотя бы один из ее аргументов равен
2 Последние два термина чаще употребляются в связи с недетерминированными схемами программ.
A.2. ВЫЧИСЛИТЕЛЬНЫЕ ИНТЕРПРЕТАЦИИ
841
• P — отображение, сопоставляющее каждому предикатному символу pn Є P отображение P LpJ Є (Sn — {true, false, ±|), удовлетворяю-ее услови корректности относительно оибки.
Конец определения A.2.3.
Чтобы определить исполнение программы, необходимо помимо интерпретационной модели задать оценку входных переменных 3: функцию, сопоста-вляу кадой входной переменной значение из S.
Определение A.2.4. Состоянием памяти схемы программ называется оценка переменных данной схемы программ. Состояние схемы программ — пара из верин и состояния памяти.
Исполнение E схемы программ — последовательность (конечная или бесконечная) пар (a^, Зі), где ai — вершины схемы, последовательность ai образует путь в схеме, и пары удовлетворя т следуим условиям:
Предыдущая << 1 .. 286 287 288 289 290 291 < 292 > 293 294 295 296 297 298 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100