What Turing machine would output all possible mathematical structures?
“Loop infinitely, incrementing count from 1: [Let steps be count. Iterate all legal programs until steps = 0 into prog: [Load submachine state from “cache tape”. Execute one step of prog, writing output to “output tape”. Save machine state onto “cache tape”. Decrement steps.] ]”
The output of every program is found on the output tape (albeit at intervals). I’m sure one could design the Turing machine so that it reordered the output tape with every piece of data written so that they’re in order too, if you want that. Or make it copypaste the entire output so far to the end of the tape, so that every number of evaluation steps for every Turing machine has its own tape location. Seemed a little wasteful though.
“Loop infinitely, incrementing
countfrom 1: [Letstepsbecount. Iterate all legal programs untilsteps= 0 intoprog: [Load submachine state from “cache tape”. Execute one step ofprog, writing output to “output tape”. Save machine state onto “cache tape”. Decrementsteps.] ]”The output of every program is found on the output tape (albeit at intervals). I’m sure one could design the Turing machine so that it reordered the output tape with every piece of data written so that they’re in order too, if you want that. Or make it copypaste the entire output so far to the end of the tape, so that every number of evaluation steps for every Turing machine has its own tape location. Seemed a little wasteful though.
edit: THANK YOU GWERN . This is indeed what I was thinking of :D