This is one of my two submissions to OPC-5. And now, here is the solution file:

Solution
--------

This program computes the Fibonacci numbers, using regexps.

First, I'll prove that $_ contains only 0's, 1's and 2's, and
that all other digits are there for obfuscation purpose only.

Then, I'll prove that the numbers of 0's and 1's are 
Fibonacci numbers.

Lastly, I'll explain the result.

1 Which digits?
---------------

We start with a string which looks like "12222221" (with six 2's, 
because we want to compute fib(6)).

This string contains substrings belonging to the following set:
"0", "1", "2", "00", "01", "10", "11", "02", "12", "22" and "21".

Of these substrings, only "0", "1", and "21" can match the regexp.
For these three substrings, the formula gives:
    0  -> 10
    1  ->  0
    21 ->  1
The resulting string will therefore contain substrings belonging to
the same set. And the de-obfuscated lines would read:
    while (/1$/){s=(2?[01])=int(abs((67*$1-1467)*$1+1423)/140)=eg}
    y/02//d;

2 How Fibonacci is computed
---------------------------

Theorem: at the end of the i-th iteration, the string contains
           fib(i-1) "1"s
mixed with fib(i) "0"s
      then (n-i) "2"s
      then either a "1" or a "0"

Demonstration: at the start of the program, the string contains a
single "1", n "2"s and another "1". After the first iteration,
the string contains a single "0", (n-1) "2"s and a "1".
That is, the first part of the string contains 0 "1"s (and 
fib(1-1) = 0) and only one "0" (fib(1) = 1).

Suppose this is true for i, we show it remains true for j=i+1.

- In the first part of the resulting  string, all "1"s come 
from the substitution 0 -> 10. There were fib(i) "0"s in the
original string, therefore there are fib(i) = fib(j-1) "1"s in
the resulting string.

- In the first part of the resulting string, all "0"s come
either from the substitution 1 -> 0 (fib(i-1) such substitutions), 
or from 0 ->10 (fib(i) such substitutions). Therefore, in the
resulting string, there are fib(i-1) + fib(i) "0"s, that is
fib(i+1) or fib(j).

- In the second part of the original string, only the last "2"
match the regexp. Actually, this "2" and the last "1" match
"21". Both digits are replaced with a single "1", in effect
deleting this "2". The number n-i becomes n-i-1, that is, n-j.

3 How many iterations?
----------------------
We start with n "2"s. Each iteration removes one "2". So, after
n iterations, we have a string consisting of:
           fib(n-1) "1"s
mixed with fib(n) "0"s
and then   a single "1", no longer prefixed by any "2"s.

After this iteration, the loop condition (end with "1") is still
true. So there is a (n+1)-th iteration, which produces:
           fib(n) "1"s
mixed with fib(n+1) "0"s
and then   a single "0", because of the 1 -> 0 substitution (used 
for a different purpose).

Then, we remove the (fib(n+1)+1) "0"s, with y/02//d, and the last 
string now contains only fib(n) "1"s.

By the way, y/02//d could even be replaced by y/0//d, because 
there are no "2"s anymore.

4 Comments
----------
Where did the formula come from?
I needed a formula producing:
    0  -> 10
    1  ->  0
    21 ->  1
I tried a polynom y = a x**2 + b x + c, and I found
    y = (67 x**2 - 1467 x + 1400)/140
or, with the Horner formula
    y = ((67 x - 1467) x + 1400)/140
The problem is, only the three values give an positive integer 
result, which would be an indication that these three values 
are the important ones, and the other values can be 
discarded. So I introduced the functions "abs" and "int". 
Since I had done that, I could alter a bit the 
polynom, and therefore I changed it to
    y = ((67 x - 1467) x + 1423)/140

Duration of the program.
This program is very inefficient. During the i-th iteration, 
you have:
fib(i-1) substitutions "1 -> 0"
  fib(i) substitutions "0 -> 10" (which extends the string)
   and 1 substitution "21 -> 1".
Therefore, the i-th iteration has fib(i+1)+1 substitutions, that is
0.723 x 1.618 ** i + small quantity.
The total cost is 0.723 x sum(1.618 ** i + small quantities),
that is O(1.618**n). Not very good, but much fun.
[download]