一斉射撃問題
↑ なお厳密には、「指令」は単に片方の端にあるセルの、他と異なる初期状態という以上の意味はない。状態遷移関数の設計上の都合によっては、直感的に見て「指令」とは感じられないような他のセルの他の状態と共通の状態としてもよい。
↑ 少ない場合についても考えるのもよいが、初めのうちは数個以上を前提としたほうがいいだろう。
↑ Sequential Machines: Selected Papers https://dl.acm.org/citation.cfm?id=1102050
↑ これについてネット等ではthousandsないしmillionsといった表現が見られることもあるが、実際の検討によればそんなに多数を必要とはしない。『一斉射撃問題を解いてみる : 分かりやすい 8 状態最少時間解まで』で示されているナイーブな検討例では、25状態となっている。
↑ 岩波『ファインマン計算機科学』 p. 48