Proof Linear: Execution of computer program

• $\mbox{state}_0$ given by inputs
• Program $=$ sequence of instructions, change state
• program $l$ states long
• terminates at state $\mbox{state}_{l-1}$
• program itself need not be linear

  branches, loops, function calls OK provided executes random instructions