News for hackers. Stuff that matters.

A comment on How the Slowest Computer Programs Illuminate Math’s Fundamental Limits. Parent comment

Re:How the Slowest Computer Programs Illuminate Math’s Funda... by tromp on Friday December 11, 2020 @11:28AM (#25387515)
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.
[ Parent | on HN ]
Re:How the Slowest Computer Programs Illuminate Math’s Funda... by cedilla on Friday December 11, 2020 @11:41AM (#25387669)
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

[ Parent | on HN ]
Re:How the Slowest Computer Programs Illuminate Math’s Funda... by lisper on Friday December 11, 2020 @11:38AM (#25387622)
Right. I forgot about the halt state. But yeah, 6561 (=3^8) still looks mighty hinky.
[ Parent | on HN ]