Efficient Markov chain model of machine code program execution and halting

We focus on the halting probability and the number of instructions executed by programs that halt for Turing-complete register based machines. The former represents the fraction of programs which provide useful results in a machine code genetic programming system. The latter determines run time and whether or not the distribution of program functionality has reached a fixed-point. We describe a Markov chain model of program execution and halting which accurately fits empirical data allowing us to efficiently estimate the halting probability and the numbers of instructions executed for programs including millions of instructions. We also discuss how this model can be applied to improve GP practice