Bijection between binary strings and pairs thereof
Python, 183

Bijection is cached on disk.

x=raw_input()
try:d=eval(open('d').read())
except:d={'':'','1 ':'1 '}
t='1 '*not' 'in x
if x not in d:
 while t in d:t+=`(id(t)/9)%2`
 d[t]=x;d[x]=t
 open(*'dw').write(`d`)
print d[x]


edit: Oops, looks like this isn't the first smartassed answer.  Mine's consistent between runs!