Turing machine contest: the 14-year-old winner | Tangente

The winner: a 14-year-old reader ---------------------------------------

Several dozen participants answered the question correctly. Adrien Diouris, from Lorient in Morbihan, was chosen at random. This 14-year-old reader of Tangente won the contest!

*"At first, once morning recess was over, mathematics was simply one subject among others. But when I started 6^th grade, I began to appreciate mathematics for what it really is. I enjoyed turning a complicated situation or expression into something easier to understand and, above all, contemplating the endless possibilities that mathematics offers," Adrien writes. He also tells us: "I fence, and for the past seven years I have belonged to the Éclaireuses et Éclaireurs de France, a secular scouting movement, in short."*

Finally, Adrien sends "a big thank-you to Tangente*, thaM thaM, and [his] mathematics teacher in 6^th grade"*.

A contest and a mathematics question ------------------------------------

The thaM thaM company distributes the thaMographe, a "four-in-one" geometry tool combining a ruler, compass, set square and protractor for measuring and drawing without a sharp point (see les Angles, Bibliothèque Tangente 53, 2015). The small company recently built and marketed an authentic Turing machine\*, offering one as a prize in a contest for our readers (see Tangente 200). Here is the question readers had to answer.

Consider a Turing tape whose cells all contain the symbol 0 before the three-state busy beaver algorithm, with states E1, E2 and E3, is run. Begin at a cell with the machine in its initial state, E1. The 0 becomes 1. The arrow shows that the machine, now in state E2, moves to the cell immediately to the right. Since this cell contains a 0, it remains 0; the machine then enters state E3 and moves to the next cell on the right (the arrow again points right). Repeat as many times as necessary until the machine reaches Stop. How many "1s" does this algorithm create before stopping?

The answer to the puzzle ----------------------

Let's follow the busy beaver algorithm from step 0 to the halting state (STOP). The number of steps completed is shown on the far left and, next to it, the configuration that results from executing the instruction in the row immediately above. For example, after completing three steps of the program, the machine is in state E3. It reads a cell containing the symbol 0. It then performs the following actions: write 1 in this cell; move to the cell on the left; remain in state E3. It has then completed four steps of the program and is in the configuration labelled 4. The halting state is reached after fourteen steps of the program. The tape then contains six cells containing the symbol 1.

\* For further information: 06 01 74 52 71 or [email protected]