PPL 143 / 177 permanent IDsPrize Problem Ledger · PPLChecked 2026.07.26
Prize Problem LedgerIndependentPPL 143Shallit #11 · Is the Thue–Morse word prime under transduction?

Permanent problem IDPPL 143

Source-statedIndependentconjecture

Formal languages

Shallit #11 · Is the Thue–Morse word prime under transduction?

Under finite-state transduction equivalence, is the Thue–Morse infinite word prime?

automata theorytheoretical computer scienceformal languages
01

The problem

Under finite-state transduction equivalence, is the Thue–Morse infinite word prime?

Open since2014source-stated by 2014
Last checked2026.07.26Catalog verification
02

Reward offers

Offer 01£20Jeffrey Shallit
Personal offer

Personal cash offer stated in Shallit’s official talk. The live talks page records subsequent updates, including a paid solution to one omitted problem; confirm claim procedure with the sponsor before relying on the award.

03

Sources & reading