[FOM] Avoiding patterns/RCA/WKL

[Andrej Bauer]

According to Wikipedia a square free ternary sequence may be obtained
as the first difference of the Thue-Morse sequence, see
http://en.wikipedia.org/wiki/Squarefree_word.

This is quite easily computed, here is code in Haskell:

thuemorse :: Int -> Int
thuemorse 0             = 0
thuemorse n | even n    = thuemorse (n `div` 2)
thuemorse n | otherwise = 1 - thuemorse ((n - 1) `div` 2)

squarefree :: Int -> Int
squarefree n = 1 + thuemorse (n + 1) - thuemorse n

Here are the first 50 digits of the squarefree word computed:

take 50 (map squarefree [0..])
[2,1,0,2,0,1,2,1,0,1,2,0,2,1,0,2,0,1,2,0,2,1,0,1,2,1,0,2,0,1,2,1,0,1,2,0,2,1,0,1,2,1,0,2,0,1,2,0,2,1]

With kind regards,

Andrej


On Mon, Nov 12, 2012 at 3:08 PM,  <pax0 at seznam.cz> wrote:
> It is well-known that there is an infinite word not containing a square (avoiding the pattern xx)
> over the three letter alphabet {0,1,2}.
> My question is: Do we need WKL over RCA for this result?
> The intuition is that there is a finitely branching tree of square-free prefixes in which we have to find an infinite branch.
> But is WKL really used here?
> Thank you, Jan Pax
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom