All Programs

• All possible programs of l

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

  u^t+1=u^tM 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)