No, most of my thinking about that was today. I’d be interested in a programming language where infinitely long programs have probability <1 of being equivalent to some finite program and have dynamics other than “keep running random instructions, achieve nothing of consequence” like what happens when you sample the target address for where your goto jumps to uniformly at random.
Potentially the structure/topology of address space matters in the infinite-program setting? That way may lie a derivation of physics.
I think any natural-number-indexed language where a nonzero fraction of instructions is “jump back 100 instructions” has almost all infinite programs equivalent to some finite program.
Just tried to prove it and I think you’re right. For example let’s say the instructions are “jump forward 1337” and “jump back 100″. Then, no matter where you are, “jump forward 100 times and then back 1337 times” would lead to a loop. So there’s a small but fixed chance that the immediately next instructions define exactly this loop, unless we run into a previously visited instruction which means we’re in a loop anyway. So over infinite time, almost all trajectories will fall into this loop or some other one. The proof generalizes to all languages in the obvious way.
EDIT: It’s fun to think about the limits of applicability of this. All that is needed is that instructions are i.i.d., all jumps are relative, and the chance of a loop is nonzero. Other than that we’re pretty free. For example, we could have countably many instructions: jump forward by BB(1) with probability 1⁄2, jump back by BB(2) with probability 1⁄4, jump forward by BB(3) with probability 1⁄8, jump back by BB(4) with probability 1⁄16… Then the expected time to loop is finite and not too large, but the expected distance to the loop is an infinity beyond comprehension.
This is a vague connection and possibly a misunderstanding, but the idea of imagining everything being inside one program and deriving physics from that kind of sounds like the Universal Dovetailer Argument, in case you haven’t heard of it.
That sounds applicable to any discussion of the Solomonoff prior at all; what I meant by deriving physics is that, by analyzing Turing-complete machine models for e.g. how well they handle infinities we might privilege hypotheses like our spacetime enough for papers like Max Tegmark’s On the dimensionality of spacetime to take us the rest of the way.
Nice. Is there a proof for that written up somewhere public?
No, most of my thinking about that was today. I’d be interested in a programming language where infinitely long programs have probability <1 of being equivalent to some finite program and have dynamics other than “keep running random instructions, achieve nothing of consequence” like what happens when you sample the target address for where your goto jumps to uniformly at random.
Potentially the structure/topology of address space matters in the infinite-program setting? That way may lie a derivation of physics.
I think any natural-number-indexed language where a nonzero fraction of instructions is “jump back 100 instructions” has almost all infinite programs equivalent to some finite program.
Just tried to prove it and I think you’re right. For example let’s say the instructions are “jump forward 1337” and “jump back 100″. Then, no matter where you are, “jump forward 100 times and then back 1337 times” would lead to a loop. So there’s a small but fixed chance that the immediately next instructions define exactly this loop, unless we run into a previously visited instruction which means we’re in a loop anyway. So over infinite time, almost all trajectories will fall into this loop or some other one. The proof generalizes to all languages in the obvious way.
EDIT: It’s fun to think about the limits of applicability of this. All that is needed is that instructions are i.i.d., all jumps are relative, and the chance of a loop is nonzero. Other than that we’re pretty free. For example, we could have countably many instructions: jump forward by BB(1) with probability 1⁄2, jump back by BB(2) with probability 1⁄4, jump forward by BB(3) with probability 1⁄8, jump back by BB(4) with probability 1⁄16… Then the expected time to loop is finite and not too large, but the expected distance to the loop is an infinity beyond comprehension.
This is a vague connection and possibly a misunderstanding, but the idea of imagining everything being inside one program and deriving physics from that kind of sounds like the Universal Dovetailer Argument, in case you haven’t heard of it.That sounds applicable to any discussion of the Solomonoff prior at all; what I meant by deriving physics is that, by analyzing Turing-complete machine models for e.g. how well they handle infinities we might privilege hypotheses like our spacetime enough for papers like Max Tegmark’s On the dimensionality of spacetime to take us the rest of the way.