All Programs

• All possible programs of $l$

  average vector $u=\mbox{Mean of all } v$

  $u^{t+1}=u^{t}M$ where $M$ is average instruction matrix

• $u$ is Markov, M is stochastic

  At least one $M_{ii} \neq 0$

  period of state $i=1$ i.e. it will be aperiodic [Feller, 1970]

  Greatest common divisor (g.c.d) of all states $=1$

• All states can be reached $\Rightarrow M$ irreducible
• Irreducible ergodic Markov chain $\Rightarrow \lim_{t \rightarrow \infty} u^{t}=u^{\infty}$
  independent of the starting state (i.e. the program's inputs)