Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore.

15 St Margarets, NY 10033
(+381) 11 123 4567



Turing Machine: Prototype of Programming Language

Programming Language Roots

Nowadays programming languages are recognized as something ordinary, which does not come as a surprise. But in general, this technology is relatively young and appeared about 50 years ago. The first abstract idea of a programming language was introduced in mathematics. There are many related notions, such as a state machine, computer algorithm, and combinational logic, that have been introduced in mathematics and after defining the notion of the Turing machine.

Founder of IT Era: Alan Turing

Alan Turing, the Father of computer science, invented the Turing machine in 1936. Alan Turing is a legendary person who anticipated the IT era and became its founder. He is also known as a person who cracked the Enigma code and brought significant value to the second World War victory. His prediction that programming languages will be a part of normal life before the year 2000 was unthinkable during the years of his life.

Father of All Programming Languages: Turing Machine

The Turing machine is a mathematical abstraction that allows one to “write” first programs. You can create your “application” by having just a list of papers. Before we move forward, let’s introduce core notions of the Turing machine:

Core notions of Turing machine

Looks pretty confusing. From the first look, it’s hard to find similarities with programming languages. So your first reaction might be like: 

Where Coding with gorillas

Writing First “Hello World” Turing Machine

Well, coding is not as far as it looks. Let’s write our first “program” using the Turing machine model. Our “hello world” program will just inverse binary numbers.  

Inverse binary numbers

Explaining Table of Instructions

0 and 1 at the left side corresponding to potential values on tape. Q1 and Q2 are statuses meaning current machine status. At the intersection of both of them we can find instructions to be executed by the machine; for example, write 1, move right, change state to Q2.  

Executing Written Turing Machine

Now let’s see how our Turing machine is working for input “001101”. I used the application “turing machine” from this website.

Turing machine with input 001101

More Complex Turing Machines

An example of a Turing machine that just inverted binary numbers looks too obvious and is still far from real development. Let’s see a more complex scenario: an example with the machine that removes all “a” characters from a string:

Turing machine example removing all "a" characters from a string


In this article, I’ve introduced the main idea of the Turing Machine and shown some examples. The Turing Machine is a much more complex model than covered here. I did not include some important notions like Turing completeness, but here you can find more details about it.

In Memory of Alan Turing

Those seeds planted by Alan Turing gave our civilization unthinkable technologies. IT technologies have changed all domains: medicine, space, finance, physics, chemistry, etc. The height of the injustice is that the person who gave rise to these miracles was driven to suicide. The past cannot be returned, but each of us can honor Alan Turing with his memory.

If I have seen further it is by standing on the shoulders of Giants.

Alan Turing memorial plaque

Credit: Source link

Previous Next
Test Caption
Test Description goes like this