프로그램을 증명할 수없는 이유는 무엇입니까?
컴퓨터 프로그램이 수학적 진술처럼 증명 될 수없는 이유는 무엇입니까? 수학적 증명은 다른 증명들 위에 구축되며, 더 많은 증명들과 공리들, 즉 우리가 자명하다고 주장하는 진리들에 이르기까지 구축됩니다.
컴퓨터 프로그램은 그러한 구조를 가지고 있지 않은 것 같습니다. 컴퓨터 프로그램을 작성한다면 어떻게 이전에 입증 된 작품을 가져 와서 프로그램의 진실을 보여줄 수 있습니까? 존재하지 않기 때문에 할 수 없습니다. 또한 프로그래밍의 공리는 무엇입니까? 현장의 원자 적 진실?
나는 위에 대한 좋은 대답이 없습니다. 하지만 소프트웨어는 과학이 아니라 예술이기 때문에 증명할 수없는 것 같습니다. 피카소를 어떻게 증명합니까?
증명 은 프로그램입니다.
프로그램의 공식적인 검증 은 거대한 연구 분야입니다. (예를 들어 Carnegie Mellon의 그룹을 참조하십시오 .)
많은 복잡한 프로그램이 검증되었습니다. 예를 들어, Haskell로 작성된 이 커널을 참조하십시오 .
프로그램은 절대적 으로 올바른 것으로 입증 될 수 있습니다. 형편없는 프로그램은 증명하기 어렵습니다. 합리적으로 잘 수행하려면 프로그램을 발전시키고 직접 증명해야합니다.
중단 문제로 인해 증명을 자동화 할 수 없습니다 . 그러나 임의의 명령문 또는 명령문 시퀀스의 사후 조건 및 전제 조건을 수동으로 증명할 수 있습니다.
Dijsktra의 A Discipline of Programming을 읽어야합니다 .
그런 다음 Gries의 The Science of Programming을 읽어야합니다 .
그러면 프로그램이 올바른지 증명하는 방법을 알게 될 것입니다.
불완전 성을 제기 한 사람들에 대한 작은 코멘트 일뿐 입니다. 모든 공리 시스템에 해당하는 것이 아니라 충분히 강력한 시스템에만 해당 됩니다.
다시 말해, Godel은 자신을 설명 할 수있을만큼 강력한 공리 시스템이 필연적으로 불완전하다는 것을 증명했습니다. 이것이 쓸모가 없다는 것을 의미하지는 않으며 다른 사람들이 연결했듯이 프로그램 증명에 대한 다양한 시도가 이루어졌습니다.
이중 문제 (증거 확인을위한 프로그램 작성)도 매우 흥미 롭습니다.
사실 입증 가능한 올바른 프로그램을 작성할 수 있습니다. 예를 들어 Microsoft 는 자동화 된 정리 증명 자를 포함하는 Spec # 이라는 C # 언어의 확장을 만들었습니다 . Java의 경우 ESC / java가 있습니다. 나는 거기에 더 많은 예제가 있다고 확신합니다.
( 편집 : 분명히 spec #은 더 이상 개발되지 않지만 계약 도구는 .NET 4.0의 일부가 될 것입니다 )
나는 프로그램의 자동 검증을 방해하는 것으로 추정되는 중단 문제 또는 불완전 성 정리 에 대해 손을 흔들고있는 포스터를 봅니다 . 물론 이것은 사실이 아닙니다. 이러한 문제는 정확하거나 부정확 한 것으로 입증 될 수없는 프로그램을 작성 하는 것이 가능함을 알려줍니다 . 즉 프로그램 구성에서 우리를 방지하지 않습니다 있습니다 라도 유용 올바른합니다.
중지 문제는 확인할 수없는 프로그램이 있음을 나타냅니다. 훨씬 더 흥미롭고 실용적인 질문은 어떤 종류의 프로그램 이 공식적으로 검증 될 수 있는지입니다. 누구나 관심있는 모든 프로그램이 (이론상) 검증 될 수 있습니다.
실제로 지금까지 매우 작은 프로그램 만이 올바른 것으로 입증되었습니다.
이 주제에 정말로 관심이 있다면 먼저 주제에 대한 고전적인 입문 작업 인 David Gries의 "The Science of Programming"을 추천하겠습니다.
실제로 프로그램이 어느 정도 정확하다는 것을 증명할 수 있습니다. 전제 조건과 사후 조건을 작성한 다음 전제 조건을 충족하는 상태가 주어지면 실행 후 결과 상태가 사후 조건을 충족 함을 증명할 수 있습니다.
그러나 까다로운 곳은 루프입니다. 이를 위해 추가로 루프 불변을 찾고 올바른 종료를 표시하려면 각 루프 이후에 남아있는 가능한 최대 반복 수에 대한 상한 함수를 찾아야합니다. 또한 루프를 반복 할 때마다 최소 1 회씩 감소한다는 것을 보여줄 수 있어야합니다.
프로그램에 대해이 모든 것을 갖추면 증거는 기계적입니다. 그러나 불행히도 루프에 대한 불변 및 바인딩 된 함수를 자동으로 파생시킬 수있는 방법이 없습니다. 인간의 직관은 작은 루프가있는 사소한 경우에 충분하지만 현실적으로 복잡한 프로그램은 빠르게 다루기 어려워집니다.
첫째, 왜 "프로그램은 증명할 수 없다"고 말합니까?
어쨌든 "프로그램"이란 무엇을 의미합니까?
프로그램이 알고리즘을 의미한다면 Kruskal을 모르십니까? Dijkstra 's? MST? 프림? 바이너리 검색? 합병? DP? 모든 것들은 그들의 행동을 설명하는 수학적 모델을 가지고 있습니다.
설명. 수학은 사물의 이유를 설명하지 않고 단순히 방법에 대한 그림을 그립니다. 태양이 내일 동쪽에서 떠오를 것이라는 것을 증명할 수는 없지만 과거에 그 일을 해왔 던 데이터를 보여줄 수 있습니다.
"컴퓨터 프로그램을 작성하면 어떻게 이전에 입증 된 작품을 가져 와서 프로그램의 진실을 보여줄 수 있습니까? 존재하지 않기 때문에 할 수 없습니다."
기다림? 당신은 할 수 없습니까? http://en.wikipedia.org/wiki/Algorithm#Algorithmic_analysis
나는 당신에게 "진실"을 보여줄 수 없습니다. 언어에 대한 "진실"을 보여줄 수없는만큼 프로그램입니다. 둘 다 세계에 대한 우리의 경험적 이해를 나타냅니다. "진실"이 아닙니다. 모든 횡설수설을 제쳐두고 병합 정렬 알고리즘이 목록의 요소를 O (nlogn) 성능으로 정렬하고 Dijkstra가 가중치 그래프에서 최단 경로를 찾거나 Euclid의 알고리즘이 가장 큰 것을 찾을 수 있음을 수학적으로 보여줄 수 있습니다. 두 숫자 사이의 공약수. 마지막 경우의 "내 프로그램의 진실"은 아마도 두 숫자 사이의 최대 공약수를 찾을 수 있다는 것입니다. 그렇지 않습니까?
반복 방정식을 사용하여 피보나치 프로그램이 어떻게 작동하는지 설명 할 수 있습니다.
자, 컴퓨터 프로그래밍은 예술인가? 확실히 그렇다고 생각합니다. 수학만큼.
나는 수학적 배경을 가진 사람이 아니므로 나의 무지를 용서하십시오. 그러나 "프로그램을 증명하다"는 것은 무엇을 의미합니까? 무엇을 증명하고 있습니까? 정확성? 정확성은 프로그램이 "올바른지"확인해야하는 사양입니다. 하지만이 사양은 사람에 의해 결정되며이 사양이 올바른지 어떻게 확인합니까?
제 생각에는 인간이 진정 원하는 것을 표현하는 데 어려움이 있기 때문에 프로그램에 버그가 있습니다. 대체 텍스트 http://www.processdevelopers.com/images/PM_Build_Swing.gif
그래서 당신은 무엇을 증명하고 있습니까? 관심 부족으로 인한 버그?
또한 프로그래밍의 공리는 무엇입니까? 현장의 원자 적 진실?
계약 기반 프로그래밍 (강좌 홈페이지 : http://www.daimi.au.dk/KBP2/ ) 이라는 과정을 수강했습니다 . 여기에서 내가 수강 한 과정 (및 내가 수강 한 다른 과정)에서 추정 할 수있는 내용
언어의 의미를 공식적으로 (수학적으로) 정의해야합니다. 간단한 프로그래밍 언어를 생각해 봅시다. 전역 변수, int, int 배열, 산술, if-then-else, while, 할당 및 아무것도하지 않는 것 [이의 "구현"으로 주류 언어의 하위 집합을 사용할 수 있습니다].
실행 상태는 쌍 목록 (변수 이름, 변수 값)입니다. "{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이 병합 알고리즘을 올바르게 구현한다는 주장입니다.
위의 공리를 사용하여이를 증명할 수 있습니다 (몇 가지 다른 공리가 필요할 수 있습니다. 하나에 대해 루프가 필요할 것입니다).
나는 이것이 올바른 프로그램을 증명하는 것이 어떤 모습인지를 보여주기를 바랍니다. 그리고 저를 믿으십시오. 겉보기에 단순한 알고리즘이 올바른지 증명하려면 많은 작업이 필요합니다. 알아, 나는 많은 시도를 읽었다 ;-)
[당신이 이것을 읽으면 : 당신의 손은 괜찮 았고, 그것은 나에게 두통을 일으킨 다른 모든 것입니다 ;-)]
물론 다른 사람들이 게시 한 것처럼 가능합니다.
아주 작은 서브 루틴이 올바른 증명하는 것은 프로그래밍 관련 학위 과정의 모든 학부가한다고 IMHO이 될 수있는 좋은 운동입니다 필요 할 수 있습니다. 코드를 명확하고 쉽게 검토하고 유지 관리 할 수 있도록 만드는 방법에 대한 훌륭한 통찰력을 제공합니다.
그러나 실제 세계에서는 실제 사용이 제한적입니다.
첫째, 프로그램에 버그가있는 것처럼 수학적 증명도 마찬가지입니다. 수학적 증명이 실제로 정확하고 오류가 없음을 어떻게 증명합니까? 당신은 할 수 없습니다. 그리고 반례의 경우, 출판 된 수학적 증명의 수에 관계없이 오류가 발견되었습니다.
둘째, 프로그램이 무엇을해야하는지에 대한 명확한 정의를 '선험적'으로하지 않으면 프로그램이 옳다는 것을 증명할 수 없습니다. 그러나 프로그램이해야 할 일에 대한 명확한 정의는 프로그램입니다. (컴파일러가없는 일종의 사양 언어로 된 프로그램 일 수 있습니다.) 따라서 프로그램이 옳다는 것을 증명하기 전에 먼저 동등하고 미리 알려진 다른 프로그램이 있어야합니다. 정확합니다. 그래서 QED는 모든 것이 무익합니다.
Brooks 의 고전적인 " No Silver Bullet "기사를 추적하는 것이 좋습니다 .
이 분야에 대한 많은 연구가 있습니다. 다른 사람들이 말했듯이 프로그램 언어 내의 구조는 복잡하며 주어진 입력에 대해 유효성을 검사하거나 증명하려고 할 때 더욱 악화됩니다.
그러나 많은 언어에서 허용되는 입력 (전제 조건)에 대한 사양을 허용하고 최종 결과 (사후 조건)를 지정할 수도 있습니다.
이러한 언어에는 B, Event B, Ada, fortran이 포함됩니다.
물론 프로그램에 대한 특정 속성을 증명하는 데 도움이되도록 설계된 많은 도구가 있습니다. 예를 들어 교착 상태의 자유를 증명하기 위해 SPIN을 통해 프로그램을 처리 할 수 있습니다.
논리 오류를 감지하는 데 도움이되는 도구도 많이 있습니다. 이것은 정적 분석 (goanna, satabs) 또는 실제 코드 실행 (gnu valgrind?)을 통해 수행 할 수 있습니다.
그러나 시작 (사양), 구현 및 배포에서 전체 프로그램을 실제로 증명할 수있는 도구는 없습니다. B 메서드는 가깝지만 구현 확인은 매우 약합니다. (그것은 인간이 speicficaiton을 구현으로 번역하는 데있어 틀림 없다고 가정합니다).
참고로 B 방법을 사용할 때 더 작은 공리로 복잡한 증명을 만드는 경우가 많습니다. (그리고 다른 해명적인 정리 증명에도 동일하게 적용됩니다).
그들은 할 수있다. 저는 대학 신입생으로서 프로그램 정확성 증명을 위해 많은 시간을 보냈습니다.
거시적 규모에서 실용적이지 않은 이유는 프로그램 증명을 작성하는 것이 프로그램을 작성하는 것보다 훨씬 어렵 기 때문입니다. 또한 오늘날 프로그래머는 함수 나 프로그램을 작성하지 않고 시스템을 구축하는 경향이 있습니다.
마이크로 스케일에서는 때때로 개별 기능에 대해 정신적으로 수행하고 쉽게 확인할 수 있도록 코드를 구성하는 경향이 있습니다.
우주 왕복선 소프트웨어에 대한 유명한 기사가 있습니다. 그들은 증명이나 동등한 것을합니다. 엄청난 비용과 시간이 소요됩니다. 이러한 수준의 검증이 필요할 수 있지만 현재 기술을 사용하는 모든 종류의 소비자 또는 상용 소프트웨어 회사의 경우 비용의 1 %로 99.9 % 솔루션을 제공하는 경쟁자가 점심을 먹게됩니다. 조금 더 안정적인 MS 오피스에 5000 달러를 지불하는 사람은 아무도 없을 것입니다.
자신감을 찾고 있다면 프로그램 증명의 대안은 테스트하는 것입니다. 이것은 이해하기 쉽고 자동화 할 수 있습니다. 또한 위에서 설명한 것처럼 수학적으로 증명이 불가능한 프로그램 클래스를 허용합니다.
무엇보다도 합격 테스트를 통과하는 것을 증명할 수있는 증거는 없습니다. *
프로그램이 말한대로 수행한다고해서 사용자가 원하는대로 수행한다는 의미는 아닙니다.
그것이 말하는 것이 사용자가 원하는 것임을 증명할 수 없다면 .
- 그런 다음 증명해야하는 것은 그들이 정말로 원하는 것입니다 . 왜냐하면 사용자로서 그들은 그들이 원하는 것을 거의 확실히 알지 못하기 때문입니다. 등. Reductio ad absurdum.
* 단위, 범위, 기능, 통합 및 기타 모든 종류의 테스트는 말할 것도 없습니다.
이것이 당신의 길에 도움이되기를 바랍니다.
여기서 언급되지 않은 것은 공식적인 방법 기반 시스템 인 B-Method 입니다. 파리 지하의 안전 시스템을 개발하는 데 사용되었습니다. B 및 Event B 개발을 지원하는 데 사용할 수있는 도구, 특히 Rodin이 있습니다.
프로그램을 증명할 수있을뿐만 아니라 컴퓨터가 증명에서 프로그램을 구성하도록 할 수 있습니다. Coq를 참조하십시오 . 따라서 구현에서 실수 할 가능성에 대해 걱정할 필요도 없습니다.
그럼에도 불구하고 Godel의 정리 ... 요점이 무엇입니까? 어떤 단순한 "진실"을 증명하고 싶습니까? 그 진리에서 무엇을 얻고 싶습니까? 이 말을 먹을 수 있지만 ... 실용성은 어디입니까?
Programs CAN be proven. It's quiet easy if you write them in language like for example Standard ML of New Jersey (SML/NJ).
Your statement is wide so it's catching lots of fish.
The bottom line is: some programs can definitely be proven correct. All programs can not be proven correct.
Here's a trivial example which, mind you, is exactly the same kind of proof that destroyed set theory back in the day: make a program which can determine whether itself is correct, and if it finds that it is correct, give an incorrect answer.
This is Gödel's theorem, plain and simple.
But this is not so problematic, since we can prove many programs.
Let us assume a purely functional language (ie Haskell). Side effects can be taken quite cleanly into account in such languages.
Proving that a program produces the right result requires you to specify:
- a correspondance between data types and mathematical sets
- a correspondance between Haskell functions and mathematical functions
- a set of axioms specifying what functions you are allowed to build from others, and the corresponding contruction on the mathematical side.
This set of specifications is called denotational semantics. They allow you to prove the reason about programs using mathematics.
The good news is that the "structure of programs" (point 3 above) and the "structure of mathematical sets" are quite similar (the buzzword is topos, or cartesian closed category), so 1/ the proofs you do on the math side will easily be transferred into programmatic constructions 2/ the programs you write are easily shown to be mathematically correct.
Read up on the halting problem (which is about the difficulty of proving something as simple as whether a program completes or not). Fundamentally the problem is related to Gödel's incompleteness theorem.
Some parts of programs can be proved. For example, the C# compiler that statically verify and guarantee type safety, if the the compilation succeeds. But I suspect the core of your question is to prove that a program performs correctly. Many (I do not dare say most) algorithms can be proved to be correct, but a whole program probably cannot be proved statically due to the following:
- Verification requires all possible branches (calls, ifs and interupts) to be traversed, which in advanced program code has super-cubic time complexity (hence it will never complete within reasonable time).
- Some programming techniques, either through making components or using reflection, makes it impossible to statically predict execution of code (i.e. you don't know how another programmer will use your library, and the compiler has a hard time predict how reflection in a consumer will invoke functionality.
And those are just some...
If the program has a well defined objective and initial assumptions (ignoring Godel...) it can be proven. Find all primes,x, for 6<=x<=10, your answer is 7 and that can be proven. I wrote a program that plays NIM (the first Python program I ever wrote) and in theory the computer always wins after the game falls into a state in which the computer can win. I haven't been able to prove it as true, but it IS true (mathematically by a digital binary sum proof) I believe unless I made an error in the code. Did I make an error, no seriously, can someone tell me if this program is beatable?
There are some mathematical theorems that have been "proven" with computer code like the four color theorem. But there are objections, because like you said, can you prove the program?
Further, what are the axioms of programming? The very atomic truths of the field?
Are the opcodes the "atomic truths"? For example on seeing ...
mov ax,1
... mightn't a programmer assert as axiomatic that, barring a hardware problem, after executing this statement the CPU's ax register would now contain 1?
If you write a computer program, how is it that you can take previous proven works and use them to show the truth of your program?
The "previous work" then might be the run-time environment in which the new program runs.
The new program can be proven: apart from formal proofs, it can be proven "by inspection" and by various forms of "testing" (including "acceptance testing").
How do you prove a Picasso?
If software is more like industrial design or engineering than like art, a better question might be "how do you prove a bridge, or an airplane?"
proving a program correct can only be done relative to the specification of the program; it is possible but expensive/time-consuming
some CASE systems produce programs more amenable to proofs than others - but again, this relies on a formal semantics of the specification...
...and so how do you prove the specification correct? Right! With more specifications!
I read a bit about this, but there are two problems.
First, you can't prove some abstract thing called correctness. You can, if things are set up properly, prove that two formal systems are equivalent. You can prove that a program implements a set of specifications, and it's easiest to do this by constructing the proof and program more or less in parallel. Therefore, the specifications must be sufficiently detailed to provide something to prove against, and therefore the specification is effectively a program. The problem of writing a program to satisfy a purpose becomes the problem of writing a formal detailed specification of a program to satisfy a purpose, and that's not necessarily a step forward.
Second, programs are complicated. So are proofs of correctness. If you can make a mistake writing a program, you sure can make one proving. Dijkstra and Gries told me, essentially, that if I was a perfect mathematician I could be a good programmer. The value here is that proving and programming are two somewhat different thought processes, and at least in my experience I make different sorts of mistakes.
In my experience, proving programs isn't useless. When I am trying to do something I can describe formally, proving the implementation correct eliminates a whole lot of hard-to-find errors, primarily leaving the dumb ones, which I can catch easily in testing. On a project that must produce extremely bug-free code, it can be a useful adjunct. It isn't suitable for every application, and it's certainly no silver bullet.
As others pointed out, (some) programs can indeed be proven.
One problem in practice however is that you first need something (i.e. an assumption or theorem) that you want to prove. So to prove something about a program you first need a formal description of what it should do (e.g. pre- and post-conditions).
In other words, you need a formal specification of the program. But getting even a reasonable (much less a rigorous formal) specification is already one of the hardest things in software development. Therefore it is generally very difficult to prove interesting things about a (real-world) program.
There are however some things which can be (and have been) more easily formalized (and proven). If you can at least prove that your program will not crash, that's already something :-).
BTW, some compiler warnings/errors are essentially (simple) proofs about a program. E.g., the Java compiler will prove that you never access an uninitialized variable in your code (otherwise it will give you a compiler error).
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.
Most answers focused on the practice and that's ok: in practice you don't care about formal proofing. But what's in theory?
Programs can be proven just as a mathematical statement can. But not in the sense you meant! In any sufficient powerful framework, there are mathematical statements (and programs) which cannot be proven! See here
So much noise here, but I am going to shout in the wind anyhow...
"Prove correct" has different meanings in different contexts. In formal systems, "prove correct" means that a formula can be derived from other proven (or axiomatic) formulas. "Prove correct" in programming simply shows code to be equivalent to a formal specification. But how do you prove the formal spec correct? Sadly, there is no way to show a spec to be bug-free or a solution any real-world problem other than through testing.
Just my 2 cents, adding to the interesting stuff already there.
Of all the programs that can't be proven, the most common ones are those performing IO (some unpredictible interaction with the world or the users). Even automated proofs sometimes just forget that "proven" programs" run on some physical hardware, not the ideal one described by the model.
On the other side mathematic proofs don't care much of the world. A recurring question with Maths is if it describes anything real. It is raised every time something new like imaginary numbers or non-euclidian space is invented. Then the question is forgotten as these new theories are such good tools. Like a good program, it just works.
참고URL : https://stackoverflow.com/questions/476959/why-cant-programs-be-proven
'Development Tip' 카테고리의 다른 글
| HeaderTemplate에서 중첩 된 repeater의 상위 데이터에 액세스 (0) | 2020.12.10 |
|---|---|
| Swift에서 UIView에 xib 할당 (0) | 2020.12.09 |
| Django : 길이가 고정 된 CharField, 어떻게? (0) | 2020.12.09 |
| Java에서 비트 시프 팅은 어떻게 작동합니까? (0) | 2020.12.09 |
| 로컬 네트워크의 다른 컴퓨터에서 webrick / rails에 액세스 (0) | 2020.12.09 |