Sultan's daughter

The sultan's daughter is a partial function on digit strings defined in Raymond Smullyan's book The Riddle of Scheherazade (1997).

Definition

The machine implements a partial function p whose domain and range is the set of non-empty strings of digits 0 to 9 (strings starting with digit 0 are probably forbidden). The function is defined by five rules. Here, ++ means concatenation, reverse means reversing the order of digits in a string, & tail means dropping the first digit of a string.

Rule 1

If x is a nonempty digit string, then p(1 ++ x ++ 2) = x.

Rule 2

If x is a nonempty digit string and p(x) is defined, then p(3 ++ x) = p(x) ++ p(x).

Rule 3

If x is a nonempty digit string and p(x) is defined, then p(4 ++ x) = reverse(p(x)).

Rule 4

If x is a nonempty digit string and p(x) is defined and has at least two digits, then p(5 ++ x) = tail(p(x)).

Rule 5

If x is a nonempty digit string and p(x) is defined, then p(6 ++ x) = 1 ++ p(x), and p(7 ++ x) = 2 ++ p(x).

Discussion

The string 47536414753642 is a fixed point given in the book. A shorter fixed point is 47431474312.

Implementation

The following perl code defines the function sd which computes p, or returns undef if p is not defined.

sub sd {
    if ($_[0]=~/\A([3-7]*)1([0-9]+)2\z/) {
        my$t=$2;
        for my$p(reverse split//,$1) {
            $t = 3 eq$p ? $t x2 : 4 eq$p ? reverse$t :
                5 eq$p ? (1<length$t?substr($t,1):return undef) :
                6 eq$p ? 1 .$t : 7 eq$p ? 2 .$t : die;
            }
        return $t;
    } else {
        return undef;
    }
} 

History

According to the story in the book, the sultan's daughter (princess) implements this function. The sultan made prince Al-Khizr find a fixed point and some other strings with interesting properties to test his worthiness to marry the princess.

McCulloch's second machine and McCulloch's third machine are related functions defined in an earlier book.