I think one can convert any stopping Turing machine into a self-cleaning one with one more state and one more symbol, as follows:<p>Remove the halting state, replacing it by either of the following 2 new states that make the machine repeat these forever:<p>- walk left until a non-cleared cell, clearing any cell visited<p>- walk right until a non-cleared cell, clearing any cell visited<p>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)<p>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.<p>So, in total, that adds one state and one symbol.<p>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.