# 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*.