Introduction of Turing Machine
Today, computers are in every household and most people know how to use them. Computers have become the basic tool of daily people lives. However, not all people know the basic model and theory behind computers. The Turing machine is the original idealized model of a computer, and it provided the basic and original computer programming algorithm. In 1936, Alan Turing, the father of theoretical computer science and artificial intelligence, built the first Turing Machine in the world (Beavers). Turing worked for the Government Code and Cypher School at Bletchley Park, Britain's code-breaking center, during the World War II(Copeland). He used his machine to help the English army decipher the German Enigma – a kind of Morse code. Morse code is a method to transfer information with dots and lines. Also, the Turing Machine, which Turing called his child, gave the basic design model to design the modern computer, and it also provided the basic programming algorithm.
In the beginning, Turing wanted to use the Turing machine instead of people to perform complicated and difficult calculations. At that time, Morse code and other secret codes were used for transmitting classified information; governments needed to train professionals to analyze codes, and the analysis required a complicated calculation. The Turing machine solved this problem. Users needed to follow the Turing Machine’s grammar, the grammar of the Turing Machine algorithm is a kind of string reading method, to set up the algorithm of secret codes; users put a special paper tape in the Turing machine, and then the Turing machine calculates and analyzes the string or symbol on the tape. This saves time when training professionals to analyze Morse code. In addition, the theory behind the Turing machine’s structure also is the theory behind building computers and the creation of computer programming. For example, in ASCII (American Standard Code for Information Interchange), each character on the keyboard corresponds to a decimal number, and the decimal numbers translate to binary numbers. These binary numbers are used by the Turing machine to create the computers’ structure because the core algorithm of computers can only analyze true and false (in programming, 1 is true, and 0 is false).
The Turing machine, like Figure 0, consists of a paper tape that records the code that is being analyzed, a head that can read and write symbols, a state register that can save the states of the Turing machine, and a finite table of instructions that can control movement when the Turing machine reads a symbol.
Figure 0: From “Lego Turing Machine”
Tapes are the original input of the Turing machine. These kinds of tapes are divided into cells, one next to the other, like in Figure 1. The tape can have different symbols (the color of symbols normally is black), such as 0, 1, $, #, etc. Most of the time, the Turing machine uses the “space” symbol to indicate the end of the tape, in other words, an empty cell is always at the end of the Turing machine tape. Also, either “$” or “#” is the symbol used for the tapes’ beginning. Because the Turing machine reads tapes from left to right, “$” and “#” are not necessary for the tape. Number characters, such as 0, 1, and 2, are always used to tell the Turing Machine which direction it should move for the next steps and which symbol it changes in the tape.
Turing Machine uses optic theory to read tapes. When cells are not blank (have the black symbol), it will think it has “food” in cells. Then, Turing Machine will read the symbols and “remember” them. When cells are blank, the machine will think it does not have “foods” in cells, so it will stop.
Figure 1: Turing Machine Tape, from “Turing Machine”, by Barker-Plummer
The head is used for reading and writing each character when it moves on tapes, as shown by Figure 2. The head in the Turing machine not only has the ability to read and write characters in the tapes, but it can also tell the Turing machine to move to the right or left. The basic order of the Turing machine reads tapes is from left to right, but this order is only during the beginning processes because there is no character to the left of the first character. When the Turing machine reads characters in the tape, it will know which kind of algorithm the code uses; in other words, the Turing machine can put original and source code together. Thus, when the Turing machine gets the calculation method, it needs to change some characters to “marked” to get the grammar as in Figure 4. Thus, the head needs to have the ability to change some characters in the tape.
Changing characters is a necessary process of the Turing Machine; characters, which have been changed, are like a “mark” to the Turing Machine, which determine of grammar or process the Turing Machine will do. When the Turing Machine reads a character and changes this character(s), it will find the other character(s) which can correspond to this character in the Turing Machine’s grammar. When the Turing Machine finds other characters, it needs the head to change the directions of reading tapes. Changing direction is a necessary function for Turing Machine because for most of Turing Machines should find the corresponding characters when they read a character, so this character may make the head move to the right or the left depending on different grammar.
In addition, some Turing Machines do not have to make a grammar in the beginning, such as the Turing Machine in Figure 3. The Turing Machine in Figure 3 is used for analyzing three letter strings to tell whether or not they follow the mathematical calculation “XOR.” Because this kind of Turing Machine does not have complicated and difficult calculations, it does not need to input and organize the rules in the beginning. Therefore, the head is like a person’s hands and eyes which is used to read and take notes to analyze information from tapes.
Figure 2: Head of Turing Machine, from “Turing Machine” by Jeff Stefan
The Turing machine’s states register and the table of instructions describe the algorithm of the machine. These two elements are like a graph, as in Figure 3, to tell users and the machine the coding algorithm. In Figure 3, all “circles” are the states, and the words beside the “⟶” are the transaction functions. According to this sample of the Turing Machine algorithm, the Turing machine has two different states registers: accept and reject. The accept register means the code in the tape can reach the goal of the grammar in the end which people input into the machine at the beginning, and the reject register means the code cannot reach the goal. In the table, the “⟶” in Figure 2 and 3 tells users and the machine which cell the head is reading and how to move and write in the next step.
Figure 3: The graph of Turing Machine working, and how states register and table describing, Language , from “Lecture Notes 2/11/2016” by Rob Gysel. Turing machine can be formally define by 7-tuple where Q is the finite set of all states in Turing machine, is the set of input alphabet, is the set of tape alphabet, q0 is the start state, qaccept is the accepted state, qreject is the rejected state (except the accept states, all other states are reject states), and is the transaction functions between each state (Gysel).
For example, the Turing Machine in Figure 3 recognizes the language —in computer science, using language and this kind of format to analyze the rules and grammar of the Turing Machine. In this language A, u, v, and w are the string which is made up by 0 and 1, and the length of u, v, and w are the same; “w = u XOR v” means that the same place of u and v have the same number, both 0 or 1, this place of w will have 0; if the place is different, one is 0 and one is 1, and its place is one in the string w for this place. For instance, if u is “1011” and v is “1111,” w should be “0100.” The “# 1011 # 1111 # 0100” exists which is an element in A. Now, the tape input in the Turing machine is “# 1011 # 1111 # 0100_” (“_” means “space,” and it is the ending symbol on the tape), and this tape is an accepted string—the string can make the Turing Machine achieve goals, and it can output the result. The process of this tape is shown in Figure 4; the red color is the where the head is. Because the final state of this tape makes the Turing machine’s head on “_” and state register moves to the accept state, it is an accepted string for Turing Machine A.
Figure 4: (Red is where is the head, and from left to the right) The Turing Machine A runs tape “# 1011 # 1111 # 0100_”, graphed by Chengji Yang
The Turing machine shows a process: program and input are saved on the tape, and then the Turing machine follows the program step by step to calculate and puts the result on the tape. The Turing machine’s structure shows how modern computers have three main hardware structures: RAM, CPU, and I/O system. The RAM (random access memory) is used to exchange data with the CPU and temple saving data; RAM is not only read data by computers, it also can be written data. The RAM is like the tapes in the Turing machine because they work to save data and output results. In the Turing Machine, tapes are a kind of carriers to record the result and details for machines; tapes not only give the information to the machine, but also get the result from machine. The CPU (central processing unit) performs the basic arithmetic, logic, control and input/output operations specified by instructions; it controls computers’ “actions” and propose methods to record data. It is like the finite table of instructions and state registers. The finite table of instruction is the theory to control machines reading and writing, and the state registers tell a machine how to record data on tapes. The I/O system (input and output system) is used to input and output data and it can perform multiple controls at the same time; I/O system record 1 and 0 on the hardware. When I/O system read data, it will read all the 1’s and 0’s on the hardware and analyze which kind of program should be executed. When it outputs data, it will “write” 1’s and 0’s on the hardware to record data. 1’s and 0’s are like characters on input tapes because both of them have the function to record data, but tapes cannot remember the data before the machine is working. The Turing Machine gives the basic design model and programming theory behind modern computers.
Reference List:
Beavers, Anthony, Alan Turing: Mathematical Mechanist. Waltham: Elsevier. 2013. Pp. 481-485
Copeland, Jack (June, 2012). Alan Turing: The Codebreaker Who Saved ‘Millions of Lives’. BBC. New Zealand. [Online]. Available: http://www.bbc.com/news/technology-18419691
Stefan, Jeff (July, 1997). Turing Machine. Nuts and Volts. [Online]. Available: http://www.nutsvolts.com/magazine/article/turing_machines
Barker-Plummer, David (September, 1995 and June, 2012). Turing Machine. Stanford Encyclopedia of Philosophy. [Online]. Available: http://plato.stanford.edu/entries/turing-machine/
Copeland, B. Jack (December, 2000 and June, 2006). The Modern History of Computing. Stanford Encyclopedia of Philosophy. [Online]. Available: http://plato.stanford.edu/entries/computing-history/
What is a Turing Machine? Wolfram Science. [Online]. Available: https://www.wolframscience.com/prizes/tm23/turingmachine.html
Copeland, Jack. What is a Turing Machine? AlanTuring.net [Online]. Available: http://www.alanturing.net/turing_archive/pages/reference%20articles/what%20is%20a%20turing%20machine.html
Lego Turing Machine. Ri Channel. [Online]. Available: http://www.richannel.org/lego-turing-machine
Gysel, Rob. Lecture Notes 2/11/2016. February 2016.
