How it all started and where it’s heading next ?
Turning Machine and its Importance
Turing machine is a computer invented in 1936 by Alan Turning. It consists of a read/write head and a paper tape that passes through it. The tape is split into squares, each bearing a single symbol ‘0’ or ‘1’. This tape serves as the machine’s storage medium and act as both input and output vehicle. It also works as a memory for storing the results of intermediate calculation processes. Before the calculation can begin, the input must consist of a finite number of symbols imprinted on the tape. The tape, however, is boundless in length, as Turing’s goal was to demonstrate that even with unlimited working memory and time, these computers are incapable of doing certain tasks. The read/write head can be customized. It’s beneficial to conceive about programming as changing the internal wiring of the skull via a plugboard layout. To use the machine, you must first program it, then inscribe the input on the tape, position the head over the square holding the leftmost input symbol, then turn it on. The machine will come to a standstill with the head positioned over the square holding the leftmost symbol of the output after the calculation.
Turing machine can perform six types of computational operations which would be read, write, move the tape left / right one square, change state and halt. The machine’s elementary or atomic actions are referred to as such. Millions of these atoms may appear in a sophisticated calculation. As said by Kerry, Ann(1) that turning machine are the foundations of modern computers and all the modern computers and calculations are based on the principles and fundamentals of the Turing machine. Commercially available computers are hard-wired to execute elementary operations far more complex than those performed by a Turing machine, such as add, multiply, decrement, store-at-address, branch, and so on. The exact composition of the primitives list differs from one manufacturer to the next. None of these computers can outperform a Turing machine, which is a stunning fact. Despite its austere simplicity, the Turing machine can calculate whatever that any computer on the market is capable of computing. A Turing machine’s program is a finite set of instructions, each of which requests that specific atomic operations be done if certain criteria are satisfied. Every instruction is in the following format: If the current state is n and the symbol beneath the head is x, write y on the square under the head [y may be identical to x], enter state m [m may be n], and — -. ‘Move left one square, “move right one square,’ or ‘stop’ may be written in lieu of — — -(2). A Turing machine can be configured in two ways to behave in line with a program. One is to change the ‘wiring’ in a Turing machine’s head. Second the machine table is translated into binary code and inscribed on the tape of a particular Turing computer known as a universal Turing machine. Turing was able to show that if the head of a Turing machine is programmed in accordance with U, and any table, P, is translated and put out on the machine’s tape, the machine will act as if its head had been programmed in accordance with P. Any Turing computer whose head is programmed in accordance to U is referred to be a universal Turing machine.
Despite being computational guru or the genius Turning machine also has many limitations. Turing machines have the drawback of being unable to accurately simulate the strengths of a given configuration. Modern stored-program computers are examples of a more particular type of abstract machine called a random-access stored program (3). A RASP machine model or an experimental prototype to machine. The RASP, like the Universal Turing machine, stores its “program” in “memory” separate from its finite-state Turing machine’s “instructions.” Because the RASP’s finite-state machine supports indirect addressing, the RASP’s “program” may address any register in the register-sequence. As a result of this distinction, it is feasible to implement computational optimizations based on memory indices that are not conceivable in a typical Turing machine. Turing machines are used to bound running times, and a ‘false lower limit’ may be proved on the running times of certain algorithms. Binary search is an example of this, which can be proven to run faster when utilizing the RASP model of computing rather than the Turing machine model. Another flaw with Turing machines is that they don’t do a good job of modeling concurrency. For example, an always halting nondeterministic Turing computer starting on a blank tape has a limit on the size of integers it can compute. There exist, on the other hand, always-halting concurrent systems with no inputs that can calculate an unlimited integer.
References:
1) Ann, K (Jun 2017). “Alan Turing: Crash Course Computer Science #15”. CrashCourse. https://www.youtube.com/watch?v=7TycxwFmdB0&t=5s
2) Copeland, J. “What is a Turning Machine?”, AlanTuring.net
3) Ques10. “State and Explain the power and limitations of a Turing Machine”.
