McCulloch's second machine

McCulloch's second machine is a partial function on digit strings defined in Raymond Smullyan's book The Lady or the Tiger? and Other Logical Puzzles (1982).

Definition

The machine implements a partial function m whose domain and range is the set of non-empty strings of digits 1 to 9. (The digit 0 or empty strings are specifically forbidden.) The function is defined by four rules. Here, ++ means concatenation and reverse means reversing the order of digits in a string.

Rule 1

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

Rule 2

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

Rule 3

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

Rule 4

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

A digit string is called mortal iff iterating the machine on it eventually leads to a string that is not in the domain of the machine. It is otherwise called immortal.

Discussion

The machine is defined for exactly the digit strings matching the following regular expression: /^[345]*2[1-9]+$/

Some strings are fixed points: m(323) = 323; m(5252) = 5252.

Some strings lead to a 2-cycle when iterated on the machine:

3243 -> 43243 -> 34234 -> 43243

Some strings are immortal because they lead to an ever growing sequence of strings. Some grow very quickly, eg.

3235 -> 35235 -> 353523535 -> 353535352353535353535353523535353523535353523535353535353535235353535 -> [a 15445 digit long string]

and some grow slowly, eg.

5232 -> 3232 -> 32232 -> 2322232 -> 322232 -> 223222232 -> 23222232 -> 3222232 -> 22232222232 -> 2232222232 -> 232222232 -> 32222232 -> 2222322222232 -> 222322222232 -> 22322222232 -> 2322222232 -> 322222232 -> 222223222222232 -> 22223222222232 -> 2223222222232 -> 223222222232 -> 23222222232 -> 3222222232 -> 22222232222222232 -> 2222232222222232 -> 222232222222232 -> 22232222222232 -> 2232222222232 -> 232222222232 -> 32222222232 -> 2222222322222222232 -> 222222322222222232 -> 22222322222222232 -> 2222322222222232 -> 222322222222232 -> 22322222222232 -> 2322222222232 -> 322222222232 -> 222222223222222222232 -> 22222223222222222232

All strings that contain any digit other than 2, 3, 4, 5 are mortal. User:b_jonas would like to see a proof on whether it's algorithmically decidable whether a string is mortal.

Implementation

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

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

History

McCulloch's first machine, defined in the same book, is a restriction of this function where only the first two of the rules is given. McCulloch's third machine is a related function. The sultan's daughter is a related function defined in the later book The Riddle of Scheherazade.