다른 관점1/5
계산 가능성
절차만 정확하면 모든 질문은 언젠가 풀릴까?
AI 해석 일러스트
‘계산 절차’라는 말을 서로 번역 가능한 형식들로
알려진 후대 사진의 외형을 1936년 만 33세 무렵으로 재연령화했습니다. 함수 card와 tape는 람다 계산과 튜링의 독립적 기계 모형을 비유합니다. 형식 모형 사이의 동치 정리와 직관적 유효 절차에 관한 처치–튜링 명제는 같지 않으며, 명제를 물리 법칙에서 증명된 정리로 만들지 않습니다. 튜링의 독립 연구가 지도 관계보다 먼저였습니다.
MathVoyage editorial direction · OpenAI image generation · historical photograph identity reference · age and generated-text correction · 2026-08-07
연도보다 생각을 먼저 기억한다면
알론조 처치
Alonzo Church
AD 1903 - AD 1995
생각의 무대 · 프린스턴
태어난 곳 · 워싱턴 DC
현대함수를 접는 추상·적용 card치환 뒤 단순해지는 색 token독립 모형을 잇는 좁은 다리
먼저 기억할 생각
계산 가능성은 람다 정의 가능성과 튜링 계산 가능성에서 만난다.한 장면으로 들어가기
AD 1932
람다 계산 도입 — Set of Postulates for the Foundation of Logic
1932~1933년 논문에서 λ-추상과 적용을 포함한 형식 체계를 제시했다. 전체 논리 체계는 모순 문제를 겪었지만 함수 계산 부분은 독립적으로 발전해 오늘날의 무타입 람다 계산이 됐다.
이 사람이 열어 주는 질문
업적 목록 대신, 다시 탐험할 개념 항구
아래 연결은 직접 영향이나 단독 발명 계보가 아니라, 기존 개념 항로에서 이 인물이 맡는 편집 역할을 반대로 보여 줍니다.
PROFILE 02 · DEEP VOYAGE
알론조 처치의 생각이 움직인 길
연도를 더 외우는 대신, 한 사람을 만든 시대와 방향을 바꾼 장면, 다음 세대로 건너간 질문을 차례로 따라갑니다.
CHAPTER 01 · 사람과 시대
알론조 처치는 어떤 질문 속에서 살았을까?
완성된 업적보다 먼저, 이 사람이 무엇을 문제로 보았고 어디까지 확실하게 말할 수 있는지 읽습니다.
약 2분 읽기
“알고리즘으로 계산할 수 있다”는 일상어를 여러 형식 체계가 만나는 수학적 질문으로 바꾼 논리학자. 처치는 1930년대 초 람다 표기와 함수의 치환·축약만으로 계산을 표현하는 람다 계산을 발전시켰다. 1936년 람다 정의 가능성으로 결정 문제의 부정적 해답을 제시했고, 튜링은 독립적으로 추상 기계 모형을 제시했다. 두 모형과 일반재귀함수 등이 같은 계산 가능한 함수 부류를 준다는 것은 수학적 동치 정리다. 반면 ‘직관적으로 효과적인 모든 절차가 이 부류에 들어간다’는 교회–튜링 명제는 물리 법칙에서 증명되는 정리가 아니라 경험과 형식화가 뒷받침하는 논제다. 튜링 기계 역시 실제 장치가 아니라 종이·기호·상태로 계산을 모델링한 추상 수학이다. 람다 계산은 이후 함수형 프로그래밍과 언어 의미론에 큰 영향을 주었고, 처치는 학술지 편집과 클레이니·로서·튜링 등 제자 지도를 통해 논리학 공동체를 키웠다.
CHAPTER 02 · 전환의 장면
생각의 방향을 바꾼 4개의 장면
생각이 한 단계 이동한 순간을 시간순으로 펼칩니다. 모든 장면은 확인된 장소 또는 정직하게 표시한 시대 맥락에서 다음 항해로 이어집니다.
장면 1 / 4
AD 1932프린스턴람다 계산 도입 — Set of Postulates for the Foundation of Logic
1932~1933년 논문에서 λ-추상과 적용을 포함한 형식 체계를 제시했다. 전체 논리 체계는 모순 문제를 겪었지만 함수 계산 부분은 독립적으로 발전해 오늘날의 무타입 람다 계산이 됐다.
장면 2 / 4
AD 1936프린스턴Church's theorem — Hilbert 결정 문제의 부정 해답
람다 정의 가능성과 재귀함수의 관점에서 일반적인 결정 절차가 존재하지 않음을 보였다. 튜링은 독립적인 기계 모형으로 같은 부정적 결론에 도달했고, 형식 모형들의 동치가 이어서 확립됐다.
장면 3 / 4
AD 1936프린스턴Journal of Symbolic Logic 창간 — 43년 편집
1936년 Journal of Symbolic Logic 창간, 1979년까지 43년간 편집. 수리논리학·기초론의 세계 표준 학술지. 튜링·괴델·콰인·크리스의 주요 논문이 모두 여기에 게재. 처치 이후 편집장 Anil Nerode·Sol Feferman으로 계승.
장면 4 / 4
AD 1936프린스턴Turing의 박사 지도교수 — Princeton 1936-1938
튜링은 자신의 계산 가능성 논문을 완성한 뒤 프린스턴에 와 처치의 지도 아래 1938년 《순서수에 기초한 논리 체계》로 박사학위를 받았다. 독립 연구 뒤에 사제 관계가 형성됐다는 순서가 중요하다.
THOUGHT EXPERIMENT · 사실이 아닌 가정
알론조 처치의 이름을 지도에서 지운다면
아래 내용은 확인된 역사적 사실이 아니라, 이 인물의 영향을 생각해 보는 가정입니다.
초보자는 λx.x+1에 3을 넣어 치환한다. 중급에서는 α-변환과 β-축약으로 작은 프로그램을 계산한다. 고급에서는 람다 계산·튜링 기계·일반재귀함수 사이 번역을 만들고, 전문 단계에서는 계산 가능성의 동치 정리와 교회–튜링 명제, 결정 불가능성·타입 이론·프로그램 의미론의 경계를 구분한다.
STANDING ON SHOULDERS · 근거가 있는 연결
누구에게서 무엇을 받아, 어디로 건넸을까?
같은 시대였다는 이유로 선을 긋지 않습니다. 저작·문제·가르침으로 확인되는 연결만 문장과 근거로 보여 줍니다.
MathVoyage 너머로
큐레이터가 고른 원전과 탐구 과제. OEIS·Project Euler·MathOverflow·arXiv에서는 발견 하나를 수첩으로 가져올 수 있습니다.
- 위키백과
- MacTutor