Integer Complexity and Turing Machines

[Joshua Searle]

SeqFans,

Recently I was thinking about integer complexity - the smallest number of 1s that generate a given integer given a set of operations. A number of sequences related to this exist on the OEIS. Not so much when you look at something analogous with turing machines, though this isn't especially surprising given how difficult they are to calculate.

There are many ways you could implement a sensible measure of kolmogorov complexity on a turing machine. For example, you could create a sequence of "the minimum number of states required for a 2-state turing machine with an infinite blank tape to print the binary representation of n and then halt", or "minimum no. states to print a string of n 1s (and then halt)".

In the latter ruleset, there are some obvious ways you can create variants of it. Do the 1s need to be printed sequentially, or in an order or direction? Should the string begin at the starting point or can it be anywhere on the tape? are other 1s on the tape not part of the string permitted? What about just having n 1s somewhere on the tape? 

One rule that seems particularly promising to me is a heavily restricted one. The machine must work within a bound of n-1 spaces to the right of the starting position (the start being position 0) and must ultimately turn them all into 1s and then halt (though it may do so in any order, though fixing the order is another option). As a vast majority of machines would exceed the bounds, you could discard them without needing to know whether they halt or not. I imagine you would eventually come across problem cases, but I would think we would have good guesses for the terms for a little while - though I may be greatly underestimating how gnarly these things get considering the number of states.

I would assume it begins 1,2 and then continues being n for a few more terms before deviating.

Joshua Searle.

[Allan Wechsler]

On a different list, I proposed the same idea as a New Year's contest: players compete by submitting Turing machines that start on a blank tape, write 2026 1s on it (I preferred the formulation that doesn't care where they are) and halt. The machine with the fewest states wins.

There was a fair amount of speculation. Obviously you can do it in 2026 states. Somebody pointed out that you could spend 45 states writing a block of 45 1s. Then you could square that number (there are a couple of fairly easy strategies for this), add one more 1, and quit. I spitballed this to be about 60 states.

Then I suggested spending a dozen states to write 2026 in binary: 1111101010. Then you implement a binary counter (two or three states at most), and decrement this binary number, adding a 1 to the final output at each step. I estimated this approach to take only 20 states in total.

At this point another contributor expressed confidence that it could be done in 5 states, citing the enormous number (on the order of 10^15) of possible 5-state machines. I argued that it wasn't obvious that 2026 would be among the possible outputs -- we needed to know more about the statistics of these machine's behavior. Perhaps they almost all write only a few 1s before quitting. The 1-counting version of the Busy Beaver function of 5 is 4098, but it seemed likely to me that this was an outlier, not typical.

 The conclusion was that we would probably never know the theoretical minimum; we won't even know if it's possible in six states because there are just too many machines to canvas.

The conversation was ultimately disappointing to me, because nobody ever actually submitted any candidate machines.

-- Allan

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/1ba01aaa-1b78-41eb-85f0-95a502efc592n%40googlegroups.com.

[Jeffrey Shallit]

This is essentially the busy beaver problem, very well studied, and many variants have been studied.

On Sun, Sep 27, 2026 at 3:07 PM Joshua Searle <jprs...@gmail.com> wrote:

--

[Joshua Searle]

The line "the minimum number of states required for a 2-state turing machine..." should of course read "the minimum number of states required for a 2-*symbol* turing machine...".

Allan, your contest puzzle couldn't be done in 5 states. According to this list [https://wiki.bbchallenge.org/wiki/BB(5)] there are none that print 2026 1s. There are 19 that print in the range 4096 to 4098 and then it drops down to 1471 for the 20th highest. For 6 states, I'm not sure but I did find a list of the top 2000 or so [https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/6x2.txt] which if I am reading it correctly that the final number is the number of 1s and they are ordered by that, none are 2026. The list appears a little out of date though as the top two are not listed, it is possible more are missing but I wouldn't think there would be for a relatively small amount of 1s so it should be fine?

> This is essentially the busy beaver problem, very well studied, and many variants have been studied.

This is true, there are a number of listed examples here: [https://wiki.bbchallenge.org/wiki/Category:Functions] but they are in most cases as far as I can see, not highly restrictive rules as I suggested.

The reason I was considered such rule was because in a certain sense, BB record holders are almost chance based machines - where it just so happens that within a huge number of machines, a few happen to generate large outputs. With a highly restrictive ruleset, designed machines are likely to win out for a reasonable amount of terms, which makes them more interesting from an algorithmic point of view, and more tractable (at least initially), which would be more amenable to having an OEIS sequence. I suspect that it would be relatively easy to create a conjectured list of terms that are likely to be correct, but quite difficult to prove that none of the "wild" ones can beat them.

Joshua Searle.