>>19
帰着させる事ができるか、という問題か。
じゃぁ、次のプログラムは止まるか判定できるかな？

MAX : 定数
m ← 1
loop { m ← m+1 mod MAX }

mod MAX は MAX で割った余り。
まぁ、普通に考えれば状態数は MAX で済む。