소수 판별 튜링머신
이번 SCTF(Samsung CTF)의 700점짜리 문제로 튜링머신 설계가 나왔다. 총 4개의 문제 중 3개는 일반적인 오토마타 교과서에서 다루는 언어들(ex: \(L=\{ 0^n1^n | n \geq 0 \}\))이었지만 마지막 단계인 \(L=\{0^p | p \, \mathrm{\,is\,prime}\}\)가 다소 많은 시간을 잡아먹었다. 사실상 소수 판별을 하는 튜링 머신을 설계하라는 문제였는데, 기억상 다른 교재들에서도 이에 대한 명확한 실례는 나와있지 않아 따로 정리했다. 아래 등장하는 그래프의 화살표에서 A/B . P는 “현재 state에서 알파벳 A를 읽었을 때, 테이프에 B를 쓰고 P방향(L, 또는 R)으로 이동한다"라는 의미를 가진다. 이제 필요한 서브루틴을 하나씩 구성해 보자.