Move the apples!

Yes, our machine can also transport fruit!

Let C={apple, pear, grape, =, blank, X} be a collection.

Place several apples, pears, and grapes in a row in the boxes, making sure to mix them together. There should be no white space between the fruits. End the row with the = sign. The head should start on the equal sign.

Objective: Move all apples after the = sign.

At the end, the head should stop on the equal sign.

If you look at the collection, you’ll see the X sign in addition to the others. What could it be used for? It’s up to you to find out…

Description of how it works (click to see, if you really can’t do it…)

The head starts by moving to the left. If it finds an apple, it replaces it with an X, then moves right to the first empty box. There, it writes an apple, then goes to the = sign, where it starts the process again. If it finds a pear, a grape or an X, it continues to the left. If it ends up on an empty square, it moves to the right, deleting all Xs as it goes; it stops at the = sign.

Count a small number of apples!

Let C={apple, =, ☐, X, [1-9]} be a collection.

Place between 1 and 9 apples consecutively on the strip, followed by the “=” sign. At the beginning and end of the treatment, the head should be on the = sign. At the end of the treatment, the number of apples should appear in the box following the = sign. The idea is to temporarily replace the apples with an X sign.

Description of operation

The head goes first to the left. If it finds an apple, it replaces it with an X, goes to the right of the = sign and there writes a 1 if the square is empty, or, if the square already contains a number between 1 and 8, increments it. It then repeats the process. If, as it moves to the left, the head encounters an X, it continues to the left. If it encounters a blank, it returns to the = sign, turning all Xs into apples in the process. It stops there. To increment, simply replace the digit read by the next higher digit: if there’s a 1, put a 2, if there’s a 2, put a 3, etc.

Increment a single number on the tape

We’ll often need to create counters. This challenge is important because it’s the starting point for more complex problems. Consider a natural number N placed on the tape, one digit per box. The head is positioned on the units digit, so the last one on the right. At the end of the processing, the number must have the value N+1. The collection is C={[0-9],☐}. The stop location doesn’t matter.

As you can see, the difficulty lies in the passage of tens! So, test numbers like 9, 99, 999! It’s not very complicated because it can be done in a single state!

Description of operation

If the head encounters a number from 0 to 8, it replaces it with the next higher number, and we stop. If it reads a 9, it replaces it with a 0, goes to the left and the process starts again. If it reads a blank, it places a 1 and it stops. That’s all…

Increment a number immediately to the right of the = sign

TThis time the task is a little more complex. Often, our counters end up just to the right of the “=” sign, as in the “apple counter” problem above. Our counter must be able to increment behind the = sign, whatever the number of apples. But when it goes from 9 to 10, from 99 to 100, from 999 to 1000, etc., the number can’t extend to the left, because of the “=” sign and the apples in the way.

Your task is to create a universal number incrementing program that extends to the right. Starting point: on the last digit of the number. The stop location is irrelevant. The collection is C={[0-9],☐}. This program has to deal with the special case of shifting to the right as the number grows by one digit. Our “universal incrementer” requires only 3 states, so it’s not very complex.

Examples: =9 becomes =10, =99 becomes =100, =9999 becomes =10000 etc, but =7 becomes =8, =299 becomes =300…

Note: If you want to reuse the machine in another program, it is best to always keep the final head position the same. I suggest always stopping on the = sign.

Good luck.

If you can’t find it, here is the listing – if this program the head stops inside the number (spoiler!)

Machine: [UniversalIncrementer]
# Increments a natural number directly behind the “=” sign.
# Start: on the rightmost data item
# End: on one of the data items

State: q0
q0, 0, 1, stop
q0, 1, 2, stop
q0, 2, 3, stop
q0, 3, 4, stop
q0, 4, 5, stop
q0, 5, 6, stop
q0, 6, 7, stop
q0, 7, 8, stop
q0, 8, 9, stop
q0, ☐, 1, stop
q0, 9, 0, ←, q0
q0, ‘=’, ‘=’, →, q1

State: q1
q1, 0 , 1 , → , q2

State: q2
q2, 0 , 0 , → , q2
q2, ☐ , 0 , stop