As a bonus exercise, let’s look at a simple Turing Machine implementation using the bash terminal. Before we jump into it, let’s go over how this machine operates.

This Turing Machine follows a set of instructions to determine if a given word is a palindrome or not a palindrome. The rules are outlined in the following table:

The states of this turning machine are defined as the following:

• initial_state
  • This state is when the writehead is at the first character of the string. In this state the first letter is changed to 0.
• searching_n
  • After the initial_state, the writehead moves right until it finds the final character of the string which will be next to a 0.
• comparning_n
  • After the writehead finds the final character of the string, it compares the final character of the string to the character from initial_state. During this state, the final character is changed to 0.
• success_move
  • If the comparison is “successful” (the characters are the same), the writehead will start moving left until it finds the new first character of the string. This new first character will be next to the 0 that was the old first character.
• is_palindrome
  • If all characters have been changed to 0 and all comparisons have been successful, the word is a palindrome.
• not_palindrome
  • If there are any failed comparisons, the word is not a palindrome and the program ends.

Let’s go through two examples.

First, let’s look at “aa”:

The table below shows the state, the string, and the underline signifies where the writehead is currently at each step. The initial string is “aa” with “0” appended so the writehead can find the final character

The writehead starts off at the initial state. Then, it searches for the final character. When it hits, the 0 at the end of the string, it moves left and goes into comparing_0 state. It then looks for the next character in the string. Since the characters are all zeros it moves from initial_state → is_palindrome.

Next, let’s look at “ab”:

This example follows the same procedure as before. However, after comparing_0, it moves into not_palindrome state since “a” and “b” are not the same character.