1
AD 1928장면 1 / 4같은 연도의 세계에서 이어 보기
힐베르트 — 결정 문제(Entscheidungsproblem)
"모든 수학 명제의 참·거짓을 기계적으로 결정하는 알고리즘이 있는가?" 힐베르트의 마지막 큰 질문.
정확한 장소가 없어 거짓 핀 대신 시간만 이어지는 장면
같은 연도의 세계에서 이어 보기이 개념의 출항 질문
풀 수 있음의 경계 찾기1 / 5번째 항구“절차만 정확하면 모든 질문은 언젠가 풀릴까?”
두 직관이 부딪히는 곳
계산이 무엇인지 엄밀히 정의하자, 오히려 어떤 프로그램도 일반적으로 판정할 수 없는 문제가 증명되었다.
이 항로는 이해를 돕는 편집 경로입니다. 직접적인 역사 영향선이나 한 사람의 단독 발명을 뜻하지 않습니다.
한 호흡으로 이해하기
"어떤 함수를 알고리즘으로 계산할 수 있는가." 1936년 튜링은 종이와 연필로 하는 계산을 이상화한 기계를 제시하고 결정 문제의 한계를 보였다. 오늘날의 정지 문제 표현으로 말하면 임의의 프로그램이 멈출지 판정하는 일반 알고리즘은 없다. 당시에도 계산 기계는 있었지만, 이 논문은 보편 계산의 추상 모형을 선명하게 했다.
한눈에 보기
문제 | 결정 가능? | 비고 |
|---|---|---|
소수 판별 | ✓ | 에라토스테네스의 체 |
정렬·검색 | ✓ | 효율 차이만 있을 뿐 |
정수해 다항식 (디오판투스 #10) | ✗ | 힐베르트 10번 — 1970 마티야세비치 |
정지 문제 (Halting Problem) | ✗ | 튜링 1936 — 대각화 논법 |
두 프로그램이 같은 일을 하는가 | ✗ | 라이스 정리 (모든 비자명 의미적 속성) |
단어 문제 (군론) | ✗ | Novikov 1955 |
결정 불가능한 문제들이 예외가 아니라 압도적 다수. 결정 가능한 게 희귀한 보석.
개념
"일정한 절차로 풀 수 있는 문제는 무엇인가?"에 대한 수학적 연구. 계산 기계가 이미 존재하던 1936년, 처치와 튜링은 서로 다른 형식 모형으로 알고리즘의 능력과 한계를 선명하게 했다.
핵심 식
계산 가능 ⟺ 튜링 기계로 풀림
시간의 항구
이 개념은 한 번에 발명되지 않았습니다
장면을 따라가면 문제, 표기, 증명 기준과 쓰임이 서로 다른 장소와 시대에서 어떻게 바뀌었는지 보입니다.
2
AD 1936장면 2 / 4같은 연도의 세계에서 이어 보기
처치·튜링 — NO (독립 증명)
같은 해 알론조 처치(람다 계산법)와 알란 튜링(튜링 기계)이 독립적으로 "그런 알고리즘은 없다"를 증명.
정확한 장소가 없어 거짓 핀 대신 시간만 이어지는 장면
같은 연도의 세계에서 이어 보기3
AD 1936장면 3 / 4같은 연도의 세계에서 이어 보기
튜링 — 튜링 기계의 정의
종이와 연필로 따르는 계산 절차를 이상화한 추상 기계를 제시했다. “효과적으로 계산 가능하다”는 직관과의 일치는 Church–Turing 명제로 구분한다.
정확한 장소가 없어 거짓 핀 대신 시간만 이어지는 장면
같은 연도의 세계에서 이어 보기4
AD 1971장면 4 / 4같은 연도의 세계에서 이어 보기
P vs NP — 새로운 미해결 문제
쿡-카프 등이 효율적으로 풀 수 있는 문제와 효율적으로 검증 가능한 문제가 같은가의 질문 제기. 100만 달러 밀레니엄 문제.
정확한 장소가 없어 거짓 핀 대신 시간만 이어지는 장면
같은 연도의 세계에서 이어 보기오늘날의 응용
컴파일러 설계의 한계, 자동 정리 증명 시스템, AI의 이론적 한계, 프로그래밍 언어의 표현력 분석.
MathVoyage 너머로
큐레이터가 고른 원전과 탐구 과제. OEIS·Project Euler·MathOverflow·arXiv에서는 발견 하나를 수첩으로 가져올 수 있습니다.
- 위키백과
- Wolfram MathWorld
- Numberphile
한 사람이 만든 개념이 아닙니다
역할이 다른 사람들을 따라가기
대표 연결은 발명자 명단이 아닙니다. 문제를 열고, 언어를 다듬고, 다른 세계로 옮긴 서로 다른 항구입니다.
수의 렌즈
같은 개념도 수의 세계가 바뀌면 다르게 보입니다
아래 수는 필수 선수 조건이 아니라 이 항로를 비추는 편집 렌즈입니다.
개념의 계보
무엇을 딛고, 무엇을 열었을까?
직접 연결만 표시하며 완전한 학습 순서나 역사 영향선을 뜻하지 않습니다.