Thue-Morse Sequence

(Originally posted at on May 17, 2011 10:43 AM)

My undergraduate and master’s degrees are in electrical engineering.  Although my master’s thesis was on computer arithmetic and asynchronous circuits, I was also interested in pseudo-random number generators.

On March 29, 2004, I was thinking of how to simply generate an infinite non-periodic binary sequence.  I came up with the sequence obtained by starting with 0 then, at each succeeding step, replacing each 0 with 01 and each 1 with 10.

Because I had no formal training in pure mathematics or in theoretical computer science, I had never seen this sequence before and thought that I was the first to discover it.  But after reading my copy of Wolfram’s A New Kind of Science, I realized that I had stumbled onto the Thue-Morse Sequence.  Thus began my adventures with the field of study known as Combinatorics on Words


1 thought on “Thue-Morse Sequence”

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s