4 ms·
Another new record in self-cleaning Turing machines
- gitgud 5y agoSide 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...
- dEnigma 5y agoCan't find more than their names either. (sinister-math, workstation, denim-joint, water, office)
- mlajtos 5y agoThey 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.
- deleted 5y ago[deleted]
- dandanua 5y agoWow, 1 trillion steps in 1 second, that's amazing.
- kzrdude 5y agoHow is the actual program found, just randomly trying different program tables?
- kzrdude 5y agoIt turns out that a different post has a good answer! https://nickdrozd.github.io/2021/09/25/spaghetti-code-conjecture-false.html https://nickdrozd.github.io/2021/09/25/spaghetti-code-conjec...
- Someone 5y agoI 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.
- fjfaase 5y agoI 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.