Turing Machines as Stochastic Processes and Stepping Stones

Abstract: Deterministic Turing machines and their associated complexity measures, by construction, cannot capture the complexity of the output of stochastic processes - like those in the real world. Motivated by this observation, we combine probabilistic Turing machines with a prior over the inputs to the Turing machine to define a complete stochastic process of Turing machines. We call this a stochastic process Turing machine. We use stochastic process Turing machines to define a set of new generative complexity measures based on Turing machines, which we call stochastic depth. We discuss the application of this framework to the "stepping stone" effect in the evolution of complex systems. This effect refers to the fact that it is often easier for natural or artificial selection to generate a complex system if it first evolves precursor states, which act as stepping stones for that evolution. Examples of stepping stones include the evolution of words before language, cells before multicellularity, and transistors before computers