2 ms·
They can be described with 2n * log(4(n + 1)) bits, since each of the n states has two rules, and each rule specifies a new binary symbol, a left or right direc
by tromp 6y ago
They can be described with 2n * log(4(n + 1)) bits, since each of the n states has two rules, and each rule specifies a new binary symbol, a left or right direction, and a new state which can also be the halt state.
For n=2, this gives 12^4 = 20736 machines. I have no idea where the number 6561 comes from.
- lisper 6y agoRight. I forgot about the halt state. But yeah, 6561 (=3^8) still looks mighty hinky.
- cedilla 6y agoA052200[1] lists the number of possible Turing machines and it agrees with you. I found no sequence containing 6561 and either "Turing" or "beaver" that illuminated me to where that number came from. 1: https://oeis.org/A052200 https://oeis.org/A052200