Cтраница 1
Завершаемость является простым понятием, когда мы применяем его к программе, написанной на традиционном детерминистском языке: такая программа предлагает только одно возможное вычисление ( после того как входные данные, если они имеются, уже определены), и ее исполнение завершается в том и только том случае, когда это вычисление конечное. [1]
Завершаемость исполнения ( Р, G, С) программы 29 устанавливается здесь с помощью неформальных рассуждений. Рассмотрим произвольное вычисление Г, которое логически определяется этой программой. Оно начинается с активации вызова вида подмнож ( si, s2), где s2 - терм, не содержащий переменных. В этом случае следующим активируется вызов процедуры пустое и мы предполагаем, что эта встроенная процедура всегда обрабатывает подобный вызов за конечное время. [2]
Свойство универсальной завершаемости ( нетеровость): не существует терма, имеющего бесконечную последовательность редукций. [3]
Под свойствами завершаемости здесь понимаются свойства активности или образования тупика. Поскольку эта задача для обычных сетей Петри является еще не решенной, то Льен исследовал эту задачу для сетей Петри, которые являются свободными от конфликтов и не содержащими параллельных действий. [4]
Представляет интерес свойство завершаемости метода резолюций: конечное множество S невыполнимо тогда и только тогда, когда пустой дизъюнкт может быть выведен из S с помощью резолюций. Из-леммы 1.3 следует достаточность этого условия. Пустой дизъюнкт, будучи невыполнимым, не может быть логическим следствием из выполнимого множества дизъюнктов. [5]
Написание самой программы и доказательство ее завершаемости за конечное число шагов оставляется читателю. [6]
Точно так же невозможно придумать никакого надежного теста, позволяющего определять завершаемость логических алгоритмов. Возможности исследования этого вопроса с помощью каких-либо методов доказательства теорем, основанных на ха-рактеризации конечности пространства вычислений, могут быть ограничены в зависимости от того, как сформулированы интересующие нас свойства, пределами разрешимости логики либо первого, либо второго порядка. То же самое подтверждается и тем фактом, что каждый логический алгоритм может быть представлен некоторой машиной Тьюринга, ибо, как хорошо известно, вопрос о завершаемости таких алгоритмов ( проблема остановки) является только полуразрешимым. [7]
При традиционном подходе к доказательству правильности программ было принято включать условие завершаемости в определение полной правильности. [8]
Разрешимость, конечно же, не имеет никакого отношения к обычному понятию завершаемости, которое указывает на окончание всего процесса исполнения программы за конечное время. Именно возможная недетерминированность логических программ лежит в основе невозможности их верификации в точном соответствии с методами доказательства правильности традиционных программ. [9]
Этот критерий включает в себя возможность доказательства полноты описаний, отсутствия неоднозначности, анализ свойств развития и завершаемости, а также согласованности различных спецификаций. Как известно из теории автоматов, конечный автомат наиболее удобен для анализа, тогда бак машина тьюринга требует сложных методов, а некоторые задачи анализа выводят их для нее в класс неразрешимых. Поэтому описательная мощность и анализируемость должны рассматриваться совместно для достижения приемлемого между ними соотношения. [10]
До сих пор, однако, предпринималось слишком мало исследований, направленных на разработку систематических методов доказательства завершаемости логических алгоритмов. [11]
Мы показали, что программа правильна по отношению к входному и выходному утверждениям, но только если ее выполнение заканчивается. Нет общего метода доказательства завершаемости программ, но обычно бывает достаточно неформальных соображений. В нашем примере программа заканчивается только тогда, когда Y равно нулю. Согласно входному утверждению, значение Y первоначально неотрицательно, и изменяется только в одном месте: в цикле, где уменьшается по крайней мере на единицу при каждом его повторении. Таким образом, неформально устанавливается, что выполнение этой программы закончится. [12]
В литературе по верификации логических программ имеется некоторая терминологическая путаница, что может вызвать недоразумение у тех, кто не знаком с происходившими в процессе развития этой теории изменениями в определениях. В подходе Кларка и Тернлунда принимается стандартное понятие частичной правильности, однако, пытаясь достичь согласованности с понятиями из области доказательства правильности традиционных программ, в качестве дополнительного требования для определения полной правильности они выбирают завершаемость. [13]
Точно так же невозможно придумать никакого надежного теста, позволяющего определять завершаемость логических алгоритмов. Возможности исследования этого вопроса с помощью каких-либо методов доказательства теорем, основанных на ха-рактеризации конечности пространства вычислений, могут быть ограничены в зависимости от того, как сформулированы интересующие нас свойства, пределами разрешимости логики либо первого, либо второго порядка. То же самое подтверждается и тем фактом, что каждый логический алгоритм может быть представлен некоторой машиной Тьюринга, ибо, как хорошо известно, вопрос о завершаемости таких алгоритмов ( проблема остановки) является только полуразрешимым. [14]
Если выбрать для v ( Rt - / С) значения, не встречающиеся в г ( Rt), то никакие ключи в Rt ье будут нарушены. Затем v растягивается с помощью новых помеченных неопределенных значений и становится частичной строкой v над U. Теперь необходима осторожность: после изменений в t имеем t ( Rt) v ( Rt) к в v есть отличающиеся помеченные неопределенные значения на U - Ri. Удаляем v, чтобы обеспечить завершаемость процесса прогонки. [15]