Рябь - Rippling

Рябь^[1] относится к группе метауровня эвристика, разработанная в основном в группе математического мышления в школе информатики Эдинбургский университет, и чаще всего используется для направления индуктивные доказательства в автоматизированные системы доказательства теорем. Рябь можно рассматривать как ограниченную форму переписать систему, где специальные аннотации на уровне объектов используются для обеспечения удобрения после завершения перезаписи, при этом требования к уменьшению меры обеспечивают завершение для любого набора правил перезаписи и выражения.

История

Раймонд Обен был первым, кто использовал термин «выплескивание», когда работал над своей докторской диссертацией 1976 года.^[2] в Эдинбургском университете. Он распознал общую схему движения на этапе переписывания индуктивных доказательств. Алан Банди позже перевернул эту концепцию с ног на голову, определив рябь как образец движения, а не как побочный эффект.^{[нужна цитата ]}

С тех пор были придуманы термины «колебание вбок», «колебание внутрь» и «колебание в прошлом», поэтому термин был обобщен как «колебание».^{[нужна цитата ]} С 2007 года рябь продолжает развиваться в Эдинбурге и других местах.

Рябь применялась ко многим проблемам, которые традиционно считались сложными в сообществе индуктивных доказательств теорем, включая Bledsoe предельные теоремы^{[нужна цитата ]} и доказательство микропроцессора Gordon,^{[нужна цитата ]} миниатюрный компьютер, разработанный Майкл Дж. С. Гордон и его команда в Кембридже.

Обзор

Очень часто при попытке доказать утверждение нам дают исходное и целевое выражения, которые отличаются только включением нескольких дополнительных синтаксических элементов.

Это особенно верно в индуктивной доказательства, где в качестве данного выражения принимается индуктивная гипотеза, а целевое выражение - индуктивный вывод. Обычно различия между гипотезой и выводом незначительны, возможно, включение функции-преемника (например, +1) вокруг индукционной переменной.

В начале колебания определяются различия между двумя выражениями, известные как волновые фронты на языке пульсаций. Обычно эти различия не позволяют завершить доказательство, и их нужно «убрать». Целевое выражение аннотируется, чтобы различать волновые фронты (различия) и скелет (общая структура) между двумя выражениями. Специальные правила, называемые волновыми правилами, могут затем использоваться в прекращение способ манипулировать целевым выражением до тех пор, пока исходное выражение не будет использовано для завершения доказательства.

пример

Мы стремимся показать, что добавление натуральные числа является коммутативный. Это элементарное свойство, и доказательство проводится обычной индукцией. Тем не менее пространство поиска такого доказательства может стать довольно большим.

Как правило, базовый случай любого индуктивного доказательства решается другими методами, кроме ряби. По этой причине мы сконцентрируемся на случае шага. Наш случай шага принимает следующую форму, где мы решили использовать x в качестве переменной индукции:

У нас также может быть несколько правил перезаписи, взятых из лемм, индуктивных определений или других источников, которые можно использовать для формирования волновых правил. Предположим, у нас есть следующие три правила перезаписи:

затем они могут быть аннотированы, чтобы сформировать:

Обратите внимание, что все эти аннотированные правила сохраняют скелет (x + y = y + x в первом случае и x + y во втором / третьем). Теперь, аннотируя случай индуктивного шага, мы получаем:

И мы все настроены на рябь:

Обратите внимание, что окончательная переписывание приводит к исчезновению всех волновых фронтов, и теперь мы можем применить удобрение, применение индуктивных гипотез, чтобы завершить доказательство.

использованная литература

дальнейшее чтение

• Дэвид А. Бейсин и Тоби Уолш (1996). "Исчисление и прекращение ряби" (PDF). Журнал автоматизированных рассуждений. 16 (1–2): 147–180. Дои:10.1007 / BF00244462. S2CID  14427821.