擬似乱数生成器

擬似乱数生成器とは、有限集合 $S$（状態の集合）、写像 $T:S\to S$（遷移）、$g:S\to V$（出力）、種の集合 $\Sigma$ から $S$ への写像 $\iota$（初期化）の組である。種 $\sigma\in\Sigma$ に対し

で定まる列 $(v_k)_{k\ge0}$ を、種 $\sigma$ の出力列という。

乱数を消費する決定的なプログラムとは、集合 $Q$（プログラムの状態）、初期状態 $q_0\in Q$、停止状態の集合 $Q_{\mathrm{halt}}\subset Q$、写像 $F:Q\times V\to Q$、$\mathrm{out}:Q_{\mathrm{halt}}\to Y$ の組である。生成器から値を 1 つ受け取るたびに $q_{k+1}=F(q_k,v_k)$ と進み、初めて $q_k\in Q_{\mathrm{halt}}$ となったところで $\mathrm{out}(q_k)$ を出力して止まる。