FANDOM


Define inverse of busy beaver function, \(\Sigma^{-1}(n)\) as the minimum number of states needed to write n ones. This gives a sequence:

\(\Sigma^{-1}(1) = 1\)

\(\Sigma^{-1}(2) = 2\)

\(\Sigma^{-1}(3) = 2\)

\(\Sigma^{-1}(4) = 2\)

\(\Sigma^{-1}(5) = 3\)

\(\Sigma^{-1}(6) = 3\)

\(\Sigma^{-1}(7) = 4\)

\(\Sigma^{-1}(8) = 4\)

\(\Sigma^{-1}(9) = 4\)

\(\Sigma^{-1}(11) = 4\)

\(\Sigma^{-1}(12) = 4\)

\(\Sigma^{-1}(13) = 4\)

Note that \(\Sigma^{-1}(10)\) is not nesessarily 4, since it is possible that there is no TM with 4 states leaving exactly 10 ones. So, \(\Sigma^{-1}(n)\) may be not even strictly increasing!

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.