Почему программы не могут быть доказаны?

Ответ 1

Доказательства являются программами.

Формальная проверка программ - огромная область исследований. (См., Например, группа в Carnegie Mellon.)

Были проверены многие сложные программы; например, см. это ядро, написанное в Haskell.

Ответ 2

Программы абсолютно могут быть доказаны как правильные. Отвратительные программы трудно доказать. Чтобы сделать это достаточно разумно, вам нужно разработать программу и проверить ее рука об руку.

Вы не можете автоматизировать доказательство из-за проблемы с остановкой. Однако вы можете вручную доказать пост-условия и предпосылки любого произвольного оператора или последовательности утверждений.

Вы должны прочитать Dijsktra Дисциплина программирования.

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

Затем вы узнаете, как правильно доказать правильность программ.

Ответ 3

Проблема с остановкой показывает, что есть программы, которые не могут быть проверены. Гораздо более интересным и более практичным является вопрос о том, какой класс программ может быть официально проверен. Может быть, каждая программа, которой кто-либо заботится, может (теоретически) быть проверена. На практике до сих пор были доказаны только очень маленькие программы.

Ответ 4

Небольшой комментарий для тех, кто воспитывает неполноту - это не относится ко всем аксиоматическим системам, только достаточно сильным.

Также очень интересна двойная проблема (написание программ для проверки доказательств).

Ответ 5

Фактически вы можете писать доказуемо правильные программы. Например, Microsoft создала расширение языка С#, называемое SpeС#, которое включает автоматическую проверку теоремы. Для java существует ESC/java. Я уверен, что есть еще много примеров.

(edit: видимо speС# больше не разрабатывается, но инструменты контракта станут частью .NET 4.0)

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

Ответ 6

Если вы действительно заинтересованы в этой теме, позвольте мне сначала порекомендовать Дэвида Гриса "Наука программирования", классическую вводную работу по этой теме.

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

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

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

Ответ 7

Во-первых, почему вы говорите, что "программы НЕ МОГУТ быть доказаны"?

Что вы подразумеваете под "программами"?

Если по программам вы имеете в виду алгоритмы, разве вы не знаете Крускала? Дейкстры? MST? Прима? Двоичный поиск? Сортировка слиянием? DP? Все эти вещи имеют математические модели, которые описывают их поведение.

ОПИСАНИЯ. Математика не объясняет, почему вещи просто рисуют картину того, как. Я не могу доказать вам, что Солнце восстанет завтра на востоке, но я могу показать данные, где он делал это в прошлом.

Ты сказал: "Если вы пишете компьютерную программу, как вы можете использовать предыдущие проверенные работы и использовать их, чтобы показать правду вашей программы? Вы не можете, так как не существует"

Подождите? Вы НЕ МОЖЕТЕ? http://en.wikipedia.org/wiki/Algorithm#Algorithmic_analysis

Я не могу показать вам "правду". Я программа настолько, насколько я не могу показать вам "правду" на языке. Оба являются представлениями нашего эмпирического понимания мира. Не на "правде". Поместив всю тарабарщину в сторону, я могу математически продемонстрировать вам, что алгоритм mergesort будет сортировать элементы в списке с производительностью O (nlogn), что Dijkstra найдет кратчайший путь на взвешенном графике или что алгоритм Евклида найдет вас наибольшим общий делитель между двумя числами. "Правда в моей программе" в последнем случае может быть, что я найду вам самый большой общий делитель между двумя числами, не так ли?

С рекуррентным уравнением я могу описать вам, как работает ваша программа Фибоначчи.

Теперь, компьютерное программирование искусства? Я уверен, что так оно и есть. Как математика.

Ответ 8

Я не из математического фона, поэтому простите мое невежество, но что означает "доказать программу"? Что вы доказываете? Правильность? Правильность - это спецификация, которую программа должна проверять как "правильную". Но эта спецификация определяется человеком, и как вы подтверждаете правильность этой спецификации?

На мой взгляд, в программе есть ошибки, потому что у людей возникают трудности с выражением того, чего они действительно хотят. alt text http://www.processdevelopers.com/images/PM_Build_Swing.gif

Итак, что вы доказываете? Ошибки, вызванные отсутствием внимания?

Ответ 9

Далее, каковы аксиомы программирования? Сама атомная истина поля?

У меня есть курс под названием Контрактное программирование (главная страница курса: http://www.daimi.au.dk/KBP2/). Здесь я могу экстраполировать курс (и другие курсы, которые я взял)

Вы должны формально (математически) определить семантику своего языка. Подумайте о простом языке программирования; который имеет только глобальные переменные, ints, int массивы, арифметические, if-then-else, while, assign и do-nothing [вы, вероятно, можете использовать подмножество любого основного языка как "реализацию" этого].

Состояние выполнения представляет собой список пар (имя переменной, значение переменной). Прочитайте "{Q1} S1 {Q2}" как "исполняющий оператор S1 выведет вас из состояния выполнения Q1 в состояние Q2".

Тогда одна аксиома будет "if both {Q1} S1 {Q2} and {Q2} S2 {Q3}, then {Q1} S1; S2 {Q3}". То есть, если оператор S1 перенесет вас из состояния Q1 в Q2, а оператор S2 перенесет вас из Q2 в Q3, тогда "S1; S2" (S1, за которым следует S2) перенесет вас из состояния Q1 в состояние Q3.

Другая аксиома будет "if {Q1 && e != 0} S1 {Q2} and {Q1 && e == 0} S2 {Q2}, then {Q1} if e then S1 else S2 {Q2}".

Теперь немного уточнения: Qn в {} будет фактически быть утверждениями о состояниях, а не о самих состояниях.

Предположим, что M (out, A1, A2) является оператором, который объединяет два отсортированных массива и сохраняет результат в out, и что все слова, которые я использую в следующем примере, были выражены формально (математически). Тогда "{sorted(A1) && sorted(A2)} A := M(A1, A2) {sorted(A) && permutationOf(A, A1 concatened with A2)}" - утверждение, что M корректно реализует алгоритм слияния.

Можно попытаться доказать это, используя приведенные выше аксиомы (возможно, вам понадобится несколько других. Вам, вероятно, понадобится цикл для одного).

Надеюсь, это иллюстрирует немного то, что может доказать правильность программ. И поверьте мне: для того, чтобы доказать их правильность, требуется много работы, даже для кажущихся простых алгоритмов. Я знаю, я много читал, -)

[если вы прочтете это: ваша ручная работа была прекрасна, все остальные вызвали у меня головные боли; -)]

Ответ 10

Конечно, они могут, как и другие, опубликовать.

Доказательство правильности очень маленькой подпрограммы - это хорошее упражнение, при котором ИМХО каждый студент в программной программе, связанной с программированием, должен требоваться. Это дает вам представление о том, как сделать код четким, легко просматриваемым и поддерживаемым.

Однако, в реальном мире это ограниченное практическое применение.

Во-первых, так же, как программы имеют ошибки, так же как и математические доказательства. Как доказать, что математическое доказательство действительно правильно и не имеет никаких ошибок? Вы не можете. А для встречного примера в любом количестве опубликованных математических доказательств были обнаружены ошибки, иногда спустя годы.

Во-вторых, вы не можете доказать, что программа правильная, не имея "априорно" однозначного определения того, что должна делать программа. Но любое однозначное определение того, что программа должна делать, - это программа. (Хотя это может быть программа на каком-то языке спецификаций, в которой у вас нет компилятора.) Поэтому, прежде чем вы сможете доказать, что программа верна, вы должны сначала иметь другую программу, которая эквивалентна и известна заранее чтобы быть правильным. Итак, QED все это бесполезно.

Я бы порекомендовал отслеживать классическую статью " No Silver Bullet" от Brooks.

Ответ 11

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

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

Такие языки включают: B, событие B, Ada, fortran.

И, конечно же, есть много инструментов, которые призваны помочь нам доказать некоторые свойства программ. Например, чтобы доказать тупиковую свободу, можно было хрустнуть их программу через SPIN.

Существует также множество инструментов, которые также помогают нам обнаруживать логические ошибки. Это можно сделать с помощью статического анализа (goanna, satabs) или фактического выполнения кода (gnu valgrind?).

Однако нет ни одного инструмента, который действительно позволял бы доказывать всю программу, начиная с момента создания (спецификации), реализации и развертывания. Метод B близок, но проверка его реализации очень слабая. (Он предполагает, что люди невероятны в переводе speicficaiton в импликацию).

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

Ответ 12

Они могут. Я провел много-много часов, когда первокурсник колледжа делал доказательства правильности программы.

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

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

Там есть знаменитая статья о программном обеспечении космического челнока. Они делают доказательства или что-то подобное. Это невероятно дорого и требует много времени. Этот уровень проверки может быть необходим для них, но для любого вида потребительской или коммерческой софтверной компании, с использованием современных технологий, вы получите свой обед, съеденный конкурентом, который поставляет решение на 99,9% при 1% стоимости. Никто не заплатит 5000 долларов за офис MS, который немного стабилен.

Ответ 13

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

Прежде всего, никакие доказательства не заменяют принятие приемочных испытаний: *

• Просто потому, что программа действительно делает то, что она говорит, но не означает, что она делает то, что пользователь хочет сделать.

  • Если вы не сможете доказать, что то, что он говорит, это то, что пользователь говорит, что они хотят.

    • Что вам нужно доказать, это то, чего они действительно хотят, потому что, будучи пользователем, они почти наверняка не знают, чего хотят. и т.д. Reductio ad absurdum.

* не говоря уже о модуле, охвате, функциональности, интеграции и других тестах.

Надеюсь, это поможет вам на вашем пути.

Ответ 14

Что-то, о чем здесь не упоминалось, это B - Method, который является системой, основанной на формальных методах. Он использовался для разработки системы безопасности парижского метрополитена. Существуют инструменты для поддержки разработки B и Event B, в частности Rodin.

Ответ 15

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

Ответ 16

Теоремы Годеля, невзирая на... Какой смысл? Какие упрощенные "истины" вы хотели бы доказать? Что бы вы хотели извлечь из этих истин? Хотя я могу есть эти слова... где практичность?

Ответ 17

Программы могут быть доказаны. Это спокойно, если вы пишете их на языке, таком как, например, стандартный ML Нью-Джерси (SML/NJ).

Ответ 18

Ваше выражение широко распространено, поэтому ловить много рыбы.

Суть в том, что некоторые программы определенно могут быть доказаны правильно. Все программы не могут быть доказаны правильно.

Вот тривиальный пример, который, разумеется, является тем же самым доказательством, который разрушил теорию множеств в тот же день: создайте программу, которая может определить, является ли она правильной, и если она считает, что она правильная, дайте неправильный ответ.

Это теорема Гёделя, простая и простая.

Но это не так проблематично, так как мы можем доказать много программ.

Ответ 19

Предположим чисто функциональный язык (например, Haskell). Побочные эффекты могут быть приняты на совершенно чистом учете на таких языках.

Доказывая, что программа создает правильный результат, вы должны указать:

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

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

Хорошей новостью является то, что "структура программ" (пункт 3 выше) и "структура математических множеств" весьма схожи (модное слово - топос или декартовая замкнутая категория), поэтому 1/доказательства, которые вы делаете математическая сторона будет легко перенесена в программные конструкции 2/программы, которые вы пишете, легко показывают, что они математически правильны.

Ответ 20

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

Ответ 21

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

• Для проверки требуется, чтобы все возможные ветки (вызовы, ifs и interupts) были пройдены, что в расширенном программном коде имеет суперкубитную временную сложность (следовательно, она никогда не завершится в разумные сроки).
• Некоторые методы программирования, либо путем создания компонентов, либо с помощью отражения, делают невозможным статическое прогнозирование выполнения кода (т.е. вы не знаете, как другой программист будет использовать вашу библиотеку, и компилятор с трудом предсказывает, как отражение в потребитель будет вызывать функциональность.

И это только некоторые...

Ответ 22

Далее, каковы аксиомы программирования? Сама атомная истина поля?

Являются ли opcodes "атомными истинами"? Например, видя...

mov ax,1

... не может программист утверждать как аксиоматический, что, запрещая аппаратную проблему, после выполнения этого оператора регистр CPU ax теперь будет содержать 1?

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

Тогда "предыдущая работа" может быть средой выполнения, в которой запускается новая программа.

Новая программа может быть доказана: помимо формальных доказательств она может быть проверена "путем проверки" и различными формами "тестирования" (включая "приемочные испытания" ).

Как вы доказываете Пикассо?

Если программное обеспечение больше похоже на промышленный дизайн или технику, чем на искусство, лучшим может быть вопрос "как вы докажете мост или самолет?"

Ответ 23

Если программа имеет четко определенные цели и исходные предположения (игнорируя Godel...), это может быть доказано. Найти все простые числа, x, для 6 <= x <= 10, ваш ответ равен 7, и это может быть доказано. Я написал программу которая воспроизводит NIM (первая программа Python, которую я когда-либо писала), и теоретически компьютер всегда выигрывает после того, как игра попадает в состояние в котором компьютер может выиграть. Я не смог доказать это как правду, но это правда (математически с помощью цифрового двоичного доказательства суммы). Я верю, если не сделаю ошибку в коде. Я сделал ошибку, не серьезно, может кто-нибудь сказать мне, является ли эта программа битой?

Существуют некоторые математические теоремы, которые были "доказаны" с компьютерным кодом, например, четырехцветная теорема. Но есть возражения, потому что, как вы сказали, вы можете доказать программу?

Ответ 24

подтверждение правильности программы может быть выполнено только по отношению к спецификации программы; это возможно, но дорогое/трудоемкое время

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

... и так как вы подтверждаете правильность спецификации? Правильно! С дополнительными характеристиками!

Ответ 25

Я немного читал об этом, но есть две проблемы.

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

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

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

Ответ 26

Как отмечали другие, действительно можно доказать (некоторые) программы.

Одна из проблем на практике состоит в том, что вам сначала нужно что-то (то есть предположение или теорема), которые вы хотите доказать. Поэтому, чтобы доказать что-то о программе, вам сначала нужно формальное описание того, что она должна делать (например, pre- и post-conditions).

Другими словами, вам нужна формальная спецификация программы. Но получение даже разумной (а тем более строгой формальной) спецификации уже является одним из самых сложных в разработке программного обеспечения. Поэтому, как правило, очень сложно доказать интересные вещи о (реальной) программе.

Однако есть некоторые вещи, которые могут (и были) более легко формализованы (и доказаны). Если вы можете хотя бы доказать, что ваша программа не будет разбиваться, это уже что-то: -).

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

Ответ 27

Я не читал все ответы, но, как я вижу, доказывание программ бессмысленно, почему никто этого не делает.

Если у вас относительно небольшой/средний проект (скажем, 10K строк кода), то доказательство, вероятно, будет также 10k строк, если не дольше.

Подумайте об этом, если в программе могут быть ошибки, в доказательстве также могут быть "ошибки". Возможно, вам понадобится доказательство для доказательства!

Другое дело, что программы очень формальны и точны. Вы не можете быть более строгим и формальным, потому что программный код должен выполняться очень тупой машиной.

Хотя доказательства будут прочитаны людьми, поэтому они имеют тенденцию быть менее строгими, чем фактический код.

Единственными вещами, которые вы хотите доказать, являются алгоритмы низкого уровня, которые работают с определенными структурами данных (например, quicksort, вставка в двоичное дерево и т.д.).

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

Ответ 28

Большинство ответов сосредоточено на практике, и это нормально: на практике вас не волнует формальная проверка. Но что теоретически?

Программы могут быть доказаны так же, как и математическое утверждение. Но не в том смысле, о котором ты говорил! В любой достаточно мощной структуре существуют математические утверждения (и программы), которые невозможно доказать! См. здесь

Ответ 29

Здесь так много шума, но я все равно буду кричать на ветру...

"Доказать правильно" имеет разные значения в разных контекстах. В формальных системах "доказать правильность" означает, что формула может быть получена из других доказанных (или аксиоматических) формул. "Доказать правильно" в программировании просто показывает код, эквивалентный формальной спецификации. Но как вы подтверждаете правильность формальной спецификации? К сожалению, нет возможности показать, что спецификация не содержит ошибок или решение любой реальной проблемы, кроме тестирования.

Ответ 30

Просто мои 2 цента, добавив к интересному материалу уже там.

Из всех программ, которые не могут быть доказаны, наиболее распространенными являются те, которые выполняют IO (некоторое непредсказуемое взаимодействие с миром или пользователями). Даже автоматические доказательства иногда просто забывают, что "проверенные" программы "работают на каком-то физическом оборудовании, а не идеальном, описанном моделью.

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