Learn

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

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_stateis_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.

Take this course for free

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.
Already have an account?