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:
Looks pretty confusing. From the first look, it’s hard to find similarities with programming languages. So your first reaction might be like:
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.
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.
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:
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.
Credit: Source link