Inequ: Self-recognizing programs
and regular expressions

It is not difficult to write inequ's in perl 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 not_recog.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 = $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 which 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.

Scores