Структурная индукция
Cтраница 1
Структурная индукция может быть использована при доказательстве свойств рекурсивных программ. [1]
Структурная индукция может быть использована для доказательства свойств функций на рекурсивных типах данных. [2]
Структурную индукцию можно применять для доказательства многих свойств рекурсивно-определенных функций, и, хотя способы доказательств не являются центральной темой книги, структурной индукцией мы будем пользоваться и в некоторых последующих главах. На самом же деле доказательства по индукции идут бок о бок с рекурсивными функциями: когда для написания программы используется рекурсия, то для обоснования ее свойств следует применять индукцию. [3]
 |
Виды индукции. [4] |
Другое направление, структурная индукция, связано с использованием логик. [5]
Этот принцип называется структурной индукцией. Ьп часто могут являться конструкторами с отсутствующими аргументами, например nil в случае со списками, но в общем случае они могут быть и конструкторами, применимыми к другим типам, отличным от D, если так, то этап базового случая в любом индуктивном доказательстве будет более сложным. [6]
Итак, с помощью структурной индукции доказано, что функция Join является ассоциативной. [7]
Структурную индукцию можно применять для доказательства многих свойств рекурсивно-определенных функций, и, хотя способы доказательств не являются центральной темой книги, структурной индукцией мы будем пользоваться и в некоторых последующих главах. На самом же деле доказательства по индукции идут бок о бок с рекурсивными функциями: когда для написания программы используется рекурсия, то для обоснования ее свойств следует применять индукцию. [8]
По существу этот закон эквивалентен уравнению рекурсивного определения reverse и вместе с законом reverse ( nil) nil мог бы использоваться в качестве альтернативной формулировки. Тем не менее можно строго вывести это утверждение из рекурсивных уравнений, определяющих и reverse, используя только примитивные шаги преобразования и структурную индукцию по списку А следующим образом. [9]
Индукция обеспечивает возможность перехода от единичных фактов к общим положениям, законам. Бэкона, который впервые попытался формализовать индуктивные выводы посредством таблиц причин. Бэкон явился родоначальником исследований эмпирической структурной индукции, целью которой является обнаружение эмпирических зависимостей в виде индуктивных обобщений, полученных на основе сравнения объектов, имеющих структуру и входящих в явления, которые представляются примерами и контрпримерами. Бэкона об индукции было развито Д. С. Миллем, который предложил свои известные методы сходства, различия, остатков и сопутствующих изменений. [10]
Только что был приведен пример, показывающий, каким образом пишутся рекурсивные программы для не очень сложной задачи, причем программы обрабатывают смешанные типы данных простым написанием одного уравнения для каждой конструкции аргумента типа данных. Такая техника доказательств называется структурной индукцией, поскольку процесс индукции проводится на синтаксической структуре функционального выражения. [11]
С помощью таких же рассуждений, как и выше, можно показать, что рекурсивные вызовы процедуры Р2 не могут продолжаться бесконечно долго. Итак, мы доказали, что все вызовы процедур пустое, е и подмнож должны обрабатываться за конечное время. Отсюда вытекает, что вычисление Г обязано быть конечным. Этот вывод имеет место для всех вычислений Г, и, стало быть, полное пространство вычислений нашей программы конечно. Следовательно, исполнение программы 29 при стандартной стратегии управления или при любой другой исчерпывающей стратегии завершается. Доказательство завершаемости можно без труда провести более формально с помощью структурной индукции. [12]
Страницы: 1