Lean으로 수학 증명을 작성하는 방법: 소프트웨어 엔지니어를 위한 안내
Anatomy of a Lean proof for software engineers
소프트웨어 엔지니어가 Lean 정리 증명기를 사용해 형식 증명을 작성하는 과정을 설명한다. 계산 이론 문제를 예로 들어 DFA를 구성하고, 덧셈기의 상태 전이를 정의한 뒤, Mathlib의 정리를 활용해 정규 언어의 역폐쇄성을 증명한다. 형식 증명이 프로그램 검증과 어떻게 연결되는지, 그리고 실제 증명 코드가 어떻게 구성되는지 보여준다.
“형식 증명을 마친 후, 나는 이것이 소프트웨어 엔지니어들에게 시스템의 속성을 형식적으로 증명하는 데 무엇이 필요한지에 대한 좋은 통찰을 제공한다고 생각했기 때문에 글을 쓰기로 결정했다.”
HN 토론
67- thom
그래서 이건 다 좋은데, 우리가 검증은 되지만 의미론적 오류가 숨어 있을 수 있는 50만 줄이 넘는 Lean 증명을 받아들여야 한다고 요구받고 있는 상황에서, 계획이 뭐죠? 런타임이 내세우는 훌륭하고 견고한 약속에도 불구하고, 이것들은 유일무이하게 취약한 소프트웨어 산출물처럼 보입니다.
- WalterGR
OP: 작성하신 글에서 목차가 표시되어야 할 자리에 "[Contents]"라고 나옵니다.
- fooker
논리학에 대한 기초적인 이해 없이 Lean이나 증명 보조기를 이해하려고 하지 마세요. 이 글은 그 부분을 대충 건너뛰는데, 꽤 복잡하기 때문에 합리적입니다.
수많은 수학 증명을 작성해 봤더라도, 보통 증명 자체의 언어나 논리를 배우지는 않습니다. 그리고 뛰어난 컴퓨터 과학자라 해도, 논리는 단순히 AND, OR, NOT이 아닙니다.
다음은 필수 읽기 자료입니다. 더 좋은 출처를 찾아도 좋지만 위키백과도 좋습니다.
* 증명 트리 - https://en.wikipedia.org/wiki/Method_of_analytic_tableaux
* 구성적/직관주의 논리 - https://en.wikipedia.org/wiki/Intuitionistic_logic
* 증명과 타입 - https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspon...
* (불)완전성 - https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...
- whattheheckheck
명세와 증명 사이의 인터페이스는 그렇게 명확하지 않은데, 명세를 이해하려면 종종 증명을 봐야 하기 때문입니다. 그리고 증명에서 이상한 점을 발견하면, 뭔가 잘못됐다는 좋은 신호입니다.
그래, 이건 마치 내가 어떤 것이 초록색이라고 말할 때, 내 초록색이 당신의 초록색인지 어떻게 아느냐와 같습니다. 수학적으로 모델링된 시스템의 증명은 그것을 구현하는 기호와 전혀 연결되어 있지 않습니다. 같은 프로그램이거나 트레이스 정제를 하는 경우가 아니라면요. 그리고 프로그램이 비즈니스 기능을 수행하는 데 올바른지 증명할 방법은 실제로 실행해 보기 전에는 없습니다. 꽤나 계산적으로 환원 불가능하죠, 상태 기계를 만드는 상태 기계라니
- woggy
사람들이 Lean을 주로 소프트웨어 명세 언어로 사용할 수 있을지, 모든 것을 증명할 의도 없이 궁금합니다.
모듈의 의미와 법칙을 명세하여 설계를 정확하고 검증 가능하게 만들고, 구현에서 그 법칙들에 대한 속성 기반 테스트를 가능하게 할 수 있을까요? Lean은 설계에 대해 더 정밀하게 사고하기 위한 도구가 됩니다.