TECH 으로 돌아가기
TECH HACKER NEWS 9분 읽기 68 READS

버그 없는 소프트웨어는 왜 이렇게 어려울까 — 복잡도 이론이 말해주는 '검증의 벽'

버그 없는 소프트웨어는 왜 이렇게 어려울까 — 복잡도 이론이 말해주는 '검증의 벽'
SOURCE IMAGE · HACKER NEWS
버그 없는 소프트웨어는 왜 이렇게 어려울까 — 복잡도 이론이 말해주는 '검증의 벽'

코드 쓰기는 쉬워졌는데, 맞는지 확인하기는요?

오라클에서 자바의 가상 스레드(Project Loom)를 이끈 엔지니어 론 프레슬러(Ron Pressler)의 에세이 "올바른 소프트웨어를 작성하는 것은 왜 어려운가"를 오늘 같이 읽어보려고 해요. 몇 해 전 강연을 글로 옮긴 건데, AI가 코드를 쏟아내는 요즘 오히려 더 와닿아요. 코드를 '쓰는' 비용은 뚝 떨어졌지만 그 코드가 '맞는지' 확인하는 비용은 그대로거든요. 이 글은 바로 그 확인 작업, 즉 검증이 왜 본질적으로 어려운지를 감이 아니라 이론으로 설명해요.

출발점: 프로그램이 뭘 할지 미리 알 수 없다

컴퓨터 과학에서 가장 유명한 결과 중 하나가 1936년 앨런 튜링의 정지 문제예요. 이게 뭐냐면, "아무 프로그램이나 주면 그게 언젠가 끝나는지 영원히 도는지 판별해주는 만능 프로그램은 만들 수 없다"는 증명이에요. 여기서 한 발 더 나간 라이스의 정리는 "이 함수는 절대 음수를 반환하지 않는다"처럼 프로그램의 동작에 관한 의미 있는 성질이 사실상 전부 같은 처지라고 말해요.

보통 여기서 이런 반론이 나와요. "실제 컴퓨터는 메모리가 유한하고 무한히 기다릴 일도 없으니 괜찮지 않나?" 프레슬러는 이 탈출구도 막혀 있다고 해요. "이 프로그램이 n단계 안에 끝나는가?"라는 질문은 답을 낼 수는 있지만, 복잡도 이론에 따르면 일반적으로 n단계를 직접 돌려보는 것보다 본질적으로 빠른 방법이 없거든요. 영화 결말을 알려면 결국 끝까지 봐야 한다는 얘기예요. 게다가 프로그램은 입력이 달라질 때마다 다른 영화가 되니, 가능한 경우를 전부 돌려봐야 하는 셈이죠.

상태 폭발: 몇 줄 늘었을 뿐인데 경우의 수는 우주만큼

상태(state)란 어느 한 순간 프로그램이 기억하고 있는 값 전체를 말해요. 문제는 그 개수예요. 불리언 변수가 하나면 상태는 2개, 열 개면 1,024개, 300개면 관측 가능한 우주의 원자 수보다 많아져요. 이걸 상태 폭발이라고 불러요. 코드는 고작 몇 줄 늘었는데 확인할 경우의 수는 지수적으로 불어나는 거죠. 그래서 모든 상태를 기계적으로 훑는 검증 기법인 모델 체킹은 이론적으로 아주 어려운 문제 부류(PSPACE)에 들어가요.

"사람이 짠 코드는 다르지 않나요?"

가장 흥미로운 대목이에요. 흔한 기대는 이렇죠. "최악의 경우는 이론가들이 만든 괴상한 프로그램 얘기고, 사람이 의도를 갖고 짠 코드는 구조가 있으니 쉬울 거야." 이 기대가 왜 틀렸는지는 아래 코드 하나로 알 수 있어요.

def collatz(n):
while n != 1:
n = n // 2 if n % 2 == 0 else 3 * n + 1

짝수면 반으로 나누고 홀수면 3을 곱해 1을 더하는 일을 1이 될 때까지 반복하는 세 줄짜리 함수예요. 그런데 이 함수가 모든 양의 정수에 대해 끝나는지는 '콜라츠 추측'이라는 미해결 수학 문제예요. 세계적인 수학자들도 아직 증명하지 못했어요. 코드가 짧고 읽기 쉽다고 해서 그 동작을 따지기 쉬운 건 아니라는 거죠.

그럼 언어를 잘 고르면 어떨까요? 함수, 모듈, 객체 같은 추상화는 같은 동작을 더 짧게 표현하게 해주는 도구예요. 그런데 표현이 간결해질수록 같은 줄 수 안에 더 많은 동작이 담기니, '코드 크기 대비 검증 난이도'는 오히려 올라가요. 그래서 프레슬러는 특정 언어나 패러다임이 검증을 일반적으로 쉽게 만들어준다는 주장에는 이론적 근거가 없다고 말해요. 함수형이든 객체지향이든 마찬가지고요.

정확성은 레고처럼 조립되지 않아요

큰 시스템을 다루는 기본기는 분할 정복이잖아요. A 모듈이 맞고 B 모듈이 맞으면 합친 것도 맞겠거니 하고요. 그런데 글이 소개하는 연구 결과에 따르면, 부품 각각을 검증하는 비용을 안다고 해서 합친 시스템의 검증 비용이 그 합 정도로 묶이지 않아요. 부품들이 상호작용하면서 새로운 상태 조합이 생기기 때문이에요. 단위 테스트는 전부 통과했는데 통합하니 터지는 경험, 다들 있으시죠? 운이 나빠서가 아니라 수학적으로 예정된 일이었던 거예요.

업계는 어떻게 타협하고 있을까요

프레슬러가 말하려는 건 "불가능하다"가 아니라 "공짜는 없다"예요. 실제로 업계는 무엇을, 얼마나 확실하게, 얼마를 들여 확인할지를 저울질하면서 여러 도구를 섞어 써요.

프레드 브룩스가 말한 '은탄환은 없다'에 수학적 뒷받침을 붙여준 글이라고 봐도 좋아요.

한국 개발자에게 주는 시사점

첫째, "이것만 쓰면 버그가 사라진다"는 말은 걸러 들으세요. 새 언어, 새 프레임워크, 새 AI 도구가 나올 때마다 듣는 얘기지만 이론은 그런 만능 해법이 없다고 해요. 대신 "이 도구는 어떤 종류의 버그를 얼마의 비용으로 막아주나?"를 묻는 습관이 훨씬 쓸모 있어요.

둘째, AI 코딩 도구를 쓸수록 검증에 시간을 더 쓰세요. 생성은 빨라졌지만 그 코드가 요구사항을 만족하는지 따지는 일의 난이도는 그대로예요. 리뷰하기 쉬운 작은 단위로 받기, 테스트부터 쓰게 하기, 속성 기반 테스트(무작위 입력을 대량으로 넣어 "정렬 결과는 항상 오름차순" 같은 규칙이 깨지는지 보는 방식) 붙이기가 그래서 중요해요.

셋째, 결제, 정산, 분산 락처럼 틀리면 크게 다치는 부분만이라도 한 단계 높은 검증을 시도해보세요. 전체에 정형 기법을 쓰는 건 비현실적이지만, 핵심 알고리즘 하나를 TLA+나 Alloy 같은 가벼운 명세 도구로 그려보는 건 주말에도 해볼 수 있어요.

마무리

한 줄로 정리하면, 버그 없는 코드가 어려운 건 우리가 게으르거나 도구가 나빠서가 아니라 문제 자체가 계산 이론적으로 어렵기 때문이에요. 그래서 좋은 엔지니어링은 완벽을 약속하는 일이 아니라, 어디에 얼마만큼의 확신을 살지 고르는 일이 되고요.

여러분 팀은 그 선을 어디에 긋고 계신가요? AI가 짠 코드가 점점 늘어나는 지금, 테스트와 리뷰만으로 충분하다고 느끼시나요?


🔗 출처: Hacker News

SOURCE · HACKER NEWS
원문 전체 보기 → https://pron.github.io/posts/correctness-and-complexity
SHARE
NEXT · CHOOSE

변화를 읽었다면,
내가 만들 수익 구조를 고릅니다.

정보를 더 모으는 데서 멈추지 않고, 광고·외주·판매·중개·구독 중 내 상황에 맞는 출발점을 정해보세요.

21가지 수익 구조 살펴보기 →
처리 중...