develooper Front page | perl.fwp | Postings from March 2005

Self-recognizing programs and regular expressions

Thread Next
Jasvir Nagra
March 7, 2005 14:00
Self-recognizing programs and regular expressions
Message ID:
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 
$_=q{$_=q{X};s/X/$_/;$/=undef;die if <> ne $_
};s/X/$_/;$/=undef;die if <> ne $_
0> cat | perl
0> cat | perl
Died at line 2, <> chunk 1.

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

The par entry is:

Entry 		Score
^.{6}$ 		255^6

Jasvir Nagra

Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About