왜 프로그램이 입증 될 수 없습니까?
https://stackoverflow.com/questions/476959
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
수학적 진술과 마찬가지로 컴퓨터 프로그램을 입증 할 수없는 이유는 무엇입니까? 수학적 증거는 다른 증거에 기반을두고 있으며,이 증거는 더 많은 증거와 공리에 이르기까지 쌓입니다.
컴퓨터 프로그램에는 그러한 구조가없는 것 같습니다. 컴퓨터 프로그램을 작성하는 경우 이전에 입증 된 작품을 취하고 프로그램의 진실을 보여줄 수있는 방법은 무엇입니까? 당신은 아무것도 존재하지 않기 때문에 당신은 할 수 없습니다. 또한 프로그래밍의 공리는 무엇입니까? 분야의 바로 원자 진실?
위에 대한 좋은 답변이 없습니다. 그러나 그것은 과학이 아니라 예술이기 때문에 소프트웨어가 입증 될 수없는 것 같습니다. 피카소를 어떻게 증명합니까?
해결책
증거 ~이다 프로그램들.
공식적인 검증 프로그램의 a 거대한 연구 분야. (예를 들어, 참조, Carnegie Mellon의 그룹.)
많은 복잡한 프로그램이 확인되었습니다. 예를 들어, 이것을 참조하십시오 Haskell로 작성된 커널.
다른 팁
불완전 성을 키우는 사람들에 대한 작은 의견만으로는 그렇지 않습니다. 모두 공리 시스템 만 충분히 강력합니다 하나.
다시 말해, 고델은 자신을 설명하기에 충분히 강력한 공리 시스템이 반드시 불완전하다는 것을 증명했다. 그렇다고해서 쓸모가 없다는 의미는 아니며 다른 사람들이 연결된 것처럼 프로그램 증명에 대한 다양한 시도가 이루어졌습니다.
이중 문제 (증거 확인 프로그램 작성)도 매우 흥미 롭습니다.
실제로 올바른 프로그램을 작성할 수 있습니다. 예를 들어, Microsoft는 C# 언어의 확장을 만들었습니다. 투기# 여기에는 자동화 된 정리 서전이 포함됩니다. Java에게는 있습니다 ESC/Java. 나는 거기에 더 많은 예가 있다고 확신합니다.
(편집하다: 분명히 사양#이 더 이상 개발되지 않았지만 계약 도구는 .NET 4.0의 일부가됩니다)
나는 일부 포스터가 손으로 흔들리는 것을 본다 중단 문제 또는 불완전 성 정리 프로그램의 자동 검증을 막을 수 있습니다. 이것은 물론 사실이 아닙니다. 이러한 문제는 단지 우리에게 그것이 있다고 말합니다 정확하거나 틀린 것으로 입증 될 수없는 프로그램을 작성할 수 있습니다.. 그렇다고해서 우리가 프로그램을 건설하는 것을 막지는 못합니다 ~이다 아마도 정확합니다.
정지 문제는 확인할 수없는 프로그램이 있음을 보여줍니다. 훨씬 더 흥미롭고 더 실용적인 질문은 어떤 클래스의 프로그램입니다. ~할 수 있다 공식적으로 확인하십시오. 어쩌면 누구나 관심이있는 모든 프로그램은 (이론적으로) 확인 될 수 있습니다. 실제로, 지금까지, 아주 작은 프로그램만이 정확한 것으로 입증되었습니다.
주제에 정말로 관심이 있다면, 주제에 대한 고전적인 소개 작업 인 David Gries의 "The Science of Programming"을 추천하겠습니다.
실제로 프로그램이 어느 정도 올바른 것을 증명할 수 있습니다. 전제 조건과 사후 조건을 작성한 다음 전제 조건을 충족하는 상태가 주어지면 실행 후 결과 상태가 사후 조건을 충족시킬 수 있습니다.
그러나 까다로운 곳은 고리입니다. 이를 위해서는 루프 불변량을 찾아야하고 올바른 종료를 표시하려면 각 루프 후 남은 최대 반복 수에서 상한 기능을 찾아야합니다. 또한 루프를 통한 각 반복 후에 적어도 하나 이상 감소 함을 보여줄 수 있어야합니다.
이 모든 프로그램이 있으면 증거가 기계적입니다. 그러나 불행히도, 루프에 대한 불변의 바운드 함수를 자동으로 도출 할 수있는 방법은 없습니다. 인간의 직관은 작은 루프가있는 사소한 경우에 충분하지만 현실적으로 복잡한 프로그램은 빠르게 다루기 어려워집니다.
첫째, 왜 "프로그램이 입증 될 수 없다"고 말하는가?
어쨌든 "프로그램"이란 무엇을 의미합니까?
프로그램에 의해 당신이 알고리즘을 의미한다면 Kruskal을 모르십니까? dijkstra? MST? Prim 's? 이진 검색? MERGESORT? DP? 그 모든 것들은 그들의 행동을 설명하는 수학적 모델이 있습니다.
설명하다. 수학은 단순히 방법의 그림을 그린 이유를 설명하지 않습니다. 나는 태양이 내일 동쪽에서 상승 할 것이라는 것을 당신에게 증명할 수는 없지만 과거에 그 일을했던 데이터를 보여줄 수 있습니다.
"컴퓨터 프로그램을 작성하는 경우 이전에 입증 된 작품을 취하고 프로그램의 진실을 보여주기 위해 어떻게 사용할 수 있습니까?
기다리다? 당신은 할 수 없습니까?http://en.wikipedia.org/wiki/algorithm#algorithmic_analysis
나는 당신에게 "진실"을 보여줄 수 없다. 나는 언어에 "진실"을 보여줄 수없는만큼 프로그램이다. 둘 다 세상에 대한 우리의 경험적 이해의 표현입니다. "진실"이 아닙니다. 모든 횡설수설을 제쳐두고 Mergesort Algorith가 O (nlogn) 성능의 목록에 요소를 정렬 할 것이라는 것을 수학적으로 보여줄 수 있습니다. Dijkstra는 가중 그래프에서 가장 짧은 경로를 찾거나 유클리드의 알고리즘이 가장 큰 경로를 찾을 수 있습니다. 두 숫자 사이의 공통 구분. 마지막 경우에 "내 프로그램의 진실"은 아마도 두 숫자 사이의 가장 큰 공통 구분을 찾을 것입니다. 생각하지 않습니까?
재발 방정식으로 Fibonacci 프로그램의 작동 방식을 설명 할 수 있습니다.
이제 컴퓨터 프로그래밍이 예술을 프로그래밍하고 있습니까? 나는 그것이 확실하다고 생각합니다. 수학만큼.
나는 수학적 배경에서 오지 않기 때문에 내 무지를 용서하지만 "프로그램을 증명하기 위해"무엇을 의미합니까? 당신은 무엇을 증명하고 있습니까? 정확성? 정확성은 프로그램이 "정확한"것으로 확인 해야하는 사양입니다. 그러나이 사양은 인간에 의해 결정 되며이 사양이 올바른지 어떻게 확인합니까?
제 생각에는 인간이 실제로 원하는 것을 표현하는 데 어려움이 있기 때문에 프로그램에는 버그가 있습니다.Alt Text http://www.processdevelopers.com/images/pm_build_swing.gif
그래서 당신은 무엇을 증명하고 있습니까? 관심 부족으로 인한 버그?
또한 프로그래밍의 공리는 무엇입니까? 분야의 바로 원자 진실?
계약 기반 프로그래밍 (코스 홈페이지 : http://www.daimi.au.dk/kbp2/). 여기에서 코스에서 외삽 할 수있는 것 (그리고 내가 수강 한 다른 과정)
당신은 당신의 언어의 의미를 공식적으로 (수학적으로) 정의해야합니다. 간단한 프로그래밍 언어를 생각해 봅시다. 글로벌 변수, ints, int array, 산술, if-then-else, 그리고 할당 및하지 않는다 [주류 언어의 하위 집합을 이것의 "구현"으로 사용할 수있을 것입니다].
실행 상태는 쌍 목록 (변수 이름, 변수 값)입니다. "실행 명령문 S1은 실행 상태 Q1에서 상태 Q2로 이동합니다.
그러면 하나의 공리가 될 것입니다 "if both {Q1} S1 {Q2} and {Q2} S2 {Q3}, then {Q1} S1; S2 {Q3}". 즉, 성명서 S1이 주 Q1에서 Q2로 데려 가면 S2는 Q2에서 Q3에서 Q2에서 Q2에서 Q2로 이동하면 "S1; S2"(S1)가 주 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)이 두 개의 정렬 된 배열을 병합하고 결과를 외부로 저장하는 진술이며 다음 예제에서 내가 사용하는 모든 단어가 공식적으로 (수학적으로) 표현되었다고 가정합니다. 그 다음에 "{sorted(A1) && sorted(A2)} A := M(A1, A2) {sorted(A) && permutationOf(A, A1 concatened with A2)}" 주장은 병합 알고리즘을 올바르게 구현합니다.
위의 공리를 사용하여 이것을 증명하려고 시도 할 수 있습니다 (다른 사람들은 아마도 필요할 것입니다. 루프가 필요할 것입니다).
나는 이것이 프로그램이 올바른 모습을 보여주는 것을 보여주기를 바랍니다. 그리고 나를 믿으십시오 : 그것은 필요합니다 많은 겉보기에 간단한 알고리즘을 위해서도 올바르게 증명하는 작업. 나는 많은 시도를 읽었다는 것을 알고있다 ;-)
이 글을 읽으면 : 당신의 핸드 인은 괜찮 았습니다. 그것은 나에게 두통을 일으킨 다른 모든 것입니다 ;-)
물론 다른 사람들이 게시 한 것처럼 그들은 할 수 있습니다.
매우 작은 서브 루틴을 정확하게 증명하는 것은 프로그래밍 관련 학위 프로그램의 모든 학부생이 필수의 할 것. 코드를 명확하고 쉽게 검토 할 수 있고 유지 관리 가능한 방법에 대한 생각에 대한 훌륭한 통찰력을 제공합니다.
그러나 현실 세계에서는 실제적인 사용이 제한적입니다.
첫째, 프로그램에 버그가있는 것처럼 수학적 증거도 마찬가지입니다. 수학적 증거가 실제로 정확하고 오류가 없음을 어떻게 증명합니까? 당신은 할 수 없습니다. 그리고 반례로서, 출판 된 수학적 증거의 수는 때로는 몇 년 후에 오류가 발견되었습니다.
둘째, 프로그램이해야 할 일에 대한 명백한 정의를 '선험적으로'하지 않고는 프로그램이 정확하다는 것을 증명할 수 없습니다. 그러나 프로그램이해야 할 일에 대한 명백한 정의는 프로그램입니다. (컴파일러가없는 어떤 종류의 사양 언어로 프로그램 일 수 있지만, 프로그램이 올바른 것을 증명하기 전에 먼저 동등한 다른 프로그램이 있어야하며 미리 알려진 다른 프로그램이 있어야합니다. 맞습니다. 그래서 모든 것이 헛된 일입니다.
나는 클래식을 추적하는 것이 좋습니다. "실버 총알이 없습니다"Brooks의 기사.
다른 사람들이 말했듯이, 프로그램 언어 내의 구성은 복잡하며, 주어진 입력에 대해 검증하거나 증명할 때만 악화됩니다.
그러나 많은 언어는 허용 가능한 입력 (전제 조건)에 대한 사양을 허용하며 최종 결과 (사후 조건)를 지정할 수 있습니다.
이러한 언어에는 다음이 포함됩니다. B, Event B, Ada, Fortran.
물론 프로그램에 대한 특정 속성을 증명하는 데 도움이되는 많은 도구가 있습니다. 예를 들어, 교착 상태의 자유를 증명하기 위해 스핀을 통해 프로그램을 크 런치 할 수 있습니다.
논리 오류를 감지하는 데 도움이되는 많은 도구도 있습니다. 이것은 정적 분석 (Goanna, Satabs) 또는 실제 코드 실행 (GNU Valgrind?)을 통해 수행 할 수 있습니다.
그러나 Inception (Specification), 구현 및 배포에서 전체 프로그램을 실제로 증명할 수있는 도구는 없습니다. B 메소드는 가깝지만 구현 점검은 매우 약합니다. (인간은 Speicficaiton을 구현으로 번역 할 때 불가능하다고 가정합니다).
참고로, B 메소드를 사용할 때는 작은 공리에서 복잡한 증거를 구축 할 수 있습니다. (그리고 다른 엑스포스트리 정리 속담에도 동일하게 적용됩니다).
그들은 할 수있다. 나는 대학 신입생으로서 많은 시간을 프로그램 정확성 증거로 보냈습니다.
매크로 척도에서 실용적이지 않은 이유는 프로그램 증명서를 작성하는 것이 프로그램을 작성하는 것보다 훨씬 어려운 경향이 있기 때문입니다. 또한 오늘날 프로그래머는 기능이나 프로그램이 작성하지 않고 시스템을 구축하는 경향이 있습니다.
마이크로 규모로, 나는 때때로 개별 기능을 위해 정신적으로 그것을 수행하고, 내 코드를 정리하여 쉽게 확인할 수 있도록하는 경향이 있습니다.
우주 왕복선 소프트웨어에 대한 유명한 기사가 있습니다. 그들은 증거 또는 동등한 일을합니다. 엄청나게 비용이 많이 들고 시간이 많이 걸립니다. 이러한 수준의 검증이 필요할 수 있지만, 모든 종류의 소비자 또는 상용 소프트웨어 회사의 경우 현재 기술을 갖춘 모든 종류의 소비자 또는 상용 소프트웨어 회사의 경우 비용의 1%로 99.9% 솔루션을 제공하는 경쟁자가 점심을 먹을 수 있습니다. 아무도 미미한 MS 사무실에 대해 5000 달러를 지불하지 않을 것입니다.
자신감을 찾고 있다면 프로그램을 증명하는 대안이이를 테스트하는 것입니다. 이해하기 쉽고 자동화 할 수 있습니다. 또한 위에서 설명한 것처럼 증거가 수학적으로 불가능한 프로그램 클래스를 허용합니다.
무엇보다도 수락 테스트를 통과하기위한 증거는 없습니다.
프로그램이 실제로 말하는 것을 수행한다고해서 사용자가 원하는대로하는 것을 의미하지는 않습니다.
하지 않는 한 당신은 그것이 말하는 것이 사용자가 원하는 것임을 증명할 수 있습니다.
- 당신이 증명해야 할 것은 그들입니다 정말로 원한다, 사용자이기 때문에 그들은 자신이 원하는 것을 거의 알지 못합니다. 등 환원 AD 부조리.
*단위, 적용 범위, 기능, 통합 및 기타 모든 종류의 테스트는 말할 것도 없습니다.
이것이 당신의 길에 도움이되기를 바랍니다.
프로그램을 증명할 수있을뿐만 아니라 컴퓨터가 증명서에서 프로그램을 구성하도록 할 수 있습니다. 보다 coq. 따라서 구현에서 실수를 저지른 가능성에 대해 걱정할 필요조차 없습니다.
고델의 이론 그럼에도 불구하고 ... 요점은 무엇입니까? 당신은 어떤 단순한 "진실"을 증명하고 싶습니까? 그 진실에서 무엇을 파생시키고 싶습니까? 내가이 말을 먹을 수있는 동안 ... 실용성은 어디에 있습니까?
프로그램은 입증 될 수 있습니다. 뉴저지 표준 ML (SML/NJ)와 같은 언어로 쓰면 조용합니다.
당신의 진술은 넓어서 많은 물고기를 잡고 있습니다.
결론은 다음과 같습니다. 일부 프로그램은 확실히 올바른 것으로 입증 될 수 있습니다. 모든 프로그램은 할 수 있습니다 ~ 아니다 올바른 것으로 입증되었습니다.
여기에 당신이 그 날에 이론을 다시 파괴 한 것과 동일한 종류의 증거 인 사소한 예는 다음과 같습니다. ~이다 정확하고 잘못된 대답을하십시오.
이것은 Gödel의 정리이며 평범하고 단순합니다.
그러나 우리는 많은 프로그램을 증명할 수 있기 때문에 이것은 그렇게 문제가되지 않습니다.
순전히 기능적인 언어 (예 : Haskell)를 가정 해 봅시다. 부작용은 그러한 언어로 상당히 깨끗하게 고려 될 수 있습니다.
프로그램이 올바른 결과를 생성한다는 것을 증명하려면 다음을 지정해야합니다.
- 데이터 유형과 수학적 세트 사이의 대응
- Haskell 함수와 수학적 함수 사이의 대응
- 다른 사람으로부터 구축 할 수있는 기능과 수학적 측면에서의 해당 기여를 지정하는 일련의 공리.
이 사양 세트를 호출합니다 의미 적 의미론. 수학을 사용하여 프로그램에 대한 이유를 증명할 수 있습니다.
좋은 소식은 "프로그램의 구조"(위 3 지점)와 "수학적 세트의 구조"가 상당히 비슷하다는 것입니다 (유행어는 토 포스, 또는 직교 폐쇄 카테고리), so 1/ 수학 측에서 수행하는 증거는 프로그램 구성 구성 2로 쉽게 전송 될 것입니다.
에서 읽으십시오 중단 문제 (프로그램이 완료되는지 여부에 관계없이 단순한 것을 증명하기가 어렵습니다). 근본적으로 문제는 괴델의 불완전 성 정리와 관련이 있습니다.
프로그램의 일부가 증명 될 수 있습니다. 예를 들어, 컴파일이 성공한 경우 정적으로 유형 안전을 확인하고 보장하는 C# 컴파일러. 그러나 귀하의 질문의 핵심은 프로그램이 올바르게 수행된다는 것을 증명하는 것입니다. 많은 (대부분의 말을 감히 말하지는 않습니다) 알고리즘은 정확한 것으로 판명 될 수 있지만 전체 프로그램은 다음과 같이 정적으로 입증 될 수 없습니다.
- 검증은 가능한 모든 분기 (호출, IFS 및 인터럽트)를 통과해야하며, 이는 고급 프로그램 코드에서 초고속 시간 복잡성을 갖습니다 (따라서 합리적인 시간 내에 완료되지는 않습니다).
- 구성 요소를 만들거나 반사를 사용하여 일부 프로그래밍 기술은 코드 실행을 정적으로 예측할 수 없습니다 (즉, 다른 프로그래머가 라이브러리를 어떻게 사용할 것인지 모르고 컴파일러는 소비자의 의지에 대한 반사가 어떻게되는지 예측하기 어려운 시간을 예측합니다. 기능을 호출하십시오.
그리고 그것들은 단지 일부입니다 ...
프로그램에 잘 정의 된 목표와 초기 가정 (Godel 무시 ...)이있는 경우 입증 될 수 있습니다. 6 <= x <= 10에 대한 모든 프라임 x를 찾으십시오. 답은 7이며 입증 될 수 있습니다. 나는 a NIM을 연주하는 프로그램 (내가 쓴 최초의 Python 프로그램)와 이론적으로 컴퓨터는 컴퓨터가 이길 수있는 상태로 떨어진 후에 컴퓨터가 항상 승리합니다. 나는 그것을 사실로 증명할 수 없었지만, 코드에서 오류를하지 않는 한 (디지털 바이너리 합계 증명에 의해 수학적으로) 사실입니다. 내가이 프로그램을 이길 수 있는지 누군가에게 오류를 일으켰습니까?
컴퓨터 코드로 "입증 된"수학적 이론이 네 가지 색상 정리. 그러나 당신이 말했듯이, 당신은 프로그램을 증명할 수 있기 때문에 반대 의견이 있습니다.
또한 프로그래밍의 공리는 무엇입니까? 분야의 바로 원자 진실?
입니다 opcodes "원자 진실"? 예를 들어 보는 것은 ...
mov ax,1
... 프로그래머 가이 진술을 실행 한 후 하드웨어 문제를 제외하고는 CPU의 공리를 주장하지 않을 수 있습니다. ax 레지스터에는 이제 포함됩니다 1?
컴퓨터 프로그램을 작성하는 경우 이전에 입증 된 작품을 취하고 프로그램의 진실을 보여줄 수있는 방법은 무엇입니까?
"이전 작업"은 새로운 프로그램이 운영되는 런타임 환경 일 수 있습니다.
새로운 프로그램은 입증 될 수 있습니다. 공식적인 증거와는 별도로, "검사"와 다양한 형태의 "테스트"( "수락 테스트"포함)를 통해 입증 될 수 있습니다.
피카소를 어떻게 증명합니까?
소프트웨어가 예술보다 산업 디자인이나 엔지니어링과 비슷하다면 더 나은 질문은 "다리 나 비행기를 어떻게 증명합니까?"일 수 있습니다.
프로그램을 정확하게 증명하는 것은 프로그램의 사양에 비해 만 수행 될 수 있습니다. 가능하지만 비싸거나 시간이 많이 걸립니다
일부 사례 시스템은 다른 것보다 증거에 더 적합한 프로그램을 생성하지만 다시, 이것은 사양의 공식적인 의미에 의존합니다 ...
... 그렇다면 사양이 올바른 방법을 어떻게 증명합니까? 오른쪽! 더 많은 사양으로!
나는 이것에 대해 조금 읽었지만 두 가지 문제가 있습니다.
첫째, 정확성이라는 추상적 인 것을 증명할 수는 없습니다. 상황이 제대로 설정되면 두 공식 시스템이 동등하다는 것을 증명할 수 있습니다. 프로그램이 일련의 사양을 구현한다는 것을 증명할 수 있으며, 증명과 프로그램을 더 이상 병렬로 구성하여이를 수행하는 것이 가장 쉽습니다. 따라서 사양은 증명할 무언가를 제공하기에 충분히 상세해야하며 따라서 사양은 효과적으로 프로그램입니다. 목적을 충족시키기위한 프로그램을 작성하는 문제는 목적을 충족시키기 위해 프로그램의 공식적인 세부 사양을 작성하는 문제가되며 반드시 한 걸음 앞으로 나아가는 것은 아닙니다.
둘째, 프로그램은 복잡합니다. 정확성의 증거도 마찬가지입니다. 프로그램을 작성하는 실수를 할 수 있다면 분명히 증명할 수 있습니다. Dijkstra와 Gries는 본질적으로 내가 완벽한 수학자라면 좋은 프로그래머가 될 수 있다고 말했습니다. 여기서 가치는 입증과 프로그래밍이 두 가지 다른 사고 과정이며, 적어도 내 경험상 나는 다른 종류의 실수를한다는 것입니다.
내 경험상, 증명 프로그램은 쓸모가 없습니다. 내가 공식적으로 설명 할 수있는 일을하려고 할 때, 구현을 정확하게 증명하면 찾기 어려운 오류가 많이 제거되어 주로 멍청한 오류를 남기고 테스트에서 쉽게 잡을 수 있습니다. 매우 버그가없는 코드를 생성 해야하는 프로젝트에서는 유용한 보조가 될 수 있습니다. 모든 애플리케이션에 적합하지는 않으며 확실히 실버 총알은 아닙니다.
다른 사람들이 지적했듯이 (일부) 프로그램은 실제로 입증 될 수 있습니다.
그러나 실제로 한 가지 문제는 당신이 처음으로 필요하다는 것입니다. 무엇 (즉, 가정이나 정리) 당신이 증명하고 싶은 것. 따라서 프로그램에 대해 무언가를 증명하려면 먼저해야 할 일에 대한 공식적인 설명 (예 : 사전 및 사후 조건)이 필요합니다.
즉, 프로그램의 공식 사양이 필요합니다. 그러나 합리적인 (엄격한 공식적인) 사양조차도 이미 소프트웨어 개발에서 가장 어려운 것 중 하나입니다. 따라서 일반적으로 증명하기가 매우 어렵습니다 흥미로운 (실제) 프로그램에 관한 것들.
그러나 더 쉽게 공식화되고 입증 될 수있는 것들이 있습니다. 최소한 프로그램이 충돌하지 않을 것이라는 것을 증명할 수 있다면, 그것은 이미 무언가입니다 :-).
BTW, 일부 컴파일러 경고/오류는 본질적으로 프로그램에 대한 증거입니다. 예를 들어, Java 컴파일러는 코드에서 초기화되지 않은 변수에 액세스하지 않음을 증명합니다 (그렇지 않으면 컴파일러 오류가 제공됩니다).
나는 모든 답을 읽지 않았지만, 내가 보는 방식, 프로그램을 증명하는 것은 무의미하다. 그래서 아무도 그것을하지 않는 이유이다.
상대적으로 작은/중간 프로젝트 (예 : 10k 줄의 코드)가 있다면, 증거는 아마도 더 이상 10k 라인 일 것입니다.
프로그램에 버그가있을 수 있다면 증거에 "버그"가있을 수 있습니다. 어쩌면 증거에 대한 증거가 필요할 수도 있습니다!
고려해야 할 또 다른 사항, 프로그램은 매우 공식적이고 정확합니다. 프로그램 코드는 매우 멍청한 기계에 의해 실행되어야하기 때문에 더 엄격하고 공식적인 것을 얻을 수 없습니다.
증거는 인간이 읽을 것이지만 실제 코드보다 덜 엄격한 경향이 있습니다.
증명할 유일한 것은 특정 데이터 구조 (예 : QuickSort, 이진 트리에 대한 삽입 등)에서 작동하는 저수준 알고리즘입니다.
이러한 것들은 다소 복잡합니다. 왜 그들이 일하는지 또는 항상 일할 것인지의 여부는 즉시 분명하지 않습니다. 또한 다른 모든 소프트웨어의 기본 빌딩 블록도 있습니다.
대부분의 답변은 연습에 중점을 두었고 괜찮습니다. 실제로는 공식적인 교정에 신경 쓰지 않습니다. 그러나 이론적으로 무엇입니까?
프로그램은 수학적 진술처럼 입증 될 수 있습니다. 그러나 당신이 의미하는 의미는 아닙니다! 충분한 강력한 프레임 워크에는 입증 될 수없는 수학적 진술 (및 프로그램)이 있습니다! 보다 여기
여기에 너무 많은 소음이 있지만 어쨌든 바람에 소리를 지르려고 ...
"올바른 증명"은 다른 맥락에서 다른 의미를 갖습니다. ~ 안에 공식 시스템, "올바른 증거"는 공식이 다른 입증 된 (또는 공리적) 공식에서 파생 될 수 있음을 의미합니다. 프로그래밍에서 "올바른 증거"는 단순히 공식 사양과 동일하게 코드를 보여줍니다. 그러나 공식적인 사양이 정확히 맞다는 것을 어떻게 증명합니까? 안타깝게도 사양을 버그가없는 것으로 표시하거나 테스트를 통한 실제 문제가없는 솔루션을 표시 할 방법이 없습니다.
내 2 센트 만, 이미 흥미로운 것들을 추가했습니다.
입증 할 수없는 모든 프로그램 중에서 가장 일반적인 프로그램은 IO를 수행하는 것입니다 (일부는 세계 또는 사용자와의 예측할 수없는 상호 작용)입니다. 자동화 된 증거조차도 때때로 "입증 된"프로그램이 일부 물리적 하드웨어에서 실행되며 모델에서 설명한 이상적인 하드웨어가 아니라는 것을 잊어 버립니다.
다른 한편으로 수학 증명은 세상을 많이 신경 쓰지 않습니다. 수학에 대한 되풀이되는 질문은 실제 사항을 묘사하는 경우입니다. 상상의 숫자 나 비 유클리드 공간과 같은 새로운 것이 발명 될 때마다 발생합니다. 그러면이 새로운 이론이 좋은 도구이므로 질문이 잊혀집니다. 좋은 프로그램처럼, 그것은 단지 작동합니다.
