초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.
어떤 프로그램으로도 풀 수 없는 문제가 있다고 말하려면 있을 수 있는 프로그램을 모두 한꺼번에 따져야 합니다. 명령어와 메모리가 많은 CPU로는 그러기 어렵습니다. 가장 단순한 기계부터 들여다봅시다.
동전을 넣어야 열리는 개찰구를 떠올려 봅시다. 잠긴 상태에서 동전을 넣으면 열리고, 열린 상태에서 밀고 지나가면 다시 잠깁니다. 순서 도어락 글의 도어락처럼 상태도로 그릴 수 있습니다. 입력을 받아 다른 상태로 옮겨 가는 화살표를 전이(transition)라 합니다.
지금 상태: 잠김
넣은 동전 0개 · 지나간 사람 0명
“동전”을 두 번 누르고 “밀기”를 눌러 봅시다.
동전을 두 개 넣어도 지나가는 사람은 한 명입니다. 개찰구는 동전을 몇 개 받았는지 기억하지 않고, 잠겼는지 열렸는지만 압니다. 사람을 지나가게 할지 정하는 데는 그것만 알면 됩니다.
정해진 몇 개의 상태와 전이 규칙만으로 움직이는 기계를 유한 오토마타(finite
automaton)라 합니다. 이 기계는 문자열(string), 즉 0110처럼 글자를 나란히
이은 것을 다음과 같이 다룹니다.
입력을 적어 둘 곳 없이 앞에서부터 읽기만 하니, 기억할 수 있는 것은 지금 상태 하나뿐입니다.
이 기계로 2진수가 3의 배수인지 판단해 봅시다. 수 전체가 아니라 지금까지 읽은 수를 3으로 나눈 나머지만 알면 되니 상태 세 개면 충분합니다.
지금 상태: 0 · 받아들임
아직 읽은 수가 없습니다(0으로 봅니다).
2진수 뒤에 비트를 하나 붙이면 수는 두 배가 되고 그 비트만큼 커집니다.
나머지 연산 글에서 본 대로 이 계산은 나머지끼리 해도
됩니다. 나머지가 2인 수 뒤에 0을 붙이면 나머지는 (2 × 2 + 0) mod 3 = 1입니다.
상태 2에서 0을 따라가면 상태 1로 가는 것이 이 계산입니다.
2진수를 앞자리부터 한 글자씩 읽어, 지금까지 읽은 수가 4의 배수인지 판단하는 유한 오토마타를 만듭니다. 글의 3의 배수 기계처럼 아무것도 읽지 않은 때는 0으로 보아 받아들입니다. 상태는 최소 몇 개면 될까요? 숫자로 답하세요.