Friday, September 23, 2016

                         Turing Machine

Turing machines are the original idealized model of a computer invented by Alan Turing in 1936. They were initially called a-machines, which referred to the automatic machine. They are equivalent to modern electronic computers at a certain theoretical level, but differ in many details.Turing machines are simple abstract computational devices intended to help investigate the extent and limitations of what can be computed.They are finite state machines with the ability to read and write data to a tape with an unlimited supply of paper. There are formulations of Turing machine, but essentially the machine reads a symbol from the tape, which is used as an input to the finite state machine.
 The turing machine consists of a tape, a head, a state register and a finite table of instructions. A tape is divided into cells, one next to the other. Each cell contains a symbol from some finite alphabet. The alphabet contains a special blank symbol which is denoted by '0' and one or more other symbols. The tape is assumed to be arbitrarily extendable to the left and to the right.The head is the part of the machine that can read and write symbols on the tape and move the tape left and right one (and only one) cell at a time. In some models the head moves and the tape is stationary.state register is the part that stores the state of the Turing machine. Among these is the special start state with which the state register is initialized. The finite table of instructions tells the computer to either erase or write a symbol, move the head and then assume the same or new state.

The initial arrangement of the colors of the cells on the tape correspond to the input given to the computer. This input can contain both "program" and "data". The steps of the Turing machine correspond to the running of the computer. The rules for the Turing machine are analogous to machine-code instructions for the computer.Given the particulars, each part of the rule specifies what "operation" the machine should perform. The remarkable fact is that certain Turing machines are universal with the appropriate input. They can be made to perform any ordinary computation.
___________________________________________________________________________

Reference



___________________________________________________________________________


1 comment:

  1. Hi Ruhi, nice post! It's incredible how much Alan Turing contributed to the field of computer science, especially with the Turing Machine. Although the movie The Imitation Game brushes over these accomplishments a bit and focuses more on his role as a codebreaker during the second world war, I would definitely recommend it if you're interested in learning more about him. My post this week was about the Turing Test for AI, you may be interested in that too!

    ReplyDelete