Let’s build a Turing machine in Javascript (Day 3)

Welcome back,

As I have promised, I've made a toy Turing machine for you. Today, we will learn to program it. We're going to write a binary counter program to run it on our toy machine. Are you ready? You might ask two questions, so I'm going to answer them right away:

  • what is a binary number and how to count it? -- just like we have natural numbers (called decimal numbers) ranging from 0 to 9, binary numbers are another number system which ranges from 0 to 1. I need you to observe a pattern here, to see things clearly. For decimals, as we count, after reaching 9 we will go for repeated combinations for the next digit. For example, 00, 01, 02, ..., 0_, ..., 09, 10, 11, ..., 1_, ..., 19, 20, 21, ..., 2_, 29, 30, 3_, ..., 4_, ..., 1__, 2__, ..... This same pattern is used to create sequences for binary numbers as well. Like, 00, 01, 10, 11, 100, 101, 110, 111, ....

We're going to base our binary counter program on this idea. Here's our logic described as a table.

screenshot from 2018-03-05 10-46-38

If we visualize the above logic, it becomes more clear to us.

binary counter

in the above didgram, red lines represents a read 0, green line represents a read 1 and blue lines represents a read blank. A transition for eack read is shown along with each connection, where w:is a write operation and m: is the tape movement to be done after write. Stop state will terminate the program execution.

so far, so good.. Now, its time to write our program. Our toy Turing machine will only understand a kind of structured instructions. So, we need to talk in that language by following strict rules. This will be an Aha! moment for you, if you are familiar with JSON. But don't worry starter, just focus on the above table, I will break everything down for you.

Let me write down the code first.

{
    "states": [
        {
            "0": {
                "write": "0",
                "move_tape": "left",
                "next_state": 0
            },
            "1": {
                "write": "1",
                "move_tape": "left",
                "next_state": 0
            },
            "blank": {
                "write": "",
                "move_tape": "right",
                "next_state": 1
            }
        },
        {
            "0": {
                "write": "1",
                "move_tape": "right",
                "next_state": 2
            },
            "1": {
                "write": "0",
                "move_tape": "right",
                "next_state": 1
            },
            "blank": {
                "write": "1",
                "move_tape": "left",
                "next_state": 2
            }
        },
        {
            "0": {
                "write": "0",
                "move_tape": "left",
                "next_state": 2
            },
            "1": {
                "write": "1",
                "move_tape": "left",
                "next_state": 2
            },
            "blank": {
                "write": "",
                "move_tape": "right",
                "next_state": -1
            }
        }
    ]
}

How to write it - if you remember these rules, you will be able to deduce our logical table into our hypothetical Turing machine code (here, its JSON).

  • the whole code is enclosed inside a pair of curly braces {}. { }
  • anything enclosed inside [] (a pair of square brackets), separated by commas (,) is some state having specific properties. To specify that the collection is of states, we label them with a key "states". {"states": [state_1, state_2, ... , state_n]}
  • in each state, there are three possibilities. The read head might read a 0, a 1 or a blank symbol from there, which will determine our next actions. So, each element in a state represents a possibility. {"0": { ... }, "1": { ... }, "blank": { ... }}
  • and for each possible reads, let's specify actions to be done. write() to the tape, move() the tape and transition() to the next state.
                "0": { "write": " ... ",
                      "move_tape": " ... ",
                      "next_state": ... 
                     }

Now let's see how our machine works #

copy the above code and paste it into the text box and press run button.

Whoo. Our machine just started counting to 1. Press the button again, then it will increment 1 to 10. If you press again, it will show 11. and so on.. Don't you remember the previous pattern that we've written down?

I want you to try more examples with our toy Turing machine. To see more logical tables, just go here and try converting them to our machine friendly code.

It was an awesome day, right? Don't loose that excitement till we meet again. bye.

footnote: by the end of this article, we indirectly introduced you to the concept of state spaces and state transitions. We believe that in the upcoming articles, this tiny idea will highly influence your thought process. This will also give you an intuition on why some algorithms that outperform others, have a close relationship with the hardware its implemented on. This concept paved the baseline for a wide variety of technologies ranging from the very low-level implementations to high-level ones, both on hardware and software, and can be interpreted in different ways as an abstract representation. We will see some of the examples that can be considered as a matured version of this idea.

About Author

Jubin Jose

Chatbot Developer at Cedex Technologies LLP | Technology: C, Node JS Hobby: beginner ML & AI + creative coding + Youtuber.


Want to work with us?

Be free to contact us for any of your chatbot development queries. As a company specialized in Chatbot development, we can provide you quality services. We will be happy to provide you a free quote.

Contact Us