# 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: /^*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 (\$_=~/\A(*)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.