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.