# McCulloch's third machine

McCulloch's third 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 M-I
If x is a nonempty digit string, then m(2 ++ x ++ 2) = x.
Rule M-II
If x is a nonempty digit string and m(x) is defined, then m(6 ++ x) = 2 ++ m(x).
Rule M-III
If x is a nonempty digit string and m(x) is defined, then m(4 ++ x) = reverse(m(x)).
Rule M-IV
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: /^[456]*2[1-9][1-9]*2\$/

The string 5464254642 is a fixed point, because m(5464254642) = 5464254642. The string 52546422 bootstraps this string in one step. The strings 4564245642, 46452464522 are other fixed points.

## Implementation

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

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

## History

The book defines an equivalent variant that operates on strings of letters instead of digits. In this, the letters Q, V, R, L take place of the digits 2, 4, 5, 6.

McCulloch's second machine is a related function. The sultan's daughter is a related function defined in the later book The Riddle of Scheherazade.