2025년 9월 19일·7분
앨런 튜링과 계산의 한계 설명
앨런 튜링의 핵심 아이디어—알고리즘, 판정 불가능성, 암호해독—과 그것들이 현대 컴퓨팅, 보안, 기계 지능에 어떤 영향을 미쳤는지를 살펴봅니다.
앨런 튜링의 핵심 아이디어—알고리즘, 판정 불가능성, 암호해독—과 그것들이 현대 컴퓨팅, 보안, 기계 지능에 어떤 영향을 미쳤는지를 살펴봅니다.
휴대폰이나 노트북으로 웹을 검색하고, 메시지를 보내고, 계정을 잠금 해제하고, 어시스턴트에게 도움을 요청하는 대부분의 일은 앨런 튜링이 명확히 한 질문들에 기초합니다: 계산이란 무엇인가? 원칙적으로 컴퓨터는 무엇을 할 수 있는가? 그리고 한계는 어디인가?
튜링이 오늘날에도 중요한 이유는 단순히 영리한 기법을 발명했기 때문만이 아닙니다. 그는 게임의 규칙을 정형화했습니다. 현대 소프트웨어 공학, 사이버보안, AI 연구는 사람들이 그의 이름을 언급하든 그렇지 않든 그 규칙을 물려받았습니다.
첫째는 계산입니다: 튜링의 단순한 계산 모델(“튜링 기계”)은 프로그램, 데이터, 알고리즘을 이야기할 수 있는 명확한 틀을 제공합니다. 이것이 노트북, 서버, 스마트폰 같은 매우 다른 장치들을 동일한 기본 아이디어의 변형으로 비교할 수 있게 하는 이유입니다—즉, 명령을 실행하는 범용 기계라는 점입니다.
둘째는 보안입니다: 제2차 세계대전 동안 튜링은 암호해독을 체계적이고 공학 중심적인 학문으로 바꾸는 데 기여했습니다. 그런 사고방식은 공격자가 무엇을 계산할 수 있는지, 그리고 그 계산이 얼마나 비용이 드는지 이해하는 것이 성공의 핵심인 현대 암호학과 보안 작업에 계속 반영됩니다.
셋째는 기계 지능입니다: 튜링은 여전히 AI 논의를 형성하는 실용적인 질문을 던졌습니다: 밖에서 보았을 때 지능적 행위를 어떻게 알아볼 것인가? 그의 “튜링 테스트”는 한계에 대한 논쟁이 있더라도 참고점으로 남아 있습니다.
이 가이드는 수학을 가볍게 다루고 직관을 강조합니다. 핵심 주제는 단순합니다: 컴퓨터는 매우 강력하지만 마법은 아닙니다. 어떤 문제들은 어떤 프로그램으로도 풀 수 없고, 더 많은 문제는 현실에서 사용할 수 없을 정도로 높은 비용을 요구합니다. 이러한 경계를 이해하면 기술 주장을 평가하고 작업에 맞는 도구를 선택하는 데 도움이 됩니다.
앨런 튜링(1912–1954)은 극적인 이야기로 도입되는 경우가 많지만, 그를 이해하는 가장 유용한 방식은 그가 직접 구축하고 증명한 것들을 통해 보는 것입니다. 그는 “무엇이 계산될 수 있는가”라는 질문을 정밀한 문제로 다루고, 답을 실제 기계 설계까지 이어간 수학자였습니다.
그의 1936년 논문 On Computable Numbers는 두 가지 지속적인 결과를 남겼습니다: 계산을 위한 추상 모델(현재의 튜링 기계)을 기술했고, 이를 이용해 일부 프로그램에 대한 질문은 일반적으로 해결 불가능하다는 것을 보였습니다. 이것은 공상과학이 아니라 논리와 계산의 한계에 관한 치밀한 주장입니다.
제2차 세계대전 중 튜링은 블레츨리 파크에서 암호해독에 참여했습니다—암호화된 메시지를 해독하는 방법을 찾는 작업입니다. 대중적 재현은 때때로 그가 "혼자서" 에니그마를 풀었다거나 "하룻밤에" 컴퓨터를 발명했다고 암시하지만, 실제는 더 흥미롭습니다: 그는 큰 노력의 핵심 기여자였고, 수학적 통찰을 반복 가능하고 운영 가능한 작업으로 바꾸는 방법과 전기-기계적 도구 설계에 기여했습니다.
튜링의 장점은 증명과 실무 사이를 오가는 능력이었습니다. 그는 종이 위의 이상화된 기계에 대해 추론한 뒤, 실제 시스템을 더 빠르고 안정적으로 만드는 절차와 하드웨어 제약을 설계하는 데 참여할 수 있었습니다. 형식적 사고와 실제 구현의 이 조합은 현대 컴퓨터 과학의 본보기입니다.
튜링의 아이디어는 여러 영역에 울림을 줍니다: 현대 컴퓨터 과학의 기초(계산 가능성 및 결정 문제), 초기 보안 사고(체계적 암호해독), 그리고 이후의 기계 지능 논쟁까지. 사람들이 그의 결론에 동의하지 않더라도, 흔히 그가 만든 틀을 사용해 논의를 전개합니다.
알고리즘은 결과를 얻기 위한 명확한 절차입니다. 반드시 "수학적"이거나 컴퓨터 관련일 필요는 없고, 신뢰할 수 있게 따라 할 수 있는 방법이면 됩니다.
차를 만드는 기본 레시피를 생각해 보세요:
이것이 알고리즘입니다: 순서대로 모호함 없는 단계들로 예측 가능한 결과를 얻습니다.
초기 기계들은 대개 단일 목적이었습니다: 한 가지 작업을 잘하도록 설계되어, 다른 작업을 하려면 다른 기계나 대대적인 개조가 필요했습니다.
범용 컴퓨터는 다릅니다. 여러 다른 알고리즘을 실행할 수 있도록 설계되어 하드웨어는 그대로지만 프로그램(명령)이 바뀝니다.
소프트웨어는 기본적으로 알고리즘을 기계가 정확히 실행할 수 있도록 기록하는 방식입니다. “3–5분 기다려라” 대신 프로그램은 “240초 기다려라”라고 말할 수 있고, “원하면 설탕” 대신 “사용자가 설탕을 선택하면 한 티스푼 추가”처럼 명시적 조건을 쓸 수 있습니다.
이 전환—명령을 기계가 저장하고 읽고 실행하는 것으로 취급하는 것—이 현대 컴퓨팅의 무대를 마련했습니다: 하나의 장치로 수많은 작업을 수행합니다.
오늘날의 vibe-coding 도구들에서 범용 아이디어가 구현된 것을 볼 수 있습니다: 모든 단계를 수동으로 쓰는 대신 목표를 설명하면 시스템이 이를 실행 가능한 소프트웨어로 변환합니다.
예를 들어, Koder.ai는 채팅 인터페이스로 웹, 백엔드, 모바일 애플리케이션을 빌드하고 소스 코드를 내보내 배포·호스팅까지 할 수 있게 합니다. 내부적으로는 결국 튜링의 틀로 귀결됩니다: 시스템은 궁극적으로 프로그램(알고리즘 + 데이터 + 제어 흐름)을 생성하며, 이것은 시간, 메모리, 보안, 정확성 같은 현실적 제약 속에서 실행되어야 합니다.
튜링 기계는 사고 실험으로 이해하는 것이 가장 좋습니다: 단계별로 무엇을 계산하는지를 잡아내기 위해 고안된 의도적으로 단순한 "상상 속 컴퓨터"입니다. 튜링은 이 장치를 직접 만들려 한 것이 아니라, 계산을 충분히 엄밀하게 정의해 증명을 할 수 있게 하려 했습니다.
무한히 긴 종이 조각(테이프)이 있고 정사각형으로 나뉘어 있다고 생각해 보세요. 각 칸에는 공백, 0, 1 같은 기호가 들어갈 수 있습니다. 읽기 헤드가 한 칸 위에 놓여 있습니다.
여기에 작은 지시 카드가 있어 헤드가 무엇을 할지 알려줍니다. 기계는 항상 소수의 상태 중 하나에 있습니다(예: 다음 숫자를 찾는 중 또는 종료 같은 "모드").
(현재 상태 + 현재 테이프 기호)의 각 조합에 대해 다음을 지시하는 규칙이 있습니다:
그게 전부지만, 적절한 규칙을 주면 이 기계는 우리가 알고 있는 어떤 알고리즘도 수행할 수 있습니다.
튜링 기계는 계산을 정의하는 명확한 방식입니다: 메모리 공간에 작용하는 유한한 기계적 규칙 집합. 이것은 하드웨어 설계도가 아니라 수학적 모델입니다.
모델이 매우 최소라서 증명에 강력합니다: 이 이상화된 기계로도 계산할 수 없다면, 일반적인 컴퓨터로도 계산할 수 없습니다.
현대 프로그램은 테이프와 헤드처럼 보이지 않지만 대응은 직관적입니다: 메모리는 데이터를 보관하고, 제어 흐름은 상태를 바꾸며, 명령은 기호를 변환합니다.
데이터베이스의 "저장 프로시저"조차 같은 패턴에 들어맞습니다: 고정된 규칙이 데이터를 읽고 갱신하며 정의된 단계로 진행합니다—계산은 반복 가능하고 규칙 중심적인 과정입니다.
프로그램에 관한 일부 질문은 기계적으로는 답이 있어야 할 것처럼 보입니다. 튜링은 중요한 종류의 질문들에 대해 그 희망이 불가능하다는 것을 보였습니다—우리가 충분히 똑똑하지 않아서가 아니라, 모든 입력에 대해 항상 정답을 내는 방법 자체가 존재할 수 없기 때문입니다.
문제가 **결정 가능(decidable)**하다는 것은 모든 입력에 대해 항상 끝나며 정답(예/아니오)을 내는 절차(알고리즘)가 있다는 뜻입니다.
문제가 **결정 불가능(undecidable)**하다는 것은 모든 경우에 대해 항상 정확히 답하는 알고리즘이 존재하지 않는다는 뜻입니다. 일부 사례는 풀 수 있어도, 모든 경우에 대해 작동하는 단일 방법은 만들 수 없습니다.
멈춤 문제는 묻습니다:
아무 프로그램과 그 입력이 주어졌을 때, 그 프로그램이 언젠가 멈출지 아니면 영원히 실행될지를 항상 판정할 수 있을까?
튜링은 그 답이 아니오라고 증명했습니다. 어떤 프로그램과 입력에 대해서도 항상 올바르게 멈춤을 예측하는 범용 판정기는 존재하지 않습니다.
일단 “모든 프로그램의 종료를 예측하는 것은 불가능하다”는 것을 받아들이면, 어떤 겉보기에는 합리적인 “완벽 분석” 도구들도 근본적으로 불가능하다는 사실을 이해하게 됩니다.
"범용 버그 탐지기"가 존재한다면, 어떤 프로그램을 넣어도 그 프로그램이 특정 종류의 버그를 가지는지 reliably(항상) 말할 수 있어야 합니다. 그러나 많은 버그 특성은 “이 프로그램이 어떤 상태에 도달하는가?”로 다시 표현할 수 있고, 이것은 멈춤 문제를 포함할 수 있습니다.
그래서 실제 도구들은 타협합니다: 불완전하게(몇몇 버그를 놓치고), 때때로 잘못 경고하거나, 혹은 제한된 종류의 프로그램에만 적용되도록 설계됩니다.
속성 예: "이 프로그램은 무한 루프에 빠지지 않는다." 어떤 도구가 모든 프로그램에 대해 이것을 완벽히 검증할 수 있다면, 그것은 멈춤 문제도 해결할 수 있었다는 의미입니다. 멈춤 문제가 결정 불가능하므로 일반적으로 완벽한 검사는 불가능합니다.
이것이 린터, 타입 검사기, 정적 분석기가 유용하지만 전능하지 않은 이유입니다.
튜링 이후의 핵심 교훈은 “계산 가능하다”가 “유용하다”를 의미하지는 않는다는 것입니다. 어떤 작업은 원칙적으로 가능(프로그램이 결국 끝남)하지만 너무 오래 걸리거나 메모리를 너무 많이 써서 현실적이지 않습니다.
모든 조합을 시도해서 퍼즐을 푸는 프로그램을 상상해 보세요. 언젠가는 답을 찾겠지만 조합 수가 컴퓨터 성능 향상 속도보다 빨리 늘어나면 ‘언젠가’는 우주의 나이보다 길어질 수 있습니다.
이것이 계산의 한계의 실용적 측면입니다: 해결책이 존재하는지가 아니라, 현실적 제약 안에 들어오는지가 핵심입니다.
모든 프로그램은 자원을 소비합니다:
종이에선 사소해 보이는 차이가 현실에서는 엄청난 차이를 만듭니다. 입력이 두 배가 됐을 때 일이 두 배로 늘어나는 방식은 관리 가능하지만, 제곱이나 그 이상의 성장은 금세 쓸모없어집니다.
컴퓨터 과학자들은 문제를 요구 시간이 어떻게 늘어나는지에 따라 그룹으로 나눕니다. 수학 없이도 아이디어는 간단합니다:
이러한 분류는 보통 복잡도 클래스로 논의됩니다—효율적으로 풀 수 있을 것으로 기대되는 문제들과 그렇지 않은 문제들을 구분합니다.
암호학에서는 어려운 문제가 장점입니다. 많은 보안 시스템은 한쪽은 쉽게(잠그기) 다른 쪽은 키 없이 푸는 것이 극도로 비싸도록(깨기) 설계됩니다.
따라서 복잡도는 우리가 빠르게 계산할 수 없는 것을 설명해줄 뿐 아니라, 적절히 활용하면 보안을 가능하게 합니다.
암호해독(cryptanalysis)은 비밀키 없이 암호화된 메시지의 의미를 복원하는 실무입니다. 제2차 세계대전 당시 이 작업은 매우 중요했습니다: 암호화된 통신은 계획과 명령, 정보 등을 담고 있어 수동으로 해독하기에는 너무 느렸습니다.
메시지를 제때 읽지 못하면 행동으로 옮길 수 없으므로 속도와 반복 가능성은 기발함만큼이나 중요했습니다.
좋은 암호는 메시지를 무작위 잡음처럼 보이게 하려 합니다. 암호해독은 현실이 어떻게 다시 유출되는지를 찾습니다: 언어의 패턴, 반복 형식, 예측 가능한 헤더, 시스템 사용 방식에서 나타나는 인간의 습관 등. 각 메시지를 개별 퍼즐로 보지 않고 데이터 문제로 다루는 접근이 핵심이었습니다.
실무적 접근은 세 가지 요소를 결합합니다:
여기서 초기 컴퓨터 과학적 사고가 드러납니다: 문제를 명확히 정의하고, 그것을 단계로 축소하며, 그 단계들을 사람보다 빠르게 실행할 시스템을 만드는 것입니다.
현대 보안도 동일한 사고방식으로 시작합니다: 영리하고 끈질긴 적대자가 있고 제약이 있다는 가정을 세웁니다. 수호자는 비밀 유지, 키 관리, 사용자 행동, 장치 무결성과 같은 가정을 세우고, 공격자는 가장 약한 가정을 찾습니다.
또한 절충의 세계입니다. 더 강한 암호화는 사용자에게 복잡성을 추가할 수 있고, 더 많은 모니터링은 프라이버시 문제를 일으킬 수 있습니다. 더 빠른 탐지는 오탐을 증가시킬 수 있습니다.
튜링 시대는 지속되는 교훈을 남깁니다: 보안은 단지 ‘최고의 알고리즘’이 아니라 시스템, 인센티브, 그리고 사람들이 실제로 어떻게 사용하는지에 관한 문제입니다.
튜링은 메시지가 문자 그대로 생사와 직결되던 시대에 일했습니다—그 압박은 현대 보안 목표와도 잘 맞습니다.
보안은 보통 몇 가지 단순한 아이디어로 귀결됩니다:
튜링 시대는 이런 것들이 무료로 주어지지 않음을 강조했습니다. 설계하고 압박 하에서 테스트해야 합니다.
현대 암호는 종종 큰 수의 인수분해처럼 한쪽은 쉽고 다른 쪽은 어렵다는 수학적 난이도에 의존합니다. 이것이 “수학적 자물쇠”입니다.
그렇지만 실제로 가장 약한 고리는 종종 “키”입니다. 키 관리는 키를 안전하게 생성하고, 복사되지 않게 저장하며, 필요할 때 교체하고, 문제가 생기면 신속히 폐기하는 일련의 문제입니다.
천재적인 알고리즘도 키가 유출되거나 패스워드가 재사용되거나 서버가 패치되지 않으면 무력화됩니다.
공격자는 적응합니다. 보안은 보통 완벽을 달성하는 것이 아니라 위험을 줄이는 것입니다: 공격을 비용이 많이 들게, 탐지 가능하게, 피해를 제한되게 만듭니다.
오늘날 공격자들은 과거 전문가 팀이 필요했던 작업들을 자동화합니다: 비밀번호 추측, 피싱, 수백만 시스템 스캔. 인터넷 규모에서는 작은 실수도 큰 사건이 됩니다—잘못 구성된 클라우드 저장소, 유출된 자격증명, 직원의 단 한 번의 클릭.
지속적인 공격을 가정하고 수학적 기법을 엄격한 운영 방침과 결합하는 것이 실용적 교훈입니다.
사람들이 컴퓨터가 "무엇을 할 수 있는가" 이야기할 때 보통 단순한 상상력을 말하는 것이 아닙니다. 처치–튜링 논제는 실용적인 규칙으로 그 선을 긋습니다: 어떤 작업이 계산 가능하다는 것은 올바른 답을 내는 단계별 절차(알고리즘)가 존재하고, 그 절차는 튜링 기계로 실행될 수 있다는 뜻입니다.
이름에도 불구하고 이것은 전형적인 수학적 증명으로 확정할 수 있는 것은 아닙니다—왜냐하면 형식 모델(튜링 기계)과 비형식적 개념(“모든 효과적 계산 방법”)을 연결하기 때문입니다. 대신 수십 년의 증거가 이를 뒷받침합니다: 새로운 계산 모델이 제안될 때마다(프로그래밍 언어, 회로 모델, 셀룰러 오토마타, 현대 CPU 등) 계산 가능한 문제의 집합은 동일하다는 것이 드러났습니다.
이 논제 덕분에 우리는 서로 다른 컴퓨터와 언어들을 상세한 차이로 헤매지 않고 비교할 수 있습니다. 두 시스템이 “튜링 완전(Turing-complete)”이면, 시간과 메모리가 충분할 때 같은 종류의 함수를 계산할 수 있습니다.
이 때문에 당신의 전화기, 노트북, 클라우드 서버는 속도, 비용, 규모에서는 다르지만 근본적으로 해결할 수 있는 문제의 종류는 다르지 않습니다.
처치–튜링은 모든 질문이 알고리즘적으로 풀린다는 약속을 하지 않습니다. 일부 문제는 *비계산적(uncomputable)*입니다(예: 멈춤 문제). 또 어떤 것이 계산 가능하더라도 입장에서 비현실적으로 느리다면 무용지물입니다—이건 복잡도 이론이 다루는 문제입니다.
튜링은 “기계가 생각할 수 있는가?”라는 질문이 모호하다는 것을 지적했습니다. “생각”은 감정, 이해, 창의성, 자기 의식, 혹은 단순히 좋은 답변을 내는 것 등 여러 의미를 가질 수 있습니다. 정의에 합의하지 못하면 명확한 시험을 만들 수 없습니다.
튜링은 모호한 질문을 실용적인 질문으로 바꾸자고 제안했습니다: 기계가 대화에서 지능적으로 행동할 수 있는가?
고전적 구성에서 인판(심판)은 텍스트로 숨겨진 두 참가자(한 명의 인간과 한 대의 기계)와 대화합니다. 심판은 질문을 자유롭게 하고 누가 인간이고 누가 기계인지 판단해야 합니다. 심판이 일관되게 구분하지 못하면 그 기계는 테스트를 통과한 것으로 여겨집니다.
이것은 지능을 ‘증명’하는 것이 아니라 특정 상호작용에서 구분 불가능한 성능을 달성할 수 있는지에 대한 측정 목표를 제시합니다.
튜링 테스트는 제약된 환경에서의 외형적 행동에 초점을 둡니다. 이것은 장점(관찰 가능)도 있지만 한계도 있습니다:
오늘날의 챗봇은 짧은 대화에서 인간처럼 느껴질 수 있어 튜링의 아이디어가 다시 주목받습니다. 하지만 평가의 함정도 드러납니다. 벤치마크는 스타일이나 테스트 형식에 익숙해짐으로써 ‘조작’될 수 있고, 대화에 능한 시스템이 사실 정확성이나 장기적 추론, 일관된 의사결정에서는 실패할 수 있습니다.
지속적인 교훈은 대화가 지능의 최종 잣대는 아니라는 것이고, 어떤 테스트가 실제로 무엇을 측정하는지에 대해 투명하고 신중해야 한다는 것입니다.
AI 시스템은 개방된 가능성을 가진 것처럼 보이지만 결국 프로그램 위에서 실행되므로 튜링이 명확히 한 동일한 경계를 물려받습니다. 그 경계는 무엇이 현실적으로 달성 가능한지, 무엇이 비용이 많이 드는지, 무엇이 원칙적으로 불가능한지를 결정합니다.
많은 AI 과제는 계산 가능하지만 비용이 큽니다: 모델 훈련, 답 검색, 계획 최적화는 막대한 시간과 에너지를 요구할 수 있습니다. 더 많은 데이터와 빠른 하드웨어는 도움이 될 때가 많습니다.
다른 목표는 더 근본적인 장벽에 부딪힙니다. 어떤 질문들은 모든 경우에 대해 일반 절차로 답할 수 없도록 판정 불가능성의 영역에 들어갑니다. 예를 들어 “임의의 시스템이 절대 실패하지 않음을 증명하라”는 광범위한 클래스의 시스템에는 완전히 자동화할 수 없는 경우가 있습니다.
문제가 계산 가능하더라도 다루기 어려운(intractable) 경우가 있습니다: 필요한 시간이 너무 빠르게 증가해 더 많은 데이터나 더 빠른 하드웨어로도 해결되지 않습니다. 장기 계획, 철저한 검증, 특정 종류의 최악 사례 추론에서 이런 문제가 나타납니다.
AI는 근사나 추측을 할 수 있지만 보장(guarantees)은 비용이 많이 듭니다.
완벽한 보장이 제한되므로 평가는 불확실성 관리에 관한 문제가 됩니다: 오류율 측정, 희귀한 시나리오 스트레스 테스트, 시간이 지남에 따른 실패 모드 추적 등. 가장 어려운 버그들은 일반 벤치마크에는 잘 나타나지 않는 엣지 케이스에 숨어 있습니다.
보안 또한 이러한 한계에 의해 형성됩니다. 규칙만으로 모든 나쁜 행동을 완전히 걸러낼 수 없고, 모든 상호작용을 완벽히 검증할 수는 없습니다.
프롬프트 주입, 데이터 중독(data poisoning), 오용은 방어가 계층화되어야 함을 상기시킵니다: 모니터링, 접근 제어, 레드팀, 신중한 시스템 설계 등 단일한 완전한 테스트에 의존할 수 없습니다.
튜링의 작업은 종종 역사로서 가르쳐지지만, 계산이 무엇을 할 수 있고 못 하는지에 대해 명확하게 생각하는 "길 안내 규칙"으로 보는 것이 더 유용합니다.
1) 계산 가능성(무엇이 원칙적으로 가능한가). 튜링 기계는 어떤 문제가 단계별 절차로 해결 가능한지를 말하는 명확한 틀을 제공합니다. 멈춤 문제는 여기서 핵심적인 결과입니다: 프로그램에 관한 일부 질문은 아무리 노력해도 일반적으로 해결될 수 없습니다.
2) 복잡도(현실의 시간과 자원으로 무엇이 가능한가). 많은 과제는 계산 가능하지만 입력이 커질 때 시간·메모리·에너지가 폭발적으로 늘어나 현실에서 쓸 수 없게 됩니다. "작은 예제에서는 작동"이 현실에서는 실패할 수 있는 이유입니다.
3) 보안(한계가 우리를 어떻게 보호할 수 있는가). 현대 암호학은 실용적 한계에 기대어 작동합니다: 어떤 시스템을 깨는 것이 불가능한 것이 아니라, 규모에서 너무 비싸고 느리게 만든다는 점입니다. 튜링의 암호해독 경험은 공격자가 수학, 공학, 그리고 운영적 요령을 사용한다는 점을 상기시킵니다.
계산 문제에 직면하면 먼저 세 가지를 질문하세요:
더 깊이 파고들고 싶다면 다음 주제를 권합니다:
컴퓨팅의 발전은 실제입니다—더 빠른 하드웨어, 더 나은 알고리즘, 더 강한 보안 도구. 그 한계들도 현실입니다. 이를 이해하는 것은 실용적 이점입니다: 적절한 도구를 고르고, 현실적인 기대를 설정하며, 수학을 무시한 약속에 속지 않도록 해 줍니다.
튜링 기계는 최소한의 추상적 계산 모델입니다: 테이프(메모리), 읽기/쓰기 헤드, 그리고 유한한 규칙(상태 집합)으로 구성됩니다. 이것은 특정 하드웨어나 프로그래밍 언어와 무관하게 “프로그램”이 원칙적으로 무엇을 할 수 있는지를 정확하게 말할 수 있게 해 줍니다.
처치–튜링 논제는 효과적인 단계별 절차로 계산할 수 있는 모든 것이 튜링 기계로도 계산 가능하다는 주장입니다. 이는 엄밀한 정리로 증명되는 것은 아니며, 여러 계산 모델(CPU, 프로그래밍 언어, 회로 등)이 동일한 계산 가능성 집합을 보인다는 수십 년의 경험으로 지지되는 경계 설정의 아이디어입니다.
“계산 가능하다(computable)”는 답을 내는 알고리즘이 존재하여 결국 정답을 낸다는 뜻입니다. “효율적으로 계산 가능하다(efficiently computable)”는 입력이 커질 때 시간과 메모리 면에서 실용적인 범위 안에 들어오는 것을 의미합니다. 많은 실제 실패는 이 둘을 혼동해서 발생합니다—계산 가능하지만 비용이 기하급수적으로 커져 쓸 수 없는 경우가 많습니다.
멈춤 문제는 모든 프로그램과 그 입력에 대해 그 프로그램이 언젠가 멈출지(종료할지) 아니면 영원히 실행될지를 항상 결정할 수 있는 범용적인 알고리즘이 존재하는지를 묻습니다. 튜링은 그런 범용 판정기는 존재할 수 없음을 증명했습니다. 실제로 이것이 의미하는 바는 임의의 코드에 대해 완벽한 정적 분석을 만드는 것이 본질적으로 불가능하다는 것입니다.
많은 버그 속성은 “이 프로그램이 특정 상태에 도달하는가?”로 다시 표현될 수 있고, 이는 멈춤 문제를 포함할 수 있습니다. 따라서 “모든 버그를 잡는 범용 버그 탐지기”는 존재할 수 없습니다. 실제 도구들은 보통 다음 중 하나를 택합니다:
그래서 정적 분석 도구는 매우 유용하지만 전능하지는 않습니다.
복잡도는 입력 크기와 함께 자원이 어떻게 증가하는지를 뜻합니다(주로 시간과 공간). 작은 차이가 규모가 커지면 지배적이 될 수 있습니다—예를 들어 입력이 두 배가 될 때 수행 시간이 두 배가 되는 것과 제곱이 되는 것은 현실에서 전혀 다른 결과를 낳습니다. 그래서 장난감 예제에서는 괜찮았던 방법이 실제 데이터에서는 비실용적이 되는 경우가 흔합니다.
현대 암호학은 보통 키 없이 되돌리기가 매우 어려운 문제들에 기대어 설계됩니다. 즉, 특정 작업은 키가 있으면 쉽고(잠그기), 키 없이는 매우 비용이 많이 듭니다(깨기). 이 ‘비용 격차’는 복잡도 가정에 기반하며, 공격자가 이론적으로는 계산 가능해도 현실적인 시간·예산 안에서는 해낼 수 없다는 점을 이용합니다.
튜링의 암호해독 작업은 지속적으로 다음 세 요소를 결합하는 접근을 보여주었습니다:
오늘날의 보안 관점도 동일합니다—문제 정의, 데이터 기반의 패턴 찾기, 그리고 자동화된 대규모 검색과 검증.
튜링 테스트는 제약된 대화 환경에서 기계가 인간과 구별할 수 없는 대화 행동을 보일 수 있는지를 평가합니다. 이것은 외형적 행동을 측정하는 유용한 벤치마크이지만, 이해, 자각, 진실성 등 내적 상태를 직접 측정하지는 않습니다. 또한 스타일과 설득력으로 테스트를 ‘속일’ 수 있다는 한계도 있습니다.
AI 시스템도 프로그램 위에서 실행되므로 계산 가능성과 복잡도의 한계를 물려받습니다. 보편적·완벽한 보증(예: "어떤 상황에서도 절대 실패하지 않는다")을 주기는 어렵고, 일부 검증 목표는 넓은 클래스의 시스템에 대해 판정 불가능성에 걸립니다. 실무에서는 테스트, 모니터링, 다층 방어, 명확한 가정 설정 같은 위험 관리 접근이 필요합니다.