+--------------------------------+ | | | TURING PROGRAM TUTORIAL FILE | | | +--------------------------------+ The purpose of this file is to provide a tutorial lesson on some of the basic features of the program called TURING. While it is possible to learn how to use the program by reading all the built-in help screens contained within each menu, if you are a first-time user, we suggest you read this tutorial while first running the program, and then later you can digest all the information contained in the help functions within each menu in the program. You can import this file, TURING.TXT, into any word processor and then print it so you can read the hard copy output while you run the program. To begin the tutorial you must have the program file TURING.EXE and the three corresponding demonstration program files called TDEMO1.TXT, TDEMO2.TXT, and TDEMO3.TXT. We assume these four files are in the current directory on the currently selected disk drive. PRELIMINARIES ============= KEYBOARD CONVENTIONS -------------------- As part of this tutorial we need to give directions on which keys to press on your keyboard. We will enclose in angle brackets single keystrokes that you should type. For example, if we ask you to type the first three letters of the alphabet we will show <A> <B> <C>. If we ask you to press the control key, the alternate key, the backspace key, the space bar, or the enter (or return) key, we will show <CTRL>, <ALT>, <BACKSPACE>, <SPACE> or <ENTER>. Each enclosure in angle brackets should refer to exactly one keystroke or one character. On most keyboards, to type in a left or right parenthesis requires using a <SHIFT> key in conjunction with another key. We will NOT show the shift key as a separate keystroke in this tutorial because we consider entering a parenthesis as entering a single character. Other characters like <+> or <*> can be entered in two different ways on some keyboards, one way uses the <SHIFT> key, the other way does not. In general, we would only show the single character in angle brackets and we leave it up to you to decide whether or not the <SHIFT> is needed to enter the character. These keyboard conventions should make clear exactly how many and which keys you press. If it is necessary to press two keys simultaneously we will show a connecting plus sign between the keystrokes. This is done primarily with the Control key <CTRL>, and the Alternate key <ALT>. For example, when we show <ALT>+<X> it means you should press both the Alternate key and key X at the same time. <ALT>+<X> is used in the Main Menu to exit from the program. ADVICE FOR NOVICES AND EXPERTS ------------------------------ This tutorial file assumes you have the mathematical background required to understand the features that will be demonstrated. You may find some sections more applicable to novices than experts, or vice versa, depending on your background and experience. If you encounter an example that is beyond your understanding, you can either skip that example, or you can press the keys and view the results, even though you may not fully comprehend the output. This tutorial does not discuss techniques on how to best use or apply the available features. It only serves to demonstrate the basic features and capabilities which you can learn to apply to solve problems that are of interest to you. GETTING STARTED =============== To begin running the TURING program type the command: <T> <U> <R> <I> <N> <G> <ENTER> The program called TURING simulates what is called a Turing Machine. Such a machine is an abstract model used to study the fundamental aspects of digital (logical) computations. A simple Turing machine is all that is required to model any digital computation on any computer, past, present, or future! Alan Turing was a British mathematician who conceived the idea in 1935, long before computers were established. Turing also helped design and build the machines which were used to break the secret German Enigma spy codes in World War II. Turing committed suicide in 1954 after having been exposed as a homosexual. There are three major components in the Main Menu screen. At the top of the screen is a representation of a recording tape which has numbers recorded on it. Initially all the numbers are 0 and each position on the tape is delineated by a little box. The boxes are numbered from 1 to 999 and only a portion of the middle of the tape is shown. The only two numbers that are allowed to be recorded on the tape are 0 and 1. The tape used in the abstract model of a Turing machine is infinite in length in both the left and right directions, but we will find it convenient to label (number) each position on the tape. This recording tape is the first major component of the Turing machine. Numbers are read or written on the tape at the position marked by what we call the Read/Write Head. This appears as a solid-white rectangle which covers the tape. The number which is on the tape under the Read/Write Head can also be seen. Any number which is read or written must pass through the Read/Write Head. The Read/Write Head is the second major part of the Turing machine. The third major component is what is called the State Transition Table. Essentially this table contains the directions for telling the machine how to operate, much like a paper roll is used to control a player piano. To understand how this table operates in conjunction with the recording tape is to understand the basics of a Turing Machine. If you have never seen a Turing Machine before, when you finish reading this tutorial and running the examples, you should have gained an appreciation of the concept. You may even be ready to write some simple Turing Machine programs that you create on your own. A FIRST PROGRAM =============== The first program we will run is the default program that has already been loaded into the State Transition Table. This is a very simple program that increments a number by 1. HOW UNARY NUMBERS ARE REPRESENTED ON THE TAPE --------------------------------------------- First we have to explain that numbers written on a Turing machine tape have a very simple representation. These numbers are NOT BINARY, in fact they are sometimes called unary. Everyone should be familiar with making tallies by writing vertical slashes on a piece of paper. Unary numbers are loosely analogous to tallies. For example, four consecutive vertical marks written like | | | | | | | | | | | | could represent the number 4. In traditional tallying, when you mark a fifth tally you draw it across the previous four tallies. So a stick representation of five tallies might look something like this | | | | -+-+-+-+- | | | | Well the analogy breaks down here. On a Turing machine tape each unary number is represented by a series of consecutive 1's. The number 4 would be represented by four consecutive ones like 1 1 1 1 but a number like 7 would be represented by seven consecutive ones like 1 1 1 1 1 1 1 In traditional tallying a number like 7 would be represented by a group of five, plus two additional tallies. | | | | | | -+-+-+-+- | | | | | | | | On a Turing machine tape, there is no crossing allowed. Just count consecutive 1's and you know what the number is. READING THE STATE TRANSITION TABLE ---------------------------------- The initial State Transition Table should appear as follows: +----+---++---+---+----+ | S# | R || W | M | N# | +----+---++---+---+----+ | 1 | 0 || 0 | R | 1 | | 1 | 1 || 1 | R | 2 | | 2 | 0 || 1 | R | 3 | | 2 | 1 || 1 | R | 2 | | 3 | 0 || 0 | H | 3 | | 3 | 1 || 0 | H | 3 | +----+---++---+---+----+ The five column headings represent the following. S# = the current State number R = the symbol which is Read from the tape (must match table R-value) W = the symbol which is Written back on the tape M = the direction of Movement. R=right L=left H=halt N# = the New state number Each line in the table has an interpretation. For example, the first two lines in the table can be interpreted as saying: If you are in state 1 and a 0 is read from the tape, then write a 0 back on the tape, move the tape to the right and remain in state 1. If you are in state 1 and a 1 is read from the tape, then write a 1 back on the tape, move the tape to the right and enter into state 2. The double vertical line in the table serves the purpose of separating the input (S# R) in the two left columns from the output (W M N#) in the last three columns. The following shows the same table with comments to the right o...
adamkozicki