Завершаемость является простым понятием, когда мы применяем его к программе, написанной на традиционном детерминистском языке: такая программа предлагает только одно возможное вычисление ( после того как входные данные, если они имеются, уже определены), и ее исполнение завершается в том и только том случае, когда это вычисление конечное. [1]
Завершаемость исполнения ( Р, G, С) программы 29 устанавливается здесь с помощью неформальных рассуждений. Рассмотрим произвольное вычисление Г, которое логически определяется этой программой. Оно начинается с активации вызова вида подмнож ( si, s2), где s2 — терм, не содержащий переменных. В этом случае следующим активируется вызов процедуры пустое и мы предполагаем, что эта встроенная процедура всегда обрабатывает подобный вызов за конечное время. [2]
Свойство универсальной завершаемости ( нетеровость): не существует терма, имеющего бесконечную последовательность редукций. [3]
Под свойствами завершаемости здесь понимаются свойства активности или образования тупика. Поскольку эта задача для обычных сетей Петри является еще не решенной, то Льен исследовал эту задачу для сетей Петри, которые являются свободными от конфликтов и не содержащими параллельных действий. [4]
Частичная и тотальная корректность программы
Представляет интерес свойство завершаемости метода резолюций : конечное множество S невыполнимо тогда и только тогда, когда пустой дизъюнкт может быть выведен из S с помощью резолюций. Из-леммы 1.3 следует достаточность этого условия. Пустой дизъюнкт, будучи невыполнимым, не может быть логическим следствием из выполнимого множества дизъюнктов. [5]
Написание самой программы и доказательство ее завершаемости за конечное число шагов оставляется читателю. [6]
Точно так же невозможно придумать никакого надежного теста, позволяющего определять завершаемость логических алгоритмов . Возможности исследования этого вопроса с помощью каких-либо методов доказательства теорем, основанных на ха-рактеризации конечности пространства вычислений, могут быть ограничены в зависимости от того, как сформулированы интересующие нас свойства, пределами разрешимости логики либо первого, либо второго порядка. То же самое подтверждается и тем фактом, что каждый логический алгоритм может быть представлен некоторой машиной Тьюринга, ибо, как хорошо известно, вопрос о завершаемости таких алгоритмов ( проблема остановки) является только полуразрешимым. [7]
При традиционном подходе к доказательству правильности программ было принято включать условие завершаемости в определение полной правильности. [8]
Разрешимость, конечно же, не имеет никакого отношения к обычному понятию завершаемости , которое указывает на окончание всего процесса исполнения программы за конечное время. Именно возможная недетерминированность логических программ лежит в основе невозможности их верификации в точном соответствии с методами доказательства правильности традиционных программ. [9]
Этот критерий включает в себя возможность доказательства полноты описаний, отсутствия неоднозначности, анализ свойств развития и завершаемости , а также согласованности различных спецификаций. Как известно из теории автоматов, конечный автомат наиболее удобен для анализа, тогда бак машина тьюринга требует сложных методов, а некоторые задачи анализа выводят их для нее в класс неразрешимых. Поэтому описательная мощность и анализируемость должны рассматриваться совместно для достижения приемлемого между ними соотношения. [10]
Реальность разработки программного обеспечения | #программирование #js #react
До сих пор, однако, предпринималось слишком мало исследований, направленных на разработку систематических методов доказательства завершаемости логических алгоритмов . [11]
Операции над высказывательными формами
Конъюнкцией высказывательных форм Ф1 и Ф2 называется высказывательная форма, истинная при тех и только при тех значениях входящих в неё переменных, которые обращают обе формы в истинное высказывание.
Дизъюнкцией высказывательных форм Ф1 и Ф2 называется высказывательная форма, ложная при тех и только при тех значениях входящих в неё переменных, которые обращают обе формы в ложное высказывание.
Отрицанием высказывательной формы Ф называется высказывательная форма, ложная при тех наборах значений переменных, которые обращают высказывательную форму в истинное высказывание и наоборот.
Импликацией высказывательных форм Ф1 и Ф2 называется высказывательная форма Ф1 Ф2, ложная при тех и только при тех значениях входящих в неё переменных, которые обращают Ф1 в истинное высказывание, а Ф2 — в ложное.
Кванторы
Выражение «для всякого x» называется квантором общности по переменной x и записывается следующим образом: x.
Запись x(Ф(x)) означает, что для всякого значения x высказывание Ф(x) истинно.
Выражение «существует x такое, что. » называется квантором существования по переменной x и обозначается так: x.
Запись x(Ф(x)) означает: «cуществует значение x такое, что Ф при этом значении является истинным высказыванием».
Метод индуктивных утверждений
Общие сведения
Верификация ПО заключается в выполнении формального доказательства того, что ПО удовлетворяет своим спецификациям.
Общими для различных методов верификации ПО является представление программ в виде схемы алгоритма, с каждой дугой которой соотносится некоторый предикат, называемый утверждением (Рис. 5 .1).
Рис. 5.1. Пример фрагмента схемы алгоритма с предикатами
Если Pi есть утверждение, связанное с входящей дугой оператора V, а Pj – утверждение, связанное с исходящей дугой того же оператора, то тогда необходимо доказать правильность следующего оператора: если Pi истинно и если оператор V выполнен, то утверждение Pj истинно. Такие теоремы имеют следующий вид: Pi→Pj.
Обычный метод их доказательства сводится, например, к тому, чтобы показать, что Pj истинно всякий раз, когда Pi истинно, т.е. для доказательства всей теоремы необходимо доказать, например, истинность Pj. Подобный процесс может быть повторен для каждого оператора программы.
На рис. 5.2 приведена схема алгоритма некоторой программы с предикатами P1 и Pn
Рис. 5.2. Пример схемы-алгоритма некоторой программы с предикатами
На данном рисунке P1 – утверждение, непосредственно предшествующее входному оператору программы (начальное утверждение), а Pn – утверждение, соответствующее выходному оператору программы (конечное утверждение).
Тогда оператор «если P1 истинно и программа выполнена, то Pn истинно», представляет собой теорему, доказательство которой устанавливает правильность того, что ПО соответствует своим спецификациям (т.е. теорема имеет вид P1→Pn). Таким образом, доказательство правильности программ сводится к доказательству теорем методами исчисления предикатов.
Одним из известных методов доказательства правильности программ является метод индуктивных утверждений, предложенный Флойдом.
Алгоритмы и исполнители. Свойства алгоритмов (дискретность, завершаемость, массовость и др.).
• Алгоритм – это точная, однозначная, конечная последовательность действий, которую должен выполнить пользователь для достижения конкретной цели либо для решения конкретной задачи или группы задач за конечное число шагов..
• Этимология слова алгоритм происходит от имени арабского математика Аль-Хорезми (точнее – латинизи-рованной формы его имени – Аlgorithmi), который еще в IX веке сформулировал правила выполнения четырех арифметических действий. Эти правила называли правилами Аль-Хорезми (algorithmi), а позднее просто стали называть алгоритмом.
• АЛГОРИТМ всегда связан с понятиями ИСПОЛНИТЕЛЯ и ДАННЫХ.
• Данные – исходные и промежуточные. Любые элементы какого-либо конечного множества (всё что представимо в цифровом виде). Сам Текст программы – это исходные данные для транслятора.
• Исполнитель – «обратная сторона» алгоритма. Субъект, который может воспринимать и выполнять определённый набор команд над определённым набором объектов. Система Исполнитель – Команды (действия) – Объекты (данные) – называют средой исполнителя.
• Конечный автомат – простейший исполнитель. Имеет конечное число различных внутренних состояний и переходов между ними (команд).
Свойства алгоритмов:
1. Дискретность – описываемый процесс должен быть разбит на последовательность отдельных простых шагов. Время выполнения каждого простого шага определенно и конечно во времени.
2. Элементарность – объём работы на каждом простом шаге ограничен сверху константой, которая зависит от исполнителя, но не зависит от входных данных.
3. Определенность – в каждый момент времени следующий шаг алгоритма однозначно следует из текущего состояния системы. Результат выполнения каждого шага (и алгоритма в целом) не зависит не от каких случайных факторов не предусмотренных алгоритмом.
4. Понятность – предписания алгоритма должны быть понятны конкретному исполнителю (соотносится с его системой команд).
5. Завершаемость – при конкретном наборе входных данных, алгоритм должен выдавать конкретный результат за конечное число шагов. Число шагов может зависеть от входных данных (не ограничено сверху).
6. Массовость – применимость алгоритма не к единственному набору данных, а ко множеству различных наборов данных. Если входные данные должны быть уникальны, то на выходе будет константа, следовательно действия сами по себе потеряют смысл.
ВОПРОС
Теория алгоритмов (задачи и примеры). Машина Тьюринга и машина Поста.
Тео́рия алгори́тмов — наука, изучающая общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления.
1. Определить (и доказать!) какие задачи являются алгоритмически разрешимыми, а какие таковыми не являются. Пример: алгоритм генерации простых чисел (без применения факторизации) – открытый и болезненный вопрос.
2. Асимптотический анализ алгоритмов – оценка того, как время выполнения алгоритма возрастает с увеличением объёма входных данных. Пример: сортировка методом пузырька VS сортировка Шелла.
3. Классификация алгоритмов и формирование критериев для оценки их качества. Пример: коэффициент Амдала – оценка эффективности параллельного выполнения кода.
Машина Тьюринга и машина Поста:
Машина Тьюринга – строгое математическое построение, абстрактный исполнитель. Абстрактная вычислительная машина, предложенная А. Тьюрингом в 1936 году. Представляет собой универсальный конечный автомат, который может имитировать другие исполнители.
Тезис Чёрча-Тьюринга – математическая функция, которая описывает поведение любого физического устройства, может быть вычислена машиной Тьюринга.
Физический смысл
1. Математический аппарат с конечным набором бесконечных лент (память неограничена), разделённых на ячейки
2. Управляющее устройство (автомат), который может находиться в одном из множестве состояний.
3. Головка для считывания записей (перемещается по управлением автомата).
Что дала модель Тьюринга?
1. Создала строгую математическую базу для исследования алгоритмов и исполнителей.
2. Указала направление развития вычислительной техники. Архитектура фон Неймана основана на машине Тьюринга.
3. Показала, что используя алгоритмы и данные, одна машина Тьюринга может имитировать другие машины (набор команд помещаются на ленту к данным).
4. Доказала, что любые алгоритмы (которые отвечают всем требованиям и облают всеми признаками), могут быть выполнены машиной Тьюринга.
5. Машины, которые могут имитировать машину Тьюринга называют полными по Тьюрингу. Реальные машины не могут, поскольку имеют ограниченную память.
Машина Поста – альтернативная математическая модель. Создана в 1937 г. американским математиком Э. Постем. От машины Тьюринга отличается большей простотой (всего 6 команд).
Отличие от машины Тьюринга
в ячейку ленты машины Тьюринга может быть записан любой символ некоторого конечного алфавита (определяется исходными данными) или «пустой» символ.
в ячейку ленты машины Поста могут быть записаны только два значения – 0 и 1.
Утверждения (тезисы) Поста
1. Машины Тьюринга и Поста эквивалентны (доказано)
2. Машина Поста может выполнить любой алгоритм (не опровергнуто).
3. Машина Поста является простейшей абстрактной машиной полной по Тьюрингу (условно доказано).
ВОПРОС
Источник: infopedia.su