How to build a Turing Machine Using Pixi.js
Published: 2022-11-27 18:56:11


![Figure 1: Winter Scenery](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1gt4ph3i6jkiuz1ieext.jpg)

Ever wondered how to create a Turing machine using a JavaScript game library? If so, keep reading to learn how to build a Turing machine using the popular JavaScript/HTML rendering library: PixiJS!

## What is a Turing Machine?

First of all, let's briefly go over what a Turing Machine is: A Turing machine is a theoretical machine originally conceived by the mathematician Alan Turing. The Turing machine can supposedly simulate any computer algorithm regardless of the level of complexity.

Although the original idea for the machine was purely abstract and hypothetical here is an image of a physical representation of this machine:


![Figure 2: A physical representation of a Turing machine](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5b89x7vj3mia71dx7h47.png)

_Figure 2: A physical representation of a Turing machine_

Keep in mind that it is not exactly in accordance with the theoretical concept as it is not possible to have a tape of infinite length.

On a more practical level, a Turing machine can read from and write to an infinite tape(although no infinite tapes exist in real life). It manipulates symbols on this theoretically infinite tape based on a predefined set of rules also known as instructions.

The machine has a head which is positioned over a single square on the aforementioned infinite tape and performs one of the following three instructions:

1. Read the value of the square that the head is currently pointing towards
2. Write a value based on the predefined instruction set to the square that the head is currently pointing towards
3. Move the tape either to the left or right by one square in order to do one of this three actions on a neighboring square

## Development:

In this tutorial we will be building a Turing Machine application that replicates a palindrome program.

{/* <Explain basic idea of a palindrome program and how this Turing Machine app recreates the palindrome program> */}

For this tutorial it would be easy if you could follow along with the sample application in this GitHub link: [Palindrome Turing Machine Starter Code](https://github.com/ShehanAT/PalindromeTuringMachine)

First visit this GitHub link and clone the repo. Then open the folder in a coding editor(I'll be using VSCode for this tutorial):


![Figure 3: Image of cloned repo in VSCode](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/veextpzevfor89p3mam1.png)

_Figure 3: Image of the cloned repo in VSCode_

For the sake of brevity we'll only cover the most important functions in the `main.js` file of this program.

#### Developing the GUI:

So let's start out by covering some rendering functions:

```
function RenderTapePointer() {
    // center the sprite's anchor point
    tape_pointer.anchor.set(0.5);
    // move the sprite to the center of the screen
    tape_pointer.x = app.screen.width / 2 - 45;
    tape_pointer.y = (app.screen.height / 2) + 150;
    tape_pointer.width = 30;
    tape_pointer.height = 30;

    app.stage.addChild(tape_pointer);
}

function RenderTapeWPixi() {
    firstTapeSquare = new PIXI.Text("1", { fontName: "foo" });
    secondTapeSquare = new PIXI.Text("0", { fontName: "foo" });
    thirdTapeSquare = new PIXI.Text("0", { fontName: "foo" });
    fourthTapeSquare = new PIXI.Text("1", { fontName: "foo" });
    fifthTapeSquare = new PIXI.Text("0".toString(), { fontName: "foo" });
    sixthTapeSquare = new PIXI.Text("0", { fontName: "foo" });
    seventhTapeSquare = new PIXI.Text("1", { fontName: "foo" });

    tapeSquaresArr = [firstTapeSquare, secondTapeSquare, thirdTapeSquare, fourthTapeSquare, fifthTapeSquare, sixthTapeSquare, seventhTapeSquare];

    const style = new PIXI.TextStyle();

    for (var i = 0; i < 7; i++) {
        // Apply the font to our text
        style.x = app.screen.width / 2;
        style.y = app.screen.height / 2;
        console.log(app.screen.height / 2);
        tapeSquaresArr[i].x = (app.screen.width - 100) / 2 + (i * 25);
        tapeSquaresArr[i].y = 400;

        // Update the font style
        style.fill = 'black';

        // Update text
        tapeSquaresArr[i].updateText();

        app.stage.addChild(tapeSquaresArr[i])
    }
}

function RenderStateText() {
    stateText.x = 50;
    stateText.y = 400;

    stateText.width = 100;
    stateText.height = 50;

    app.stage.addChild(stateText);

    stateValText.x = 170;
    stateValText.y = 400;
    stateValText.width = 50;
    stateValText.height = 50;

    app.stage.addChild(stateValText);
}
```

Here is a brief explanation for the functions above:

- `RenderTapePointer()`: This function's main job is to render the tape pointer that will indicate the current tape square that the program is computing. All image objects in the Pixi.js rendering library are called [Sprites](https://pixijs.download/dev/docs/PIXI.Sprite.html). Notice the `app.stage.addChild(tape_pointer)` line which is responsible for showing the Sprite on-screen by adding it to the Pixi.js [Stage](https://api.pixijs.io/@pixi/layers/Stage.html) object. Here is a screenshot of the tape pointer:


![Figure 4: Tape pointer pointing to the current tape square](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0xo184s3s813qmi52aow.png)

_Figure 3: Tape pointer pointing to the current tape square_

- `RenderTapeWPixi()`: This function renders the actual tape that will be used by the Turing Machine. Since the Turing Machine is setup to run a Palindrome program, having a finite length of tape is feasible. Here is a screenshot of the tape containing some predefined values:


![Figure 5: Tape containing seven binary values](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/h7abglxc59ypk1hvjsyv.png)

_Figure 4: Tape containing seven binary values_

- `RenderStateText()`: This function renders the text that indicates the current state of the Turing Machine. The current state of the machine is important because it influences the selecting of the new symbol to be placed in the currently selected tape square. For example: If the current state is `0` and the current symbol is `1` then the new symbol that will be written into the current tape square is `_`(This is based on the state rules that we will cover soon). Here is a screenshot of the rendered state text:


![Figure 6: Current state text rendered to the stage](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/gar7xjad8aqzz8ialgle.png)

_Figure 5: Current state text rendered to the stage_

Next we'll cover the functions that render the buttons and title for the application:

```
var startBtn = PIXI.Sprite.from("./assets/start-icon.png")
startBtn.buttonMode = true;
startBtn.anchor.set(0.5);
startBtn.position.x = 200;
startBtn.position.y = 150;
startBtn.width = 50;
startBtn.height = 50;
startBtn.interactive = true;
startBtn.on('mousedown', startPalindromeProgram);
app.stage.addChild(startBtn);

var restartBtn = PIXI.Sprite.from("./assets/restart-icon-v2.png")
restartBtn.buttonMode = true;
restartBtn.anchor.set(0.5);
restartBtn.position.x = 200;
restartBtn.position.y = 150;
restartBtn.width = 50;
restartBtn.height = 50;
restartBtn.interactive = true;
restartBtn.on('mousedown', restartPalindromeProgram);
app.stage.addChild(restartBtn);
restartBtn.visible = false;

var stopBtn = PIXI.Sprite.from("./assets/stop-icon.png")
stopBtn.buttonMode = true;
stopBtn.anchor.set(0.5);
stopBtn.position.x = 400;
stopBtn.position.y = 150;
stopBtn.width = 50;
stopBtn.height = 50;
stopBtn.interactive = true;
stopBtn.on('mousedown', stopProgram);
app.stage.addChild(stopBtn);

var resumeBtn = PIXI.Sprite.from("./assets/resume-icon.png")
resumeBtn.buttonMode = true;
resumeBtn.anchor.set(0.5);
resumeBtn.position.x = 600;
resumeBtn.position.y = 150;
resumeBtn.width = 50;
resumeBtn.height = 50;
resumeBtn.interactive = true;
resumeBtn.on('mousedown', resumeProgram);
app.stage.addChild(resumeBtn);

var moveTapeInterval = null;

function stopProgram() {
    moveTapeInterval.pause();
    toggleGameSpeedSliderVisible(true);
}

function resumeProgram() {
    moveTapeInterval.resume(gameSpeed);
    toggleGameSpeedSliderVisible(false);
}

function restartPalindromeProgram() {
    ResetGame();
    StartTape();
    restartBtn.visible = false;
    restartBtnLabel.visible = false;
}

...

const title = new PIXI.Text('Palindrome Program Turing Machine', {
    fill: '#272d37',
    fontFamily: 'Roboto',
    fontSize: 20,
    align: 'center',
});
title.roundPixels = true;
title.x = stageWidth / 2;
title.y = 40;
title.anchor.set(0.5, 0);
app.stage.addChild(title);

```

Here is a brief explanation of the code above:

- `startBtn`: This button controls the start of the Palindrome program. Notice the eventlistener `'mousedown'` which makes starting the Palindrome program possible
- `restartBtn`: This button allows the user to restart the Palindrome program once it has reached the end state. It is not shown in the initial startup of the application
- `stopBtn`: This button pauses the Palindrome program. It is useful for adjusting the game speed which can only be changed when the game is paused.
- `resumeBtn`: This button allows the user to resume the game after being paused. Clicking it also makes the game speed slider disappear in order to prevent the user from changing the game speed while the program is running

Here are screenshots showing all four buttons:


![Figure 7: The start, pause and resume buttons on display](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vzc3o9dbp5io7fwh0m29.png)


![Figure 8: The restart button on display](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/y5g6rdj4kol1l0j0en3t.png)

_Figure 6: The start, pause, resume and restart buttons on display_

Lastly the `title` variable is an instance of [`PIXI.Text()`](https://pixijs.download/dev/docs/PIXI.Text.html), which is used to create a title for the application on the top of the game screen.

#### Developing the internal logic:

Moving onto the internal logic for the application, let's start out by defining the state rules for the Palindrome program:

```
var palindromePrgStateRules = [
    // [<current_state>, <current_symbol>, <new_symbol>, <direction>, <new_state>]
    ['0', '0', '_', 'r', '1o'],
    ['0', '1', '_', 'r', '1i'],
    ['0', '_', '_', '*', 'accept'],
    ['0', '1', '_', 'r', '1o'],
    ['1i', '_', '_', 'l', '2i'],
    ['1i', '*', '*', 'r', '1i'],
    ['1o', '*', '*', 'r', '1o'],
    ['1o', '_', '_', 'l', '2o'],
    ['2o', '0', '_', 'l', '3'],
    ['2o', '_', '_', '*', 'accept'],
    ['2o', '*', '*', '*', 'reject'],
    ['2i', '1', '_', 'l', '3'],
    ['2i', '_', '_', '*', 'accept'],
    ['2i', '*', '*', '*', 'reject'],
    ['3', '_', '_', '*', 'accept'],
    ['3', '*', '*', 'l', '4'],
    ['4', '*', '*', 'l', '4'],
    ['4', '_', '_', 'r', '0'],
    ['accept', '*', ':', 'r', 'accept2'],
    ['accept2', '*', ')', '*', 'halt-accept'],
    ['reject', '_', ':', 'r', 'reject2'],
    ['reject', '*', '_', 'l', 'reject'],
    ['reject2', '*', ')', '*', 'halt-reject'],
];
var comparisonValues = {
    "0": ["0", "*"],
    "1": ["1", "*"],
    "*": ["0", "1", "*"],
    " ": ["_"],
    "_": ["_"],
    ")": [")"]
}

```

The `palindromePrgStateRules` 2d array is an array containing array elements, each with 5 strings in them to represent the following rules:

- The first element represents the current state value of the program
- The second element represents the current symbol that the tape pointer is pointing to
- The third element represents the new symbol that should take the place of the current symbol(second element)
- The fourth element represents the direction that the tape pointer should take for its next move. `'l'` means move to the left, `'r'` means move to the right.
- The fifth and final element represents the new state value that should take the place of the current state value(first element)

Finally, the `comparisonValues` object serves as a comparison reference for the current symbol that the tape pointer is pointing to and the values that are considered equivalent comparisons to it. For example: if the current symbol is `1` then the compatible equivalents to it are `'1'` and `'*'`(based on the line `"1": ["1", "*"],`). This object is very useful in deciding the appropriate next symbol to assign for a given square that the tape pointer is pointing to.

Next, let's cover the functions responsible for starting the Palindrome program:

```
function startPalindromeProgram() {
    renderTapePointer();
    renderTapeWPixi();
    renderStateText();
    startTape();
    toggleStartBtnVisible(false);
    toggleGameSpeedSliderVisible(false);
    startBtnLabel.visible = false;
}

...

function startTape() {
    moveTapeInterval = new IntervalTimer(moveTapeLogic, gameSpeed);
    moveTapeInterval.start();
}

function moveTapeLogic() {
    var moveTapeDirection = ProcessInput();
    var counter = 0;
    console.log("moveTapeDirection: " + moveTapeDirection);
    switch (moveTapeDirection) {
        case "r":
            tape_pointer.x += 25;
            currentHeadIndex++;
            break;
        case "l":
            tape_pointer.x -= 25;
            currentHeadIndex--;
            break;
        case "halt-reject":
            clearInterval(moveTapeInterval);
            moveTapeInterval.clear();
            toggleRestartButton(true);
            break;
        default:
            break;
    }
    counter++;
}

```

Here is a brief explanation for the two functions above:

- `startPalindromeProgram()`: This the main starting function for the whole program. It calls the rendering functions to render the necessary elements on screen, hides the start button and game slider, and finally calls the `startTape()` function.
- `startTape()`: This function starts the program by using the `IntervalTime` class to setup an interval. You might be wondering the purpose of using the `IntervalTimer` class instead of the more convenient `setTimeout()` function. Well here it is: `IntervalTimer` allows for the ability to pause, resume and clear the currently running interval by calling those respective methods.
- `moveTapeLogic()`: This function can be considered the controller for this application because it identifies the output received by calling the `ProcessInput()` function. The output signifies the direction that the tape pointer should move next to, and this logic is handled by the switch statement in this function. The way the tape pointer's position is represented programmatically is via the `currentHeadIndex` variable. When the tape pointer is moved one square to the right this variable is incremented by one, and when the tape pointer is moved to the left `currentHeadIndex` is decremented by one. The ending state is reached when a output of `halt-reject` is received from `ProcessInput()`. The `setInterval()` function underlying `moveTapeInterval` is cleared, which brings the program to an end.

Next we'll cover the main processing function for this application:

```
function ProcessInput() {
    var i = 0;
    var foundMatch = false;
    for (i = 0; i < palindromePrgStateRules.length; i++) {

        var textComparison = null;
        var currentTapeVal = null;
        if (currentHeadIndex >= tapeSquaresArr.length) {
            textComparison = compareTapeValues(" ", palindromePrgStateRules[i][1]);
            currentTapeVal = " ";
        } else {
            textComparison = compareTapeValues(tapeSquaresArr[currentHeadIndex].text, palindromePrgStateRules[i][1]);
            currentTapeVal = tapeSquaresArr[currentHeadIndex].text;
        }

        if (textComparison && currentState == palindromePrgStateRules[i][0]) {
            var newTapeSymbol = setNewTapeSymbol(currentTapeVal, palindromePrgStateRules[i][2]);

            try {
                tapeSquaresArr[currentHeadIndex].text = newTapeSymbol;
                tapeSquaresArr[currentHeadIndex].updateText();
            } catch (err) {
                console.log("current head index is empty");
            }

            currentState = palindromePrgStateRules[i][4];
            stateValText.text = palindromePrgStateRules[i][4];
            foundMatch = true;
            break;
        }
    }
    if (foundMatch) {
        return palindromePrgStateRules[i][3];
    } else {
        return "halt-reject";
    }
}
```

The `ProcessInput()` function performs the following steps in determining the next action to take when presented with the current input symbol. That is, the current tape symbol that the tape pointer is pointing to.

1. It loops over the `palindromePrgStateRules` array in order to find a matching element for the current state of the game. For example: if the current state value is `2i` and the current tape symbol is `1` then the element `['2i', '1', '_', 'l', '3']` matches this criteria.
2. Following the example in the previous step: the new symbol for the tape square is set to `_`, the tape pointer is moved one position to the left, and the state value is change from `2i` to `3`.
3. In the event that a matching element in the `palindromePrgStateRules` array is not found to match the current state of the program, the `halt-reject` value is returned by the function and the program is bought to the end state.

Let's quickly look at the function for comparing the current input symbol to a given input symbol in the `palindromePrgStateRules` array:

```
function compareTapeValues(currentHeadVal, stateCurrentSymbolVal) {
    if ((currentState == "accept" || currentState == "accept2") && currentHeadVal == "_") {
        return true;
    }
    if (comparisonValues[currentHeadVal.toString()].includes(stateCurrentSymbolVal.toString())) {
        return true;
    } else {
        return false;
    }
}
```

The above function uses the `comparisonValues` object that we defined earlier in determining whether `currentHeadVal` and `stateCurrentSymbolVal` match. Keep in mind that the symbol: `*` that is found in some elements of `palindromePrgStateRules` means that the `currentHeadVal` gets a free pass; it will match up to any given `currentHeadVal` value. Another condition that is considered a match is when the current state value is set to `accept` and `currentHeadVal` is `_`.

Now let's visit the function responsible for restarting the program if the user wants to run it once more:

```
function resetGame() {
    // Reset tape numbers to defaults
    const tapeNumDefaults = ["1", "0", "0", "1", "0", "0", "1"];

    for (var i = 0; i < tapeSquaresArr.length; i++) {
        // Apply the font to our text
        tapeSquaresArr[i].text = tapeNumDefaults[i];

        // Update text
        tapeSquaresArr[i].updateText();
    }

    // Reset tape pointer to default position
    tape_pointer.x = app.screen.width / 2 - 45;
    tape_pointer.y = (app.screen.height / 2) + 150;

    // Reset current head index and current state variables to 0
    currentHeadIndex = 0;
    currentState = '0';

    toggleStartBtnVisible(false);
    toggleGameSpeedSliderVisible(false);
}
```

The `resetGame()` function resets the main state variables in the program(`currentHeadIndex`, `currentState`) to their default values along with changing the tape square symbols back to their default values and moving the tape pointer sprite back to its starting position. Finally, the start button and the game slider is hidden. The restart button will be displayed in place of the start button, which gives the user the option to restart the Palindrome program.

That brings the development section of this blog post to a close.

If you made it this far then congratulations! You have a pretty good idea of how this application functions.

## Program Demo:

Here is a gif showing a demonstration of this program:

[Game demonstration link on Imgur](https://imgur.com/a/9ZvAFAH)

## Conclusion

Thanks for reading this blog post!

If you have any questions or concerns feel free to post a comment in this post and I will get back to you if I find the time.

If you found this article helpful feel free share it and make sure to follow me on [Twitter ](https://twitter.com/SeanAtukorala)and [GitHub](https://github.com/ShehanAT), connect with me on [LinkedIn](https://www.linkedin.com/in/shehan-atukorala-8631491a5/) and subscribe to my [YouTube channel](https://www.youtube.com/channel/UCtxed_NljgtAXrQMMdLvhrQ).