A strict finite-state transducer image of the Thue–Morse word: A clock-rigidity proof of non-atomicity

We prove that the Thue–Morse degree is not an atom in the hierarchy of finite-state transducer degrees. For the word r(n) = p(3n), where p is the period-doubling word, we show 0 < [r] < [t]. The key new ingredient is a clock-rigidity theorem for transductions into the factor language of period doubling, combined with an odd-prime obstruction. This answers Open Problem 4 of Endrullis, Klop and Bakhshi (2019) and Shallit's 2014 question, and also resolves their Open Problem 1 on deleting every third letter. Version 1.1. Preprint, not yet peer reviewed. SHA-256 of the deposited files:nonatomicity_v1.1.pdfd2be3a25a34965991e2d3a06170a059249e6406e980d7d51b60b0a8c0ffa884cthue_morse_nonatomicity_v1.1_release.zip0741c42fcf90b2e707b38e3a61068b3c1f7c8f789095b43d79dc60c050b9e0aa