001▲ 202 · 댓글 84정확한 소프트웨어 작성이 어려운 이유David Hilbert는 1930년 모든 수학을 형식화하고 일관성, 완전성, 결정가능성을 증명할 수 있다고 믿었으나, Kurt Gödel의 불완전성 정리와 1936년 Church·Turing의 정지 문제(halting problem) 증명으로 Hilbert의 계획이 무너졌다.
정지 문제부터 모델 검사까지 계산 이론의 기본 정리들이 왜 소프트웨어 검증이 근본적으로 불가능한지를 보여주기 때문에, 프로그램 정확성의 한계를 수학적으로 이해하려는 개발자와 연구자에게 필수적이다.
핵심 요약
David Hilbert는 1930년 모든 수학을 형식화하고 일관성, 완전성, 결정가능성을 증명할 수 있다고 믿었으나, Kurt Gödel의 불완전성 정리와 1936년 Church·Turing의 정지 문제(halting problem) 증명으로 Hilbert의 계획이 무너졌다.
정지 문제는 자기참조를 이용한 대각선 논법으로 증명되며, 주어진 프로그램이 종료하는지 판단하는 알고리즘은 존재할 수 없다는 것을 보여준다.
정지 문제의 직접적 결과로 도달가능성 판정 불가능, Rice의 정리(프로그램의 비자명 성질 판정 불가능), Busy Beaver 함수의 비계산가능성 등이 따른다.