[FOM] Avoiding patterns/RCA/WKL
Andrej Bauer
andrej.bauer at andrej.com
Wed Nov 14 23:44:03 EST 2012
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
More information about the FOM
mailing list