How long are Long Programs?

Next: How long are Long

W. B. Langdon UCL

How long are Long Programs?
Summary
Distribution of Output of Linear 4 input logic (AND NAND OR NOR) programs
Proof Linear: Model of Computer
Proof Linear: Execution of computer program
Instructions as Transformation Matrices
All Programs
Rate of Convergence of Markov Processes
How big do programs have to be?
Memory
AND NAND OR NOR Binary inputs, 8 bit memory, inputs unprotected
AND NAND OR NOR Binary inputs, 8 bit memory, inputs unprotected
Conclusions
So what?
Without Write Protection, Random Linear Programs Longer than $\approx 2.3 {N}/{m}$
What is Total Variation Distance?
references
About this document ...

Bill LANGDON 2002-07-17