戦略型ゲーム$G$の無限繰り返しゲームにおけるプレイヤー$i$の機械（有限オートマトン）は、

• $Q_{i}$は状態の有限集合
• $q^{0}_{i}$は初期状態
• $f_{i}:Q_{i} \rightarrow A_{i}$は、状態から１つの行動を定める出力関数
• $\tau_{i}:Q_{i} \times A_{i} \rightarrow Q_{i}$は、状態と相手プレイヤーの行動の対から状態を定める状態遷移関数

からなる４つの組 $(Q_{i},q_{0}^{i},f_{i},\tau_{i})$である。

こう定義することで戦略の概念を機械の概念に置換することが出来る。そして、計算論、形式言語論とゲーム理論とを橋渡しすることが出来る。

Turing Machine