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
.
- This state is when the writehead is at the first character of the string. In this state the first letter is changed to
searching_n
- After the
initial_state
, the writehead moves right until it finds the final character of the string which will be next to a0
.
- After the
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 to0
.
- After the writehead finds the final character of the string, it compares the final character of the string to the character from
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.
- 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
is_palindrome
- If all characters have been changed to
0
and all comparisons have been successful, the word is a palindrome.
- If all characters have been changed to
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
State | String |
---|---|
initial_state | a̲a0 |
searching_0 | 0a̲0 |
searching_0 | 0a0̲ |
comparing_0 | 0a̲0 |
success_move | 0̲00 |
initial_state | 00̲0 |
is_palindrome | 000̲ |
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”:
State | String |
---|---|
initial_state | a̲b0 |
searching_0 | 0b̲0 |
searching_0 | 0b0̲ |
comparing_0 | 0b̲0 |
not_palindrome | 0̲b0 |
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.
Instructions
In the terminal, we can use a turing machine to check if any word is a palindrome by using the following command:
python3 turing.py word
Replace word
with any word you would like to test out. We recommend:
- racecar
- test
- deified
- divided
Mix up the length of the words you try. Notice how many steps longer words take.