4 ms·

> 6,561 possible machines with two rules Huh? How do they get to that number? A TM state can be described with 4+2log2(N) bits, where N is the number of stat

by lisper 6y ago

> 6,561 possible machines with two rules Huh? How do they get to that number? A TM state can be described with 4+2log2(N) bits, where N is the number of states, so a 2-state TM can be specified with 12 bits, so there are at most 4096 of them. Where do the extra 2465 come from?

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 ago
  Right. I forgot about the halt state. But yeah, 6561 (=3^8) still looks mighty hinky.
- cedilla 6y ago
  A052200[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
tzs 6y ago
Probably its a 3 symbol Turing machine (0, 1, blank). For each rule, there are 3 possible inputs (0, 1, blank), 3 possible outputs (0, 1, blank), 3 possible movements (left, right, stay), and 3 possible next rules (rule 1, rule 2, halt). That gives 3^4 possible rules, or 3^4 3^4 = 3^8 = 6561 possible pairs of rules.
- lisper 6y ago
  Nope, that's not it. See the sibling comment from xjparker.
xjparker 6y ago
Hi, I'm the journalist who wrote the Quanta article. Scott Aaronson's Busy Beaver survey paper provides a function for calculating the total number of possible (2-symbol) Turing machines with n states: T(n)=(4n + 1)^2n. When n=2, T(n)=6,561. According to an email I got from Aaronson, this "allow[s] the possibility of halt states."
- lisper 6y ago
  Hm, interesting. I think the discrepancy comes about because Scott takes into account equivalence under state permutation, but I'd have to crunch some more algebra to be sure. In any case, I'd certainly accept Scott A. as an authoritative source on this. [UPDATE] No, that can't be it. A two-state machine has no equivalent permutations because one state has to be a privileged start state. And even if it did, there are only two permutations of two states, so this can't possible explain the discrepancy. [UPDATE2] Turns out there is a typo in Scott's formula. The correct answer is (4(n+1))^2n, not (4n+1)^2n. This is because each state transition has 4(n+1) possible values, 4 possibilities for the movement direction and symbol to write (with two possibilities each) and, independently, n+1 possible next states (including the halt state). The result for 2-state machines is, as /u/tromp correctly noted, 20736. [UPDATE3] (I think I'm about to set some kind of record here.) As a sanity check, it's pretty easy to see that the result has to be an even number because every possible TM has a corresponding distinct TM where the direction of movement or written symbol in any state is changed to the opposite value.
  - tzs 6y ago
    OK, I looked at Aaronson's paper. Here is his description of a Turing machine: > Following Radó’s conventions, we consider Turing machines over the alphabet {0, 1}, with a 2-way infinite tape, states labeled by 1, ... , n (state 1 is the initial state), and transition arrows labeled either by elements of {0, 1} × {L, R} (in which case the arrows point to other states), or else by “Halt” (in which case the arrows point nowhere). Note that under this definition when the machine halts it does NOT write the tape or move the head. That gives the machine 4n+1 ways to respond to a given input. If it is not halting, there are 4 actions it can take (0L, 0R, 1L, 1R) and n states it can go to. If it is going to halt, there is just one action. Hence, 4n + 1 possible responses. With two possible inputs, that's (4n+1)^2 possible rules, and with n rules that's (4n+1)^(2n) possible machines as given by Aaronson and used by the article's author, which is indeed 6516 when n = 2. For machines that do write and move even when halting, we can treat halt as an extra state, which gives the formula in your UPDATE2. For completeness we should consider machines that write but do not move on halt. Their formula is (4n+2)^(2n), or 10000 for n = 2. (That would also be the formula for rather pointless machines that move but do not write on halt).

by lisper 6y ago

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 ago
Right. I forgot about the halt state. But yeah, 6561 (=3^8) still looks mighty hinky.
cedilla 6y ago
A052200[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

tzs 6y ago

Probably its a 3 symbol Turing machine (0, 1, blank). For each rule, there are 3 possible inputs (0, 1, blank), 3 possible outputs (0, 1, blank), 3 possible movements (left, right, stay), and 3 possible next rules (rule 1, rule 2, halt). That gives 3^4 possible rules, or 3^4 3^4 = 3^8 = 6561 possible pairs of rules.

lisper 6y ago
Nope, that's not it. See the sibling comment from xjparker.

xjparker 6y ago

Hi, I'm the journalist who wrote the Quanta article. Scott Aaronson's Busy Beaver survey paper provides a function for calculating the total number of possible (2-symbol) Turing machines with n states: T(n)=(4n + 1)^2n. When n=2, T(n)=6,561. According to an email I got from Aaronson, this "allow[s] the possibility of halt states."

lisper 6y ago
Hm, interesting. I think the discrepancy comes about because Scott takes into account equivalence under state permutation, but I'd have to crunch some more algebra to be sure. In any case, I'd certainly accept Scott A. as an authoritative source on this. [UPDATE] No, that can't be it. A two-state machine has no equivalent permutations because one state has to be a privileged start state. And even if it did, there are only two permutations of two states, so this can't possible explain the discrepancy. [UPDATE2] Turns out there is a typo in Scott's formula. The correct answer is (4(n+1))^2n, not (4n+1)^2n. This is because each state transition has 4(n+1) possible values, 4 possibilities for the movement direction and symbol to write (with two possibilities each) and, independently, n+1 possible next states (including the halt state). The result for 2-state machines is, as /u/tromp correctly noted, 20736. [UPDATE3] (I think I'm about to set some kind of record here.) As a sanity check, it's pretty easy to see that the result has to be an even number because every possible TM has a corresponding distinct TM where the direction of movement or written symbol in any state is changed to the opposite value.
- tzs 6y ago
  OK, I looked at Aaronson's paper. Here is his description of a Turing machine: > Following Radó’s conventions, we consider Turing machines over the alphabet {0, 1}, with a 2-way infinite tape, states labeled by 1, ... , n (state 1 is the initial state), and transition arrows labeled either by elements of {0, 1} × {L, R} (in which case the arrows point to other states), or else by “Halt” (in which case the arrows point nowhere). Note that under this definition when the machine halts it does NOT write the tape or move the head. That gives the machine 4n+1 ways to respond to a given input. If it is not halting, there are 4 actions it can take (0L, 0R, 1L, 1R) and n states it can go to. If it is going to halt, there is just one action. Hence, 4n + 1 possible responses. With two possible inputs, that's (4n+1)^2 possible rules, and with n rules that's (4n+1)^(2n) possible machines as given by Aaronson and used by the article's author, which is indeed 6516 when n = 2. For machines that do write and move even when halting, we can treat halt as an extra state, which gives the formula in your UPDATE2. For completeness we should consider machines that write but do not move on halt. Their formula is (4n+2)^(2n), or 10000 for n = 2. (That would also be the formula for rather pointless machines that move but do not write on halt).