An infinite FTW

Haskell, 15 bytes

v%w=w++w%(v++w)

The infix function % produces an infinite string, which Haskell prints forever because Haskell is cool like that.

>> "1"%"0"
"010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101

The recursive idea is similar to Zgarb's solution. Writing f for the function %, and + for string concatenation, it implements:

f(v,w) = w + f(w,v+w)

The infinite output string starts with w, and the remainder of it is the result for the Fibonacci-shifted strings w and v+w.

This has no problem generating a million characters in a minute.

Pyth, 8 bytes

u,peGsGQ

Input in the form "W-1", "W0".

Proof of completion:

$ time pyth -cd 'u,peGsGQ' <<< '"1", "0"' 2>/dev/null | head -c1000000 > /dev/null

real    0m0.177s
user    0m0.140s
sys 0m0.038s

---

Proof of correctness:

Here is the series as internally generated. It is printed in concatenation by the program.

[0, 10, 010, 10010, 01010010, 1001001010010,...]

Compare to the following, printed in concatenation, which is simply the string added to the previous string on each step:

[0, 1, 0, 01, 010, 01001, 01001010, 0100101001001, ...]

We want to prove these are equivalent.

Clearly, they are the same through the first few steps. Let's compare them after a bit:

010
  010

10010
  01001

01010010
  01001010

1001001010010
  0100101001001

We see that the pairs of strings are alternately of the forms:

01a 10b
a10 b01

Where a and b are arbitrary sequences on 0s and 1s. Let's continue the sequence for a bit, to prove is continues forever by induction:

01a   10b   10b01a   10b01a10b
  a10   b01   a10b01   b01a10b01

2 steps later, it is of the correct form.

10b   01a   01a10b   01a10b01a
  b01   a10   b01a10   a10b01a10

2 steps later, it is of the correct form.

So by induction, the strings always match once concatenated.

Haskell, 31 bytes

w#v=v++drop(length v)(v#(v++w))

This defines an infix function # that takes two strings and returns an infinite string. Usage:

> let w#v=v++drop(length v)(v#(v++w)) in "11"#"000"
"000110000001100011000000110000...

If I query the millionth element of the sequence defined by "1" and "0", even the online interpreter prints the result in less than a second:

> let w#v=v++drop(length v)(v#(v++w)) in ("1"#"0") !! 1000000
'0'

Explanation

w#v=                             -- The result of w#v is
    v++                          -- v concatenated to
                      v#(v++w)   -- the infinite word v#(v++w),
       drop(length v)            -- with the first v characters dropped.

Basically, we know that w#v == v#(v++w) and w#v begins with v, and use these facts to define the result. Since Haskell is lazy, this "magically" just works.