Machine: [EvenOddDetector]
# Detects whether a digit is even or odd. Does not move the head.
State: q0
q0, 0 , 0 , even
q0, 2 , 2 , even
q0, 4 , 4 , even
q0, 6 , 6 , even
q0, 8 , 8 , even
q0, 1 , 1 , odd
q0, 3 , 3 , odd
q0, 5 , 5 , odd
q0, 7 , 7 , odd
q0, 9 , 9 , odd

Notice in this listing, that when the head is not moving, there is no move → or ← instruction.

The unit counter

Here’s a fun and easy challenge. Place the number 9 on the strip and position your head on the 9. The machine must decrement the number, display the result, and start again until the number is 0. At that point, it must erase it and stop. Of course, the program is only useful in step-by-step mode, walking or running. On the strip, you must see successively, in the same box, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, ☐. You can, of course, start from any other number.

No difficulty in implementation; we don’t even move the head. It is a first step towards a more complex machine, which can decrement any natural number. The collection is C={[0-9], ☐ }

Machine: [DecrementUnit]
# Decrements a digit until it disappears.
# Start: on the digit
# End: on the blank that replaces the digit

State: q0
q0, 9, 8, q0
q0, 8, 7, q0
q0, 7, 6, q0
q0, 6, 5, q0
q0, 5, 4, q0
q0, 4, 3, q0
q0, 3, 2, q0
q0, 2, 1, q0
q0, 1, 0 , q0
q0, 0 , ☐ , q0

The irreversible encoding machine

Let the collection C={[AZ], ☐ , . }

Write a sentence on the strip using capital letters. As in a crossword puzzle, ignore accents. Separate the words with spaces. End the sentence with a period.

A sentence is written on the strip using capital letters. As in crossword puzzles, special characterss are ignored. Separate words with blanks. End the sentence with a period.

Example: THE TURING MACHINE IS GREAT.

The head is positioned on the first letter of the sentence. It must stop on the period.

Write a program that transforms each letter and the blank into another letter or a blank. This is the classic transposition system; one letter is exchanged for another. For example, A becomes T, B becomes R, etc. Each character read must have a corresponding character. Each corresponding character must correspond to one, and only one, character. Thus, if I translate A into T, I can no longer translate another letter into T. Don’t forget to translate the blank.

The machine must be irreversibly encoded: if we run it on a text that has already been encoded, the text must be over-encoded, but not returned to its original version. This means that if I code A with a T, the T must not be transformed into A. A few exceptions can be tolerated, but not too many.

Here, the program is tedious because there are 26 letters, but easy to write; it requires only one state. The main interest lies in organizing the work. How are students going to encode without making mistakes? It’s important to set up a procedure for allocating letters, and above all not to throw yourself into programming without preparation.

The decoding machine

This is the corollary of the previous machine! Create a machine that can decode a message written by the previous one.

As the Actilud interface is quite ergonomic, students can reuse the old machine after saving it, and, in the instruction editor, click on the permutation icon for each letter.

After creating the two machines, we can explain how  asymmetric encryption works.  Let’s imagine two people, Alice and Bob, who decide to communicate encrypted using the Turing machine. Alice will create two machines, one for encoding, another for decoding. Bob will do the same. When they meet, Alice gives Bob her encoding machine, and Bob gives his to Alice. Then they go their separate ways. Thus, Alice and Bob can now encrypt their messages with their correspondent’s machine. To decrypt the messages received, they must use their personal decoding machine, which they carefully store in a safe. This means that a total of 4 machines are needed to ensure communication, two machines per correspondent.

Asymmetric encryption is the basis of the TLS protocol used in exchanges between a browser and a website via HTTPS. The browser initiates communication with the website’s server. The latter responds by sending its public key. The browser then sends encryption information, which it encrypts with the received public key. The server receives the information and decodes it with its private key. This allows the two parties to establish a symmetrical exchange system, valid only between the two parties for the duration of the session.

The reversible (symmetrical) coding machine

This time, once the machine has encoded a text, a second pass must bring back the original text. This is the principle of reversible encryption (or symmetric encryption). Here again, everything lies in the organization of the work: how do you proceed to make it work? The design phase is fundamental.

To do this, we need to group the letters into pairs. We have 26 letters and a blank, which makes 13 pairs and a symbol that will not be translated. Here, if I translate the A to a T, the T must be translated to an A in the same state.

An even/odd number detector

Let a natural whole number be written on the strip, one digit per box. The digits follow one another.

We start somewhere inside the number. If the number is even, the machine must stop on the last digit in the “even” state. If the number is odd, the machine must stop on the last digit in the “odd” state.

The collection will be C={[0-9],☐} (the numbers 0 to 9 and whitespace).

To complete this challenge, the machine must first scan the numbers to the right until it reaches the last one. To find it, it must pass the digits until it reaches the first blank. There, it moves back one square to the left. It then reaches the last digit. If this digit is 0, 2, 4, 6, or 8, the machine enters the “even” state; this state will not be defined, and therefore the machine stops. For other digits, the machine enters the “odd” state, which is also undefined and therefore causes a stop.

To complete the challenge, two states must be used.

The solution:

Machine: [EvenOddNumberDetector]
# Detects whether a number is even or odd. Ends on the last digit.
State:path

path, 0 , 0 , → , path

path, 1 , 1 , → , path
path, 2 , 2 , → , path
path, 3 , 3 , → , path
path, 4 , 4 , → , path
path, 5 , 5 , → ,path
path, 6 , 6 , → , path
path, 7 , 7 , → , path
path, 8 , 8 , → , path
path, 9 , 9 , → ,path
path, ☐ , ☐ , ← , detection
State:detection
detection, 0 , 0 , even
detection, 2 , 2 , even
detection, 4 , 4 , even
detection, 6 , 6 , even
detection, 8, 8, even
detection, 1, 1, odd
detection, 3, 3, odd
detection, 5, 5, odd
detection, 7, 7, odd
detection, 9, 9, odd

The caterpillar: a three-state challenge

This challenge is interesting in step-by-step, walking or running mode.

Consider a caterpillar formed by several consecutive letters O. A little further to the right, after a few white squares, there is an appetizing letter X. The caterpillar must move to the letter X and eat it. Of course, the caterpillar crawls: the letters O must not be separated! The idea is to move it by removing the O from the left end to place it at the right end, and to repeat this process until the end. Thus, the caterpillar shortens and stretches to move. Initially, the head is positioned on the leftmost O. We end up on the letter O on the right, which must replace the X. The collection is C={ O, X, ☐ }

This challenge is interesting in step-by-step, walk or run mode.

Let’s say a caterpillar formed by several consecutive letters O. A little further to the right, after a few white boxes, there’s an appetizing letter X. The caterpillar must move to the letter X and eat it. Of course, the caterpillar is crawling: you can’t separate the letters O! The idea is to move the caterpillar by removing the O from the left end and placing it on the right end, and repeating this process until you reach the finish line. In this way, the caterpillar shortens and stretches to move. Initially, the head is positioned on the leftmost O. It ends on the letter O on the right, which must replace the X. The collection is C={ O, X, ☐ }

We start by deleting the leftmost O, then we go through the list of O’s to the right until the end. If there is a blank, we place an O, we go back to the beginning of the caterpillar and start the processing again. If there is an X, we place the O and stop.

So we need: a state to remove the leftmost O; a state to place the O; a state to move back.