AFTD Auto-Formalizing Theoretical Domains

thue_morse_word

def

The n-th Thue-Morse word t_n over the alphabet {false, true}, defined recursively by t_0 = [false] and t_{n+1} obtained by replacing each false with [false, true] and each true with [true, false].

Statement

def thue_morse_word : ℕ → List Bool
Defined in
arXiv:2610.10950
Verified
29 Oct 2026
Axioms
none listed
Used by 7

Read back from the Lean

A function thue_morse_word from the natural numbers ℕ to List Bool, defined recursively by: - thue_morse_word 0 is [false]; - thue_morse_word (n + 1) is the concatenation of the lists obtained by replacing each element b in thue_morse_word n with [true, false] if b = true, and with [false, true] if b = false.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The n-th Thue-Morse word of length 2^n over {false, true}. -/
def thue_morse_word : ℕ → List Bool
| 0 => [false]
| n + 1 => (thue_morse_word n).flatMap (fun b => match b with | true => [true, false] | false => [false, true])
See it in the graphDiscuss this resultChallenge it