Анализ прекращения - Termination analysis

пустота ж(int п) { пока (п > 1) если (п % 2 == 0) п = п / 2; еще п = 3 * п + 1;}

По состоянию на 2020 год пока неизвестно ли это C -программа завершается для каждого входа; видеть Гипотеза Коллатца.

В Информатика, анализ прекращения является программный анализ который пытается определить, действительно ли оценка данного программа останавливается на каждый Вход. Это означает определение того, вычисляет ли входная программа общий функция.

Это тесно связано с Проблема с остановкой, который должен определить, останавливается ли данная программа на данный ввод и который неразрешимый. Анализ завершения даже сложнее, чем проблема остановки: анализ завершения в модели Машины Тьюринга поскольку модель программ, реализующих вычислимые функции, будет иметь цель решить, является ли данная машина Тьюринга общая машина Тьюринга, и эта проблема находится на уровне ${displaystyle Pi _{2}^{0}}$ из арифметическая иерархия и, таким образом, является более сложной задачей, чем проблема остановки.

Теперь, поскольку вопрос о том, является ли вычислимая функция тотальной, не является полуразрешимый ^[1], каждый звук анализатор завершения (т. е. положительный ответ никогда не дается для незавершенной программы) неполный, т. е. должен не определять завершение для бесконечного числа завершающихся программ, либо из-за бесконечного выполнения, либо из-за остановки с неопределенным ответом.

Доказательство прекращения

А доказательство прекращения это тип математическое доказательство что играет решающую роль в формальная проверка потому что полная правильность из алгоритм зависит от прекращения.

Простой общий метод построения доказательств завершения включает в себя привязку мера с каждым шагом алгоритма. Мера берется из области определения обоснованные отношения, например, из порядковые номера. Если мера «уменьшается» в соответствии с отношением на каждом возможном шаге алгоритма, она должна прекратиться, потому что нет бесконечные нисходящие цепочки в отношении обоснованного отношения.

Некоторые типы анализа расторжения могут автоматически генерировать или предполагать наличие доказательства расторжения.

Пример

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

я: = 0петля пока i = SIZE_OF_DATA process_data (data [i])) // обрабатываем блок данных в позиции i    я: = я + 1 // переход к следующему блоку данных для обработки

Если значение SIZE_OF_DATA неотрицательный, фиксированный и конечный, цикл в конечном итоге завершится, если обрабатывать данные тоже заканчивается.

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

я: = 1петля пока i = 0 i: = i + 1

При анализе завершения можно также попытаться определить поведение завершения некоторой программы в зависимости от неизвестного ввода. Следующий пример иллюстрирует эту проблему.

я: = 1петля пока i = НЕИЗВЕСТНО i: = i + 1

Здесь условие цикла определяется с использованием некоторого значения UNKNOWN, где значение UNKNOWN неизвестно (например, определяется вводом пользователя при выполнении программы). Здесь анализ завершения должен учитывать все возможные значения UNKNOWN и выяснять, что в возможном случае UNKNOWN = 0 (как в исходном примере) завершение не может быть показано.

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

На практике не удается показать завершение (или незавершение), потому что каждый алгоритм работает с конечным набором методов, способных извлечь соответствующую информацию из данной программы. Метод может смотреть, как изменяются переменные относительно некоторого условия цикла (возможно, показывая завершение этого цикла), другие методы могут пытаться преобразовать расчет программы в некую математическую конструкцию и работать над этим, возможно, получая информацию о поведении завершения из некоторые свойства этой математической модели. Но поскольку каждый метод способен «видеть» только некоторые конкретные причины (не) прекращения, даже путем комбинации таких методов нельзя охватить все возможные причины (не) прекращения.^{[нужна цитата ]}

Рекурсивные функции и циклы эквивалентны по выражению; любое выражение, включающее циклы, может быть записано с использованием рекурсии, и наоборот. Таким образом завершение рекурсивных выражений также неразрешима вообще. Большинство распространенных рекурсивных выражений (т. Е. Не патологический ) можно показать, что он завершается различными способами, обычно в зависимости от определения самого выражения. Например, аргумент функции в рекурсивном выражении для факториал функция ниже всегда будет уменьшаться на 1; посредством в хорошем состоянии из натуральные числа, аргумент в конечном итоге достигнет 1, и рекурсия прекратится.

функция факториал (аргумент в качестве натуральное число) если аргумент = 0 или же аргумент = 1 возвращаться 1    иначе        возвращаться аргумент * факториал (аргумент - 1)

Зависимые типы

Проверка завершения очень важна в зависимо типизированный язык программирования и системы доказательства теорем, такие как Coq и Агда. Эти системы используют Изоморфизм Карри-Ховарда между программами и доказательствами. Доказательства над индуктивно определенными типами данных традиционно описывались с использованием принципов индукции. Однако позже было обнаружено, что описание программы с помощью рекурсивно определенной функции с сопоставлением с образцом является более естественным способом доказательства, чем использование принципов индукции напрямую. К сожалению, разрешение неограниченных определений приводит к логической несогласованности в теориях типов.^{[нужна цитата ]}. Поэтому Агда и Coq имеют встроенные средства проверки завершения.

Типоразмеры

Один из подходов к проверке завершения в языках программирования с зависимой типизацией - это размерные типы. Основная идея состоит в том, чтобы аннотировать типы, по которым мы можем выполнять рекурсию, с помощью аннотаций размера и разрешать рекурсивные вызовы только для меньших аргументов. Типоразмеры реализованы в Агда как синтаксическое расширение.

Текущее исследование

Есть несколько исследовательских групп, которые работают над новыми методами, которые могут показать (не) прекращение. Многие исследователи включают эти методы в программы^[2] которые пытаются анализировать поведение завершения автоматически (без вмешательства человека). Постоянный аспект исследований - позволить использовать существующие методы для анализа поведения завершения программ, написанных на языках программирования "реального мира". Для декларативных языков вроде Haskell, Меркурий и Пролог, существует много результатов^[3][4][5] (в основном из-за сильной математической подготовки этих языков). Исследовательское сообщество также работает над новыми методами анализа поведения завершения программ, написанных на императивных языках, таких как C и Java.

Из-за неразрешимости проблемы остановки исследования в этой области не могут достичь полноты. Всегда можно придумать новые методы, которые обнаруживают новые (сложные) причины прекращения.

Смотрите также

• Анализ сложности - проблема оценки времени, необходимого для завершения
• Вариант петли
• Полное функциональное программирование - парадигма программирования, которая ограничивает диапазон программ теми, которые доказуемо завершаются
• Рекурсия Вальтера

Рекомендации

1. Роджерс-младший, Хартли (1988). Теория рекурсивных функций и эффективная вычислимость. Кембридж (Массачусетс), Лондон (Англия): MIT Press. п. 476. ISBN  0-262-68052-1.
2. Инструменты на termination-portal.org
3. Giesl, J. и Swiderski, S. и Schneider-Kamp, P. и Thiemann, R. Pfenning, F. (ed.). Автоматический завершающий анализ для Haskell: от переписывания терминов к языкам программирования (приглашенная лекция) (постскриптум). Изменение сроков и заявки, 17-е межд. Конф., РТА-06. LNCS. 4098. С. 297–312. (связь: springerlink.com ).
4. Параметры компилятора для анализа завершения в Mercury
5. http://verify.rwth-aachen.de/giesl/papers/lopstr07-distribute.pdf

Исследовательские работы по автоматическому анализу завершения программ включают:

• Кристоф Вальтер (1988). «Алгоритмы с ограниченным аргументом как основа для автоматизированных доказательств завершения». Proc. 9-е Конференция по автоматическому вычету. LNAI. 310. Springer. С. 602–621.
• Кристоф Вальтер (1991). «О доказательстве завершения алгоритмов машиной» (PDF). Искусственный интеллект. 70 (1).
• Си, Хунвэй (1998). "На пути к автоматизированному доказательству расторжения через Замораживание" (PDF). В Тобиас Нипков (ред.). Методы и приложения перезаписи, 9-й Междунар. Конф., РТА-98. LNCS. 1379. Springer. С. 271–285.
• Юрген Гисль; Кристоф Вальтер; Юрген Браубургер (1998). «Завершающий анализ функциональных программ». У В. Бибеля; П. Шмитт (ред.). Автоматическое удержание - основа для приложений (постскриптум). 3. Дордрехт: Kluwer Academic Publishers. С. 135–164.
• Кристоф Вальтер (2000). «Критерии прекращения действия». В С. Hölldobler (ред.). Интеллектика и вычислительная логика (постскриптум). Дордрехт: Kluwer Academic Publishers. С. 361–386.
• Кристоф Вальтер; Стефан Швейцер (2005). «Автоматизированный анализ прекращения для не полностью определенных программ» (PDF). У Франца Баадера; Андрей Воронков (ред.). Proc. 11-й Int. Конф. на Логика программирования, искусственного интеллекта и рассуждений (LPAR). LNAI. 3452. Springer. С. 332–346.
• Адам Копровски; Йоханнес Вальдманн (2008). «Арктическое прекращение ... ниже нуля». У Андрея Воронкова (ред.). Методы перезаписи и приложения, 19-я Международная конференция. Конф., РТА-08 (PDF). Конспект лекций по информатике. 5117. Springer. С. 202–216. ISBN  978-3-540-70588-8.

Системные описания автоматических инструментов анализа завершения включают:

• Гизл, Дж. (1995). «Генерация полиномиальных порядков для доказательств завершения (описание системы)». В Сян, Цзе (ред.). Методы перезаписи и приложения, 6-е Междунар. Конф., РТА-95 (постскриптум). LNCS. 914. Springer. С. 426–431.
• Ohlebusch, E .; Claves, C .; Марше, К. (2000). «TALP: Инструмент для окончательного анализа логических программ (описание системы)». В Bachmair, Лео (ред.). Методы перезаписи и приложения, 11-е Int. Конф., РТА-00 (сжатый постскриптум). LNCS. 1833. Springer. С. 270–273.
• Hirokawa, N .; Миддельдорп, А. (2003). "Tsukuba Termination Tool (описание системы)". В Nieuwenhuis, R. (ed.). Методы перезаписи и приложения, 14-я Int. Конф., РТА-03 (PDF). LNCS. 2706. Springer. С. 311–320.
• Giesl, J .; Thiemann, R .; Schneider-Kamp, P .; Фальке, С. (2004). «Автоматическое подтверждение расторжения с AProVE (описание системы)». В Ван Остром, В. (ред.). Методы перезаписи и приложения, 15-е Int. Конф., РТА-04 (PDF). LNCS. 3091. Springer. С. 210–220. ISBN  3-540-22153-0.
• Hirokawa, N .; Миддельдорп А. (2005). «Тирольский инструмент прекращения (описание системы)». В Giesl, J. (ред.). Изменение сроков и заявки, 16-е межд. Конф., РТА-05. LNCS. 3467. Springer. С. 175–184. ISBN  978-3-540-25596-3.
• Копровский, А. (2006). «TPA: прекращение действия подтверждено автоматически (описание системы)». В Pfenning, F. (ed.). Изменение сроков и заявки, 17-е межд. Конф., РТА-06. LNCS. 4098. Springer. С. 257–266.
• Marché, C .; Зантема, Х. (2007). «Прекращение конкурса (описание системы)». В Баадере, Ф. (ред.). Изменение сроков и заявки, 18-е межд. Конф., РТА-07 (PDF). LNCS. 4533. Springer. С. 303–313.

внешняя ссылка

• Завершающий анализ функциональных программ высшего порядка
• Список рассылки инструментов прерывания
• Прекращение конкурса - см. Марше, Zantema (2007) для описания
• Портал прекращения действия