처치의 람다 계산과 같은 시기, 튜링은 사람이 규칙에 따라 기호를 조작하는 과정을 추상 기계로 표현했다. 두 서로 다른 모형이 같은 계산 가능 함수에 이른 사실이 ‘효과적 절차’의 수학을 굳혔다.
- 잠깐 멈춰 묻기
- 종이의 한 칸만 보고 정해진 규칙을 따르는 사람을 상상하면, ‘계산한다’는 행위를 가장 작은 동작들로 정의할 수 있을까요?
- 생각이 달라진 점
- 튜링은 무한 테이프, 읽고 쓰는 머리, 유한한 상태, 전이표로 사람의 규칙적 기호 조작을 추상화했습니다. 개별 기계를 부호로 읽어 여러 기계의 동작을 흉내 내는 범용 기계와, 어떤 기계가 멈출지 일반적으로 판정할 수 없다는 경계를 같은 틀에서 보였습니다.
- 말할 수 없는 것
- 튜링 기계는 1936년에 제작된 전자 컴퓨터가 아니라 계산 가능성을 연구하는 추상 모형입니다. ‘튜링 완전’은 빠르거나 지능적이라는 뜻이 아니며, 정지 문제는 특정 프로그램의 종료를 전혀 분석할 수 없다는 뜻도 아닙니다.
- 이 장소
- 케임브리지 King's College의 수학 교육, Max Newman의 기초론 강의, 도서관과 학술지 접근은 튜링이 계산자의 실제 동작에서 형식 모형을 끌어낼 조건을 주었습니다. 논문이 심사·출판되는 동안 처치의 독립 결과를 알게 되어 프린스턴으로 이어졌습니다. (캠강변 · 버드나무 · 평지 · 52.2°N 0.1°E)
- 강 위의 도해
- 끝없는 테이프의 한 칸만 읽는 머리와 유한한 상태, 전이표 한 줄이 기호를 쓰고 움직일 방향을 정한다.
- 강 위의 표시
- 쓰고 읽힌 기록을 올려 둔 책상 · 1900–1969년 (콘크리트 표지 · 전기 가로등 · 콘크리트 다리 · 송전탑과 아파트·라디오탑 · 바지선 · 비행기)