Math Detours · Grade 10 · Around the corner · 36

A machine you can undo only one way

Push every item in an endless list one place along and put 0 at the front. Nothing is lost, and a second machine undoes it. Run the two in the other order and something is lost for good. This is Hilbert's hotel as a machine.

Name ____________________Date ____________

Tonight's idea

Hilbert's hotel is a thought experiment: endless rooms numbered 1, 2, 3, and so on, all full. A new guest arrives. Everyone moves one room along, and room 1 is free. Nobody is thrown out.

Tonight's lists are endless lists of numbers, such as \((5, 2, 7, 1, \ldots)\). Two machines act on them. The right shift \(R\) pushes every item one place along and puts 0 at the front. The left shift \(L\) deletes the first item and pulls the rest forward.

\[R(a, b, c, \ldots) = (0, a, b, c, \ldots) \qquad L(a, b, c, \ldots) = (b, c, d, \ldots)\]

\(L\) after \(R\) gives every list back: \(L(R(x)) = x\). \(R\) after \(L\) does not: \(R(L(x))\) has 0 where the first item of \(x\) was.

"\(L\) after \(R\)" means run \(R\) first, then \(L\). A machine is one-to-one if different inputs always give different outputs. It is onto if every list comes out for some input.

Watch one: both orders on \((5, 2, 7, 1, \ldots)\)

Let \(x = (5, 2, 7, 1, \ldots)\). The dots stand for the rest of the list, whatever it is.

\(L\) after \(R\). First \(R(x) = (0, 5, 2, 7, 1, \ldots)\). Then \(L\) deletes the 0 that \(R\) just put there: \(L(R(x)) = (5, 2, 7, 1, \ldots) = x\). The list is back, and this works for every list.

\(R\) after \(L\). First \(L(x) = (2, 7, 1, \ldots)\). The 5 is gone. Then \(R\) makes room at the front, but it can only put 0 there: \(R(L(x)) = (0, 2, 7, 1, \ldots)\). That is not \(x\).

What happened. \(R\) loses nothing, so it can be undone afterwards. \(L\) throws the first item away, and no machine that runs afterwards can know it was a 5.

Your turn

  1. Let \(x = (1, 2, 3, 4, 5, \ldots)\), the counting numbers. Write the first five items of \(R(R(x))\), of \(L(L(x))\), of \(L(L(R(R(x))))\) and of \(R(R(L(L(x))))\). Then say exactly which lists \(x\) have \(R(L(x)) = x\).
  2. (a) Explain why \(R\) is one-to-one, and name a list that \(R\) never outputs. (b) Explain why \(L\) is onto, and name two different lists that \(L\) sends to the same list. (c) Could any machine \(M\), however clever, have \(R(M(x)) = x\) for every list \(x\)? Could any have \(M(L(x)) = x\) for every \(x\)?
  3. Now use short lists: three items, each 0 or 1, such as \((1, 0, 1)\). (a) How many such lists are there? (b) A machine turns each of these lists into one of these lists. Explain why, if it is one-to-one, it must also be onto. (c) The chopped shift \(S(a, b, c) = (0, a, b)\) pushes along and drops the last item. How many different lists does it output? Is it one-to-one?
  4. Write \(2x\) for the list \(x\) with every item doubled. (a) Find every endless list with \(L(x) = 2x\). (b) Find every endless list with \(R(x) = 2x\).

Stretch: chains of machines

(a) On lists of four numbers, the chopped shift is \(S(a, b, c, d) = (0, a, b, c)\). Run \(S\) four times on \((1, 2, 3, 4)\). What does four runs of \(S\) do to any list of four numbers? Can any number of runs of \(R\) do that to an endless list? (b) Run this chain on an endless list, in this order: \(R, R, L, L, L, R\). Whenever an \(L\) comes straight after an \(R\), the pair does nothing and can be crossed out. Cross out until you are stuck. What single short chain is left? (c) Why does every chain of \(R\)s and \(L\)s boil down to some \(L\)s followed by some \(R\)s?

Answers

  1. \(R(R(x)) = (0, 0, 1, 2, 3, \ldots)\) and \(L(L(x)) = (3, 4, 5, 6, 7, \ldots)\). Then \(L(L(R(R(x)))) = (1, 2, 3, 4, 5, \ldots) = x\), but \(R(R(L(L(x)))) = (0, 0, 3, 4, 5, \ldots)\): the 1 and the 2 are lost. Since \(R(L(x))\) is \(x\) with its first item replaced by 0, it equals \(x\) exactly when the first item of \(x\) is already 0.
  2. (a) If \(R(x) = R(y)\), run \(L\) on both sides: \(x = y\). So different inputs give different outputs. Every output of \(R\) starts with 0, so \((1, 0, 0, 0, \ldots)\) never comes out: \(R\) is not onto. (b) Any list \(y\) comes out of \(L\), because \(L(R(y)) = y\). But \((5, 2, 7, 1, \ldots)\) and \((9, 2, 7, 1, \ldots)\) both go to \((2, 7, 1, \ldots)\), so \(L\) is not one-to-one. (c) No to both. \(R(M(x))\) always starts with 0, so it cannot equal a list that starts with 1. And \(M\) receives the same list \((2, 7, 1, \ldots)\) from both lists in (b), so it gives one answer and is wrong for at least one of them. \(L\) undoes \(R\) from one side only, and nothing does it from the other.
  3. (a) \(2 \times 2 \times 2 = 8\). (b) A one-to-one machine gives 8 different outputs for the 8 inputs. There are only 8 lists, so every list comes out. On a finite set you cannot be one-to-one without being onto, so nothing there behaves like \(R\). (c) The outputs are \((0, 0, 0)\), \((0, 0, 1)\), \((0, 1, 0)\) and \((0, 1, 1)\): 4 lists. It is not one-to-one: \((1, 0, 0)\) and \((1, 0, 1)\) both give \((0, 1, 0)\). (This counting needs a finite set. With any numbers allowed there are endlessly many lists of three, and the same conclusion holds only for machines that respect adding and scaling, called linear, by a harder argument.)
  4. Write \(x = (a_1, a_2, a_3, \ldots)\). (a) \(L(x) = (a_2, a_3, \ldots)\) and \(2x = (2a_1, 2a_2, \ldots)\), so each item is double the one before: \(x = (a, 2a, 4a, 8a, \ldots)\) for any number \(a\). Check: deleting \(a\) leaves \((2a, 4a, 8a, \ldots)\), which is \(2x\). Unless \(a = 0\), the items grow in size without limit. (b) \(R(x) = (0, a_1, a_2, \ldots)\) must equal \((2a_1, 2a_2, 2a_3, \ldots)\). So \(2a_1 = 0\), then \(2a_2 = a_1 = 0\), then \(2a_3 = a_2 = 0\), and so on. Only the all-zero list works. \(L\) doubles a whole family of lists. \(R\) doubles nothing but zeros.

Stretch. (a) \((0, 1, 2, 3)\), then \((0, 0, 1, 2)\), then \((0, 0, 0, 1)\), then \((0, 0, 0, 0)\). Each run drops one more of the original items, so four runs turn every list of four into all zeros. No number of runs of \(R\) does that: after \(n\) runs of \(R\), \(n\) runs of \(L\) bring the list back. (b) Crossing out the second \(R\) and the first \(L\) leaves \(R, L, L, R\). Crossing out the \(R, L\) at the front leaves \(L, R\): the whole chain just replaces the first item with 0. (c) Keep crossing out until no \(L\) comes straight after an \(R\). Then everything that runs after the first \(R\) is another \(R\), so all the \(L\)s come first and all the \(R\)s after. Chains like these can always be combined but not always undone. Mathematicians call such a collection a semigroup.

← PreviousNext: How many shuffles mix a deck? →