Does the moveRight() method perform its duties correctly?

Introduction

This blog implements a Turing machine tape using a doubly-linked list, and an object of type Cell can represent each cell in the tape. Besides, there is a pointer to the current cell in this tape, and one can move this pointer by calling the moveRight() or moveLeft() method. In this blog, I’ll discuss the circumstances under which a given moveRight() method can correctly perform its duties and the cases under which it cannot.

1. Questions

Does the following moveRight() method perform its duties correctly？Specifically, there are two code snippets (UoPeople, n.d.):

/**
 * Represents one cell on a Turing Machine tape.
 */
public class Cell {
    public char content;  // The character in this cell.
    public Cell next;     // Pointer to the cell to the right of this one.
    public Cell prev;     // Pointer to the cell to the left of this one.
}

/**
 * Moves the current cell one position to the right along the tape.
 * Note that if the current cell is the rightmost cell that exists,
 * then a new cell must be created and added to the tape at the right of the current cell,
 * and then the current cell pointer can be moved to point to the new cell.
 * The content of the new cell should be a blank space.
 */
public void moveRight () {
    if (currentCell.next == null) { // if the current cell is the rightmost cell that exists
        Cell newCell = new Cell(); // create a new cell
        newCell.content = ' '; // The content of the new cell should be a blank space
        newCell.next = null;
        newCell.prev = currentCell; // add the new cell to the tape at the right of the current cell
        currentCell.next = newCell;
        currentCell = currentCell.next; // Moves the current cell one position to the right along the tape
    }
}

Suppose we have a ten cells tape with the contents “HelloWorld”. If the current cell points to the head of the tape, can the moveRight() method above perform its duties correctly? In other words, after executing the moveRight() method, will the current cell point to “e” instead of “H”? The images below show what we expect from the moveRight() method:

Before executing the moveRight() :

After executing the moveRight():

2. Answers

The moveRight() method can not perform its duties correctly. The reasons are at follows: The current cell is at the head of the list, and the list has ten cells, so currentCell.next is not null. As a result, the statement currentCell = currentCell.next; in the if-clause will not be executed, the current cell will not move to the next cell.

To further confirm the above explanation, I tested this moveRight() method, and the results show that it did not move the current cell to the right. The detailed test procedure and outputs are shown below.

3. Proving process

3.1. Codes and Outputs

Codes:
Tape.java

package turing;


/**
 * A class named Tape to represent Turing machine tapes.
 * A Turing machine tape can be represented by a doubly-linked list
 * where each cell has a pointer to the previous cell (to its left) and to the next cell (to its right).
 * The pointers will allow the machine to advance from one cell to
 * the next cell on the left or to the next cell on the right.
 */
public class Tape {
    //  an instance variable of type Cell that points to the current cell
    private Cell currentCell;

    /**
     * a constructor that creates a tape that initially consists of a single cell
     */
    public Tape() {
        // create a new cell that contain a blank space
        Cell newCell = new Cell();
        newCell.content = ' ';
        newCell.next = null;
        newCell.prev = null;

        // let the current cell pointer point to the newCell
        this.currentCell = newCell;
    }

    /**
     * returns the pointer that points to the current cell
     *
     * @return
     */
    public Cell getCurrentCell() {
        return currentCell;
    }

    /**
     * returns the char from the current cell
     */
    public char getContent() {
        return currentCell.content;
    }

    /**
     * changes the char in the current cell to the specified value
     *
     * @param ch
     */
    public void setContent(char ch) {
        currentCell.content = ch;
    }

    /**
     * Moves the current cell one position to the left along the tape.
     * If the current cell is the leftmost cell that exists,
     * then a new cell must be created and added to the tape at the left of the current cell,
     * and then the current cell pointer can be moved to point to the new cell.
     * The content of the new cell should be a blank space
     */
    public void moveLeft() {
        if (currentCell.prev == null) { // if the current cell is the leftmost cell that exists
            Cell newCell = new Cell(); // create a new cell
            newCell.content = ' '; // The content of the new cell should be a blank space
            newCell.prev = null;
            newCell.next = currentCell; // add the new cell to the tape at the left of the current cell
            currentCell.prev = newCell;
        }
        currentCell = currentCell.prev; // Moves the current cell one position to the left along the tape
    }

    /**
     * Moves the current cell one position to the right along the tape.
     * Note that if the current cell is the rightmost cell that exists,
     * then a new cell must be created and added to the tape at the right of the current cell,
     * and then the current cell pointer can be moved to point to the new cell.
     * The content of the new cell should be a blank space.
     */
    public void moveRight() {
        if (currentCell.next == null) { // if the current cell is the rightmost cell that exists
            Cell newCell = new Cell(); // create a new cell
            newCell.content = ' '; // The content of the new cell should be a blank space
            newCell.next = null;
            newCell.prev = currentCell; // add the new cell to the tape at the right of the current cell
            currentCell.next = newCell;
//            currentCell = currentCell.next; // Moves the current cell one position to the right along the tape
        }
        currentCell = currentCell.next; // Moves the current cell one position to the right along the tape
    }

    /**
     * Moves the current cell one position to the right along the tape.
     * Note that if the current cell is the rightmost cell that exists,
     * then a new cell must be created and added to the tape at the right of the current cell,
     * and then the current cell pointer can be moved to point to the new cell.
     * The content of the new cell should be a blank space.
     */
    public void moveRightInQuiz() {
        if (currentCell.next == null) { // if the current cell is the rightmost cell that exists
            Cell newCell = new Cell(); // create a new cell
            newCell.content = ' '; // The content of the new cell should be a blank space
            newCell.next = null;
            newCell.prev = currentCell; // add the new cell to the tape at the right of the current cell
            currentCell.next = newCell;
            currentCell = currentCell.next; // Moves the current cell one position to the right along the tape
        }
    }

    /**
     * returns a String consisting of the chars from all the cells on the tape,
     * read from left to right, except that leading or trailing blank characters should be discarded.
     * The current cell pointer should not be moved by this method; it should point to the
     * same cell after the method is called as it did before.
     * You can create a different pointer to move along the tape and get the full contents.
     *
     * @return a String consisting of the chars from all the cells on the tape
     */
    public String getTapeContents() {
        // return "" if there are no cells
        if ((currentCell.next == null) && (currentCell.prev == null)) return "";

        // Concatenate chars on the tape and convert them into strings for output
        StringBuilder stringBuilder = new StringBuilder();

        // Concatenate the currentCell's content
        stringBuilder.append(currentCell.content);

        // Concatenate the contents of all preceding cells
        Cell cell = currentCell.prev;
        while (cell != null) {
            stringBuilder.insert(0, cell.content);
            cell = cell.prev;
        }

        // Concatenate the contents of all following cells
        cell = currentCell.next;
        while (cell != null) {
            stringBuilder.append(cell.content);
            cell = cell.next;
        }
        return stringBuilder.toString().trim();
    }
}

Tape.java (UoPeople, n.d.)

Cell.java

package turing;

/**
 * Represents one cell on a Turing Machine tape.
 */
public class Cell {
    public char content;  // The character in this cell.
    public Cell next;     // Pointer to the cell to the right of this one.
    public Cell prev;     // Pointer to the cell to the left of this one.
}

Cell.java (UoPeople, n.d.)

TestTape.java

package turing;

/**
 * Create a list that has ten cells - "HelloWorld".
 * Let the current cell pointer point to the head - "H".
 * Call the moveRight() method in the quiz, and then the current cell should pointer point to the "e".
 * However, the results show that the current cell still pointer points to the "H",
 * which means that the moveRight() method does not perform its duties correctly.
 */
public class TestTape {
    public static void main(String[] args) {
        Tape tape = new Tape();

        // Create a list that has ten cells - "HelloWorld"
        System.out.println("Create a list that has ten cells - \"HelloWorld\"");
        for (int i = 0; i < "HelloWorld".length(); i++) {
            tape.setContent("HelloWorld".charAt(i));
            System.out.println("The position at the " + tape.getContent());
            tape.moveRight();
            System.out.println("The position at the " + tape.getContent());
        }

        System.out.println();

        //Let the current cell pointer point to the head - "H"
        System.out.println("Let the current cell pointer point to the head - \"H\"");
        for (int i = 0; i < "HelloWorld".length(); i++) {
            tape.moveLeft();
            System.out.println("The position at the " + tape.getContent()); // "H"
        }

        System.out.println();

        // Call the moveRight() method in the quiz,
        // and the current cell should pointer point to the "e".
        // However, the results show that the current cell pointer still points to the "H"
        // which means that the moveRight() method does not perform its duties correctly.
        System.out.println("Call the moveRight() method in the quiz to test whether it performs its duties correctly:");
        tape.moveRightInQuiz();
        System.out.println("The position at the " + tape.getContent()); // "H"
    }
}

TestTape.java (UoPeople, n.d.)

Outputs:

Create a list that has ten cells - "HelloWorld"
The position at the H
The position at the  
The position at the e
The position at the  
The position at the l
The position at the  
The position at the l
The position at the  
The position at the o
The position at the  
The position at the W
The position at the  
The position at the o
The position at the  
The position at the r
The position at the  
The position at the l
The position at the  
The position at the d
The position at the  

Let the current cell pointer point to the head - "H"
The position at the d
The position at the l
The position at the r
The position at the o
The position at the W
The position at the o
The position at the l
The position at the l
The position at the e
The position at the H

Call the moveRight() method in the quiz to test whether it performs its duties correctly:
The position at the H

Process finished with exit code 0

3.2. Explanation

In Tape.java, I created a list with ten cells - “HelloWorld”. Then, I let the current cell pointer point to the head - “H”. Next, in TestTape.java, I called the moveRightInQuiz() method in the quiz, and the current cell pointer should point to the “e”. However, the results show that the current cell pointer still points to the “H”, which means the moveRightInQuiz() method does not perform its duties correctly.

Why doesn’t this moveRightInQuiz()perform its duties correctly? The reasons are at follows: The current cell is at the head of the list, and the list has ten cells, so currentCell.next is not null. As a result, the statement currentCell = currentCell.next; in the if-clause will not be executed, the current cell will not move to the next cell.

If we want the moveRight() method to perform its duties correctly, we can move the statement currentCell = currentCell.next; outside the if statement. In this case, the statement currentCell = currentCell.next; will always be executed regardless of whether the currentCell.next is null or not. As a result, the moveRight() method will let the currentCell’s pointer point to its next cell, thus performing its duties correctly. The correct moveRight() method is as follows:

/**
 * Moves the current cell one position to the right along the tape.
 * Note that if the current cell is the rightmost cell that exists,
 * then a new cell must be created and added to the tape at the right of the current cell,
 * and then the current cell pointer can be moved to point to the new cell.
 * The content of the new cell should be a blank space.
 */
public void moveRight() {
    if (currentCell.next == null) { // if the current cell is the rightmost cell that exists
        Cell newCell = new Cell(); // create a new cell
        newCell.content = ' '; // The content of the new cell should be a blank space
        newCell.next = null;
        newCell.prev = currentCell; // add the new cell to the tape at the right of the current cell
        currentCell.next = newCell;
    }
        currentCell = currentCell.next; // Moves the current cell one position to the right along the tape
}

The correct moveRight() method (UoPeople, n.d.)

4. In Conclusion

1.If the tape has only one head cell, and the current cell points to it, then the moveRight() method in the quiz can perform its duties correctly.

2.However, if the tape has more than one cell, and the current cell points to this head cell, then the moveRight() method in the quiz cannot perform its duties because, in this case, the statement currentCell = currentCell.next; will not be executed.

3.If one wants the moveRight() method to perform its duties correctly in any case, he/she needs to move the statement currentCell = currentCell.next; outside the if statement.

Word count: 2342

References

UoPeople. (2020). Lab 5: Tape for a Turing Machine (Doubly-linked List).
https://my.uopeople.edu/mod/page/view.php?id=279538

UoPeople. (2022). Code Unit 3.
https://my.uopeople.edu/mod/folder/view.php?id=279540

​

---

This is the ending, thanks for reading.

---