컴퓨터가 할 수 없는 것 - 정지문제

컴퓨터가 “모든 걸 자동으로 판정”할 수 없는 이유: 정지 문제 쉽게 이해하기

왜 이런 문제가 나왔나

사람들은 묻는다. “이 프로그램이 끝까지 실행될까? 아니면 영원히 돌까?”
가능하면 배포 전에 자동으로 판정하고 싶다. 무한루프나 데드락을 피하고 싶기 때문이다. 항공. 의료. 금융처럼 실패 비용이 큰 분야에서는 특히 그렇다. 그래서 연구자들은 “모든 프로그램의 종료 여부를 항상 맞히는 검출기”를 꿈꿨다.

왜 중요한가

만약 그런 검출기가 가능하다면 완벽한 자동 검증이 가능하다. 치명적 버그를 출발선에서 막을 수 있다. 그러나 수학적 결과는 반대다. 그 검출기는 원리상 만들 수 없다. 이 한계는 소프트웨어 안전. 보안. 자동화의 범위를 규정한다. 우리가 어떤 전략을 써야 하는지도 정한다. 즉, 완벽 자동화는 불가. 제한과 격리. 부분 판단. 사람의 증명이 필요하다.

한 문장 정의

정지 문제: “주어진 프로그램이 언젠가 끝나는지를 모든 경우에 항상 맞게 판정하는 만능 알고리즘은 존재하지 않는다”는 정리.

직관적 비유 1: 완벽 예언가 vs 반대로 하는 사람

• 가정: 어떤 예언가가 있다. 당신의 행동을 100% 맞춘다.
• 당신은 이렇게 말한다. “예언가가 ‘집에 감’이라면 난 안 간다. ‘안 감’이라면 바로 간다.”
• 예언가는 무엇을 말해도 틀린다.
• 정지 문제의 핵심도 같다. 만능 검출기가 뭐라 해도 그 판단을 뒤집는 프로그램을 만들 수 있다. 그래서 모순이 생긴다.

직관적 비유 2: 규칙표 vs 반대 버튼

• 회사가 모든 경우를 다루는 거대한 규칙표를 만든다.
• 직원 하나가 “규칙표가 ‘근무’라면 퇴근. ‘퇴근’이라면 야근”을 선언한다.
• 규칙표는 어떤 줄을 골라도 틀린다.
• 분기 수. 케이스 나열. 패턴 매칭으로는 해결되지 않는다. 자기참조+뒤집기가 본질이기 때문이다.

영상 속 구성요소가 하는 일

• 복사기: 프로그램의 설계도(청사진)를 복제해 자기 자신을 입력으로 넣기 쉽게 한다.
• 부정기: 검출기의 판단을 반대로 바꾸는 간단한 장치다.
• 이 둘을 묶은 합성 기계에 자기 자신의 청사진을 입력하면 모순이 드러난다.
• 결론은 같다. “만능” 검출기는 존재할 수 없다.

흔한 오해 정리

• 이진수라서 못 하는 게 아니다. 하드웨어가 달라도 논리 구조는 같다.
• 확률로 “거의 항상” 맞히는 것도 정지 문제의 요구를 충족하지 못한다. “항상”이 핵심이다.
• “모르겠다”를 허용하면 모순은 피한다. 하지만 그건 만능 판별기가 아니다.

그럼 현실에서 무엇이 가능한가

• 제한된 언어: 구조적 재귀만 허용. 크기 타입으로 입력이 줄어드는 구조만 허용. 애초에 “끝나는 프로그램만 표현”하게 설계.
• 부분 결정: 정적 분석기가 “모르겠다”를 돌려줄 수 있게 한다. 오탐이나 미탐을 감수한다.
• 증명 보조: 개발자가 변량과 불변식을 써서 특정 코드의 종료를 증명한다.
• 운영 전략: 타임아웃. 리소스 한도. 샌드박스. 최소 권한. 격리와 롤백.

보안과 품질에 주는 메시지

• 완벽한 보안 스캐너는 없다. 모든 악성 코드를 무오류로 탐지하는 자동 판별기는 만들 수 없다.
• 목표를 바꿔야 한다. 위험을 줄이고. 빨리 탐지하고. 즉시 격리하고. 쉽게 복구한다.
• 설계 단계에서 제약을 두고. 배포 단계에서 관찰 가능성을 높이고. 운영 단계에서 방어층을 쌓는다.

요약

• 만능 종료 검출기가 있다면 좋다. 그러나 원리상 불가능하다.
• 그래서 소프트웨어 공학은 제한, 부분 판단, 증명, 운영 통제를 함께 쓴다.
• 이 지식은 “어디까지 자동화할 수 있는가”의 경계를 알려 준다. 올바른 기대치를 세우고, 시스템을 현실적으로 설계하게 만든다.