Front page | perl.fwp |
Postings from March 2005
We have all had fun with perl writing quines or self-reproducing
programs. Quines, when run, print out a copy of themselves to stdout.
One of the many reasons quines are fun is self-reproduction is one
aspect of a very primitive form of artificial life. A different aspect
of artificial life might be self-recognition - the ability to tell if I
am different (not equal) to you or "I neq U". I define an Inequ to be a
program which reads from stdin. If it recognises the program there to
be the same as itself it quits with an status (or error-level) of 0
otherwise it quits with a non-zero status.
I tried writing an inequ in perl and it is quite easy especially if you
start with a quine. For example:
bash$ PS1='$?> '
0> cat recog.pl
$_=q{$_=q{X};s/X/$_/;$/=undef;die if <> ne $_
};s/X/$_/;$/=undef;die if <> ne $_
0> cat recog.pl | perl recog.pl
0> cat random.pl | perl recog.pl
Died at recog.pl line 2, <> chunk 1.
255>
Note that the status of the last execution was 255 ie. non-zero.
Its not surprising that with a Turing complete language like perl this
is possible. A more challenging exercise is to write a self-recognising
regular expression. A regular expression inequ in perl is a string $x
where $y =~ /$x/ implies $y eq $x.
An example of an attempt at an inequ regular expression is /a/.
However, although "a" =~ /a/ there are infinitely many other strings
which are also accepted by /a/ (for example "apple" =~ /a/).
Similarly, /^a$/ accepts only the string "a" but since it does not
accept "^a$", it is not an inequ.
The challenge then is to find a regular expression inequ or failing
that, the regular expression that accepts the smallest set of strings
including itself. The score of an entry is the size of the set of
strings it accepts. If two regular expressions find the same size set
of strings, the shorter regular expression wins.
I will summarise entries at
http://www.cs.auckland.ac.nz/~jas/toys/inequ.html#score
The par entry is:
Entry Score
^.{6}$ 255^6
--
Jasvir Nagra
http://www.cs.auckland.ac.nz/~jas
Thread Next