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

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

некоторые системы СЛУЧАЯ производят программы, более поддающиеся доказательствам, чем другие - но снова, это полагается на формальную семантику спецификации...

... и поэтому как Вы доказываете корректную спецификацию?Правильно! С большим количеством спецификаций!

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

эти коды операций "атомарные истины"? Например, на наблюдении...

mov ax,1

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

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

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

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

, Как Вы доказываете Picasso?

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

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

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

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

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

И это - просто некоторые...

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

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

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

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

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

необходимо считать Dijsktra Дисциплина А Программирования .

Затем необходимо считать Gries Наука о Программировании .

Затем, Вы будете знать, как доказать корректные программы.

Просто маленький комментарий тем, кто поднял неполноту - она не имеет место для весь аксиоматические системы, только достаточно мощные .

, Другими словами, Гедель доказал, что аксиоматическая система, достаточно мощная для описания себя, обязательно будет неполной. Это не означает, что было бы бесполезно однако, и поскольку другие связались с, различные попытки доказательств программы были предприняты.

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

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

Можно на самом деле записать доказуемо корректные программы. Microsoft, например, создала расширение языка C#, названного Spec#, который включает автоматизированную программу автоматического доказательства теоремы. Для Java, существует ESC/java . Я уверен, что там существует намного больше примеров.

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

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

Если Вы действительно интересуетесь темой, позвольте мне сначала рекомендовать David Gries "Науку о Программировании", классическая вводная работа над темой.

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

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

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

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

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

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

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

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

, Что Вы подразумеваете под "программами" так или иначе?

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

ОПИСЫВАЮТ. Математика не объясняет, почему из вещей она просто рисует изображение как. Я не могу доказать Вам, что солнце поднимется завтра на Востоке, но я могу показать данные, где оно делало ту вещь на прошлом.

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

, Ожидают? Вы не МОЖЕТЕ? http://en.wikipedia.org/wiki/Algorithm#Algorithmic_analysis

я не могу показать Вам "истину" я программа так, как я не могу показать Вам "истину" на языке. Оба - представления нашего эмпирического понимания мира. Не на "истине". Откладывание всего мусора, я могу продемонстрировать Вам математически, что сортировка с объединением algorith отсортирует элементы в списке с O (nlogn) производительность, что Dijkstra найдет кратчайший путь на взвешенном графике, или что алгоритм Euclid найдет Вас наибольшим общим делителем между двумя числами. "Истина в моей программе" в том последнем случае, возможно, что я найду Вас наибольшим общим делителем между двумя числами, разве Вы не думаете?

С уравнением повторения я могу формировать рисунок Вам, как Ваша программа Fibonacci работает.

Теперь, действительно ли программирование является искусством? Я уверенный думаю, что это. Так же как математика.

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

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

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

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

я рекомендовал бы разыскать классика" Никакая Серебряная пуля " статья Brooks.

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

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

Такие языки включают: B, Событие B, Ada, Фортран.

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

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

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

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

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

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

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

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

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

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

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

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

    <ул.> <литий>, Который затем необходимо доказать, то, что они действительно хотят , потому что, будучи пользователем, они почти наверняка не знают то, что они хотят. и т.д. Доведение до абсурда.

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

Hope это помогает Вам на Вашем пути.

Что-то, что не было упомянуто здесь, B - Метод , который является формальной основанной на методе системой. Это использовалось для разработки системы безопасности Парижа под землей. Существуют инструменты, доступные для поддержки разработки B и События B, особенно Rodin.

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

у меня есть TA'ed курс, названный основанным на контракте Программированием (домашняя страница курса: http://www.daimi.au.dk/KBP2/ ). Здесь, что я могу экстраполировать от курса (и другие курсы я взял)

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

режим выполнения был бы списком пар (имя переменной, значение переменной). Читайте "{1 квартал} 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 в {}'s на самом деле был бы операторами о состояниях, не самих состояниях.

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

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

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

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

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

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

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

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

Но это не так проблематично,

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

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

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

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

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

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

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

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

I haven't read all of the answers, but the way I see it, proving programs is pointless, that's why no one does it.

If you have a relatively small/medium project (say, 10K lines of code), then the proof is probably gonna be also 10k lines, if not longer.

Think about it, if the program can have bugs, the proof can also have "bugs". Maybe you'll need a proof for the proof!

Another thing to consider, programs are very very formal and precise. You can't get any more rigorous and formal, because the program code has to be executed by a very dumb machine.

While proofs are going to be read by humans, so they tend to be less rigorous than the actual code.

The only things you'll want to prove are low-level algorithms that operate on specific data structures (e.g. quicksort, insertion to a binary tree, etc).

These things are somewhat complicated, it's not immediately obvious why they work and/or whether they will always work. They're also basic building blocks for all other software.

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

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