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

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

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

У меня нет хороших ответов на вышесказанное. Но кажется, что программное обеспечение не может быть доказано, потому что это искусство, а не наука. Как ты докажешь Пикассо?

 Robert Gould26 янв. 2009 г., 01:31
Вопрос довольно пессимистичный, и в любом случае это неверное предположение
 A. Rex25 янв. 2009 г., 02:04
@ Mitch Wheat: Где @ 4thspace, если предположить, что все математические утверждения могут быть доказаны?
 Johnno Nolan25 янв. 2009 г., 17:57
Надеюсь, этот вопрос не закроется,
 4thSpace25 янв. 2009 г., 08:42
Спасибо, что указал на это, Митч.
 Mitch Wheat25 янв. 2009 г., 01:52
@ 4-е пространство: Годель доказал (!), Что в любой формальной системе аксиом существуют утверждения, для которых невозможно доказать их истинность или ложь. Вы делаете предположение, что все математические утверждения могут быть доказаны, что, к сожалению, не так.

Ответы на вопрос(30)

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

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

К таким языкам относятся: B, Event B, Ada, fortran.

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

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

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

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

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

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

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

 nicerobot25 янв. 2009 г., 17:50
Конечно, вы можете создать корректно доказуемую программу, но проблема остановки доказывает, что не существует общего решения для каждой программы, поэтому «программы не могут быть проверены».
 Noah Sussman18 мар. 2016 г., 19:21
Хотя в некоторых случаях вы можете доказать, что программа соответствует спецификации, нет способа доказать, что оба: 1)Спецификация правильно и 2) метод, используемый для проверки спецификациитакже верный. другие упоминали Годеля, но Витгенштейн также наблюдал это явление.
 ShreevatsaR25 янв. 2009 г., 23:53
nicerobot: Вы не понимаете. «Программы не могут быть доказаны» в том же смысле, что «теоремы не могут быть доказаны» - их невозможно доказатьвсе, Множество индивидуальных программМожно быть доказано так же, как многие отдельные теоремы могут быть доказаны.

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

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

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

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

если вы пишете их на языке, например, Standard ML из Нью-Джерси (SML / NJ).

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

 A. Rex25 янв. 2009 г., 02:11
Мне не нужно далеко ходить, чтобы найти примеры компьютеров, занимающихся теорией групп:cs.unm.edu/~mccune/otter/otter-examples/auto
 A. Rex25 янв. 2009 г., 02:10
Конечно,en.wikipedia.org/wiki/Prover9_theorem_prover может (автоматически) доказать, что sqrt (2) иррационально. Я посмотрю, смогу ли я найти определенный пример.
 timday25 янв. 2009 г., 11:57
ОК, честные комментарии. То, что существуют вещи, которые невозможно доказать, не означает, что каждый случай является неопределенным. Я должен знать это; Раньше я работал в микроэлектронике, и у нас была команда по формальным методам, которая отлично справилась с поиском сломанных конечных автоматов и потенциальных тупиков.
 A. Rex25 янв. 2009 г., 01:59
По этой логике мы не будем заниматься теорией чисел. Но я, другие люди, и компьютеры тоже.
 Sumudu Fernando25 янв. 2009 г., 05:24
Проект MIZAR - еще один достойный пример автоматизированной теории чисел, хотя он более полезен в качестве проверочного средства проверки.

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

Чтобы доказать, что программа дает правильный результат, вам необходимо указать:

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

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

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

Что вы подразумеваете под "программами" в любом случае?

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

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

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

Подождите? Вы не можете?http://en.wikipedia.org/wiki/Algorithm#Algorithmic_analysis

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

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

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

 Michael Foukarakis30 авг. 2010 г., 09:47
К сожалению, программы - это больше, чем алгоритмы. Очень тривиальная программа без прерывания может убедить вас в этом.
 user5156830 янв. 2009 г., 18:55
Хороший ответ, если слишком много махать рукой: D

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 Wouter van Nifterick20 июн. 2009 г., 21:14
Я также не понимаю, почему люди в корне превосходят компьютеры, когда дело доходит до доказательства правильности.
 A. Rex25 янв. 2009 г., 02:32
Позвольте мне свести это к одному вопросу: думаете ли вы, что мы, люди, можем доказать что-то (возможно, прекращение циклов), что компьютеры в принципе не могут, из-за проблемы остановки?
 A. Rex25 янв. 2009 г., 02:01
Люди как-то магически невосприимчивы к проблеме остановки? Конечно, вы можете автоматизировать доказательства ...
 S.Lott25 янв. 2009 г., 02:18
@A. Рекс: Если вы разрабатываете программу для остановки, вы можете доказать, действительно ли она останавливается. Для произвольных программ, не обязательно предназначенных для остановки, вы не можете доказать, останавливается ли она.
 Steven A. Lowe25 янв. 2009 г., 16:55
+1 для Дейкстры; -1 за глупый компьютер! = Человеческая дискуссия в комментариях; +1 за сговор по терминологии; -1 за потерю места для комментариев; +1 для Дейкстры ;-)

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

 Bill the Lizard25 янв. 2009 г., 19:41
@Kim: Первое предложение ответа Джона - именно то, что показывает проблема остановки. Может быть, вас смутил остальной его ответ, который ставит другой вопрос?
 S.Lott25 янв. 2009 г., 03:52
Я бы предложил сбросить «очень» и оставить на «маленький». Некоторые довольно сложные вещи были доказаны очень хорошо.
 Kim Stebel25 янв. 2009 г., 08:13
проблема остановки не показывает такой вещи
 Brian Postow03 мар. 2009 г., 23:21
Это не тот случай, когда каждая полезная программа может быть проверена. Я несколько раз хотел программы, которые в конечном итоге были эквивалентны HALT или более часто EQUIV (эквивалентны ли эти две программы), и, очевидно, они не могут быть проверены.
 S.Lott25 янв. 2009 г., 19:24
@Kim: интересный полукоммент. Если проблема с остановкой не показывает, что существует класс программ, которые не могут быть доказаны для остановки, то что это показывает?

на практике вас не интересуют формальные проверки. Но что в теории?

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

кто воспитал незавершенность - дело не в этомвсе только аксиоматические системыдостаточно мощный из них.

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

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

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

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

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

 Chris Broski08 дек. 2010 г., 21:07
Фред Брукс сказал это лучше: «Даже совершенная верификация программы может только установить, что программа соответствует ее спецификации. […] Большая часть сути построения программы на самом деле заключается в отладке спецификации».

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

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

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

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

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

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

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

 Matt R15 окт. 2009 г., 09:31
«Хотя доказательства будут читать люди, они, как правило, менее строгие, чем фактический код». - если они не являются проверяемыми машиной доказательствами.
 hasen15 окт. 2009 г., 10:50
Как вы доказываете правильность программы, которая проверяет доказательства? И как вы доказываете, что доказательство действительно доказывает, о какой программе идет речь, а не что-то еще?

Являются лиопкоды «атомные истины»? Например, увидев ...

mov ax,1

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

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

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

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

Как ты докажешь Пикассо?

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

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

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

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

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

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

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

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

 hasen07 мая 2009 г., 09:32
Что значит для этой программы быть правильной?
Решение Вопроса

находятся программы.

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

Многие сложные программы были проверены; например, увидеть этоядро написано на Хаскеле.

 Matt Flowers25 янв. 2009 г., 17:17
Мне удалось пройти всю мою карьеру в колледже и первые пару лет моей профессиональной карьеры, и почему-то я никогда не знакомился с этой удивительной областью. Спасибо за ссылки, это действительно интересный материал!

Я закончил курс под названием «Контрактное программирование» (домашняя страница курса:http://www.daimi.au.dk/KBP2/). Вот что я могу извлечь из курса (и других курсов, которые я прошел)

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

Состояние выполнения будет список пар (имя переменной, значение переменной). Прочитайте «{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 правильно реализует алгоритм слияния.

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

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

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

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

 David Thornley30 янв. 2009 г., 19:30
Вы говорите, что есть компилятор спецификации Coq. Как вы докажете, что ваша спецификация Coq верна?
 warren02 февр. 2009 г., 21:10
Похоже, в те дни, когда о Z говорили - обеспечение доказуемо правильной программы было на самом деле легкой задачей, это доказывало, что строитель был правильным
 Jay Kominek30 янв. 2009 г., 20:19
Нет, я не это сказал. Хотя вы должны дать Coq спецификацию, этого недостаточно. Он также нуждается в конструктивном доказательстве (которое может помочь вам построить), а затем дает правильную программу. Вы должны предоставить доказательство. Вам просто не нужно переводить это в программу, и вы рискуете ошибками.

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

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

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

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

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

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

 Steven Evers30 янв. 2009 г., 18:50
Если программа может быть подтверждена как правильная, то можно доказать, что она удовлетворяет всем требованиям, перечисленным в документе с требованиями. Я бы сказал, что многие подрядчики хотели бы иметь возможность сделать это.
 A. Rex25 янв. 2009 г., 02:21
Так люди не умирают?en.wikipedia.org/wiki/Therac_25
 Jason Punyon♦25 янв. 2009 г., 02:41
Нет ... они делают. Но программное доказательство не помогло бы им ... (AECL не учитывала дизайн программного обеспечения во время оценки того, как машина может дать желаемые результаты и какие существуют режимы отказа).
 Dan Dyer25 янв. 2009 г., 02:04
Я бы предположил, что мотивация состоит в том, чтобы доказать, что программа правильная, что было бы весьма полезно.
 A. Rex25 янв. 2009 г., 02:51
Дело остается тем не менее. Если вы находитесь в сценарии высокого риска (люди умирают, потеря миллиардов долларов), то доказательство правильности было бы неплохо. Я предполагаю, что это одна из причин, по которой НАСА вкладывает средства в исследования по проверке.

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

 Johnno Nolan25 янв. 2009 г., 23:27
Ах да, пропустил, что А.Рекс спасибо.
 A. Rex25 янв. 2009 г., 18:02
stackoverflow.com/questions/476959/... упоминает Б, но я бы все же оставил ваш комментарий, что касается упоминания Метро и Родена. знак равно

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

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

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

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

Я бы порекомендовал выследить классикаНет серебряной пулистатья Брукса.

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

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

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

 Don Hatch18 февр. 2018 г., 05:59
Это комментарий, а не ответ.
 Nils07 мая 2009 г., 09:38
Это классический «рисунок пузыря», который был частью некоторых утомительных курсов по управлению проектами, которые я должен был пройти. Я думал, что вопрос заключается в том, чтобы доказать, что какой-то алгоритм делает то, что он должен делать, а НЕ спорить с заказчиком о функциях
 pyon30 янв. 2009 г., 08:36
Не могу согласиться больше. Немного не по теме: я уже видел эту картину на слайдах профессора, который читает лекции по внедрению SAP в моем колледже.
 Samy Bencherif28 нояб. 2016 г., 20:39
@NicolasDorier Чтобы доказать, что программа означает, что она соответствует спецификации для всех входных данных. Спецификация может быть сделана менее субъективной с такими контрактами, какrequires а такжеensures в программировании c.
 Nicolas Dorier07 мая 2009 г., 14:59
@ Nils, вопрос о «программе», которую нужно доказать, а не об алгоритме. Попытка доказать алгоритм - это нормально, потому что легко выразить то, что мы хотим, чтобы алгоритм делал. Но, безусловно, доказывать, что программа это бессмысленно для меня

Ваш ответ на вопрос