3 ms·

I'm interested in that as well. On the other hand, all of that can only account for constant factors (in the limit, I can use some extra states to encode a lamb

I'm interested in that as well. On the other hand, all of that can only account for constant factors (in the limit, I can use some extra states to encode a lambda calculus interpreter in my Turing machine). Even for Turing machines, two symbols tapes might not be the most efficient in terms of BB steps per encoded machine bit. Having said all that, your encoding is a bit wasteful, so let's optimize. ;) First, there's really no need for the encoded states to end on bit boundaries. To give an example, to encode 9 numbers between 0 and 9 (inclusive), you don't need 9*ceil(log2(10))=36 bits, you only need ceil(9*log2(10))=30 bits by treating the digits as a large decimal number and converting that to binary. Second, if you're going to halt anyway, there's no need (at least for the BB problem) to write a symbol and move the tape on the last transition, so we can simply treat that as an alternative to encoding a transition. Armed with both of those, the size of an encoded machine goes down to ceil(2 * 6 * log2(2 * 2 * 6 + 1)) = 56 bits. (In general for n states and k symbols, ceil(k * n * log2(2 * k * n + 1)). The 2 is for the directions, the + 1 is the halting transition.)

tromp 4y ago
Yes, it's a bit wasteful. But importantly, it's straightforward, and it's what efficient universal Turing Machines would use in their input, so it makes sense for a comparison. Even the binary lambda coding allows for some optimization, like coding for variable 2 at depth 2 as 111 rather than 1110 since an occurrence of variable >= 3 would not make the term closed. > so we can simply treat that as an alternative to encoding a transition That's fine for the shift number but a lot of BB research concerns the number of 1s written rather than the number of steps taken, and there it matters. They prefer to use a single model for all variants.

tromp 4y ago

Yes, it's a bit wasteful. But importantly, it's straightforward, and it's what efficient universal Turing Machines would use in their input, so it makes sense for a comparison. Even the binary lambda coding allows for some optimization, like coding for variable 2 at depth 2 as 111 rather than 1110 since an occurrence of variable >= 3 would not make the term closed. > so we can simply treat that as an alternative to encoding a transition That's fine for the shift number but a lot of BB research concerns the number of 1s written rather than the number of steps taken, and there it matters. They prefer to use a single model for all variants.