Another new record in self-cleaning Turing machines

I think one can convert any stopping Turing machine into a self-cleaning one with one more state and one more symbol, as follows:

Remove the halting state, replacing it by either of the following 2 new states that make the machine repeat these forever:

- walk left until a non-cleared cell, clearing any cell visited

- walk right until a non-cleared cell, clearing any cell visited

Finally, you have to cater for the case where the stopping machine goes through a state where the tape is empty before stopping (yes, that can happen, but since the machine eventually stops, that means it has to be in a different state every time that happens)

You can do that by introducing a pseudo-blank symbol that is treated the same as the ‘real’ blank, and writing that whenever the stopping machine writes a blank.

So, in total, that adds one state and one symbol.

If so, that puts a lower bound on the record for self-clearing Turing machines with S states. It can’t be less than that for stopping ones with one fewer states and one fewer symbols. I don’t think that bound is tight.

Side note: Those AI generated images are interesting, but there's no mention of them anywhere, which is confusing as they're not quite abstract enough to be unrelated...

I have been analyzing the Turing machine and it is indeed a rather simple loop that implements a Collatz-like function. In the loop a number is divided by two and then multiplied by five where there is a slight difference in the behaviour depending on whether the number is odd or even. It seems there is a second variable that also plays some role. I have not figured out the exact behaviour yet. In inside this loop there are some nested loops. Most of the steps occur in these nested loops.

Wow, 1 trillion steps in 1 second, that's amazing.

How is the actual program found, just randomly trying different program tables?