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...
They are definitely related and probably generated by DallE/CLIP. The images 0 and 3 clearly shows Turing and a beaver. Other (1,4) seems like “beaver+computer/machine” and I have no idea about 2.
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.
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.