They can be described with 2n \* log(4(n + 1)) bits, since each of the n states ... | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

		tromp on Dec 11, 2020 \| parent \| context \| favorite \| on: How the Slowest Computer Programs Illuminate Math’... 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.

cedilla on Dec 11, 2020 | [–]

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

lisper on Dec 11, 2020 | [–]

Right. I forgot about the halt state. But yeah, 6561 (=3^8) still looks mighty hinky.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact