Alan Turing
Recently a friend of mine (I’ll call him Jim – not his name) asked me to teach him how to write computer programs. Since my current favorite language is Ruby, I suggested that he start with one of the Ruby tutorials. We had our first session together a couple of weeks later. Jim had gotten a fair way through the tutorial and knew the basics of Ruby but, I realized, he had no real understanding of what a computer program was about. So I decided that we should write a real computer program.
I had recently been reading about Alan Turing and his code breaking efforts in World War II. So I set Jim the problem of building a program to implement a symmetric cypher. A symmetric cypher is one where enciphering plain text produces the cyphered text, and using the same procedure on the cyphered text produces the plain text.
I asked Jim to invent a simple symmetric cypher. With some prompting he came up with a cypher which exchanges adjacent letters in the text. Thus “adjacent” becomes “daajectn” which works for text with an even number of letters but fails for an odd number of letters, as we found out with our first attempt at programming it. Jim very much enjoyed this exercise.
In our next session we fixed the problem caused by an odd number of letters and improved the program so that instead of requiring the input text to be a constant within the program, the input was read from the terminal. Here is the final program:
while true
puts “??”
x = gets.strip
if (x.strip == “quit”)
break
end
lst = nil
if x.size % 2 == 1
lst = x[x.size-1]
x = x[0, x.size-1]
end
y = “”
(0..(x.size/2 – 1)).each do |i|
y = y + x[i * 2+1] + x[i * 2]
end
if lst
y = y + lst
end
puts y
end
Rather than concentrating on the syntax of Ruby, we concentrated on what constitutes a computer program and how one goes about designing one. When we needed to know something about Ruby syntax, for example how to read a line from the console, we Googled it.
Jim and I have not yet had our third session. As homework I gave him the choice of two problems. The easy one is to think of and implement a cypher that is harder to break than our simple letter exchange cypher. The second, much harder problem is to build an emulator for a single-instruction computer. Here is the statement of the problem:
A simple, practical Turing-complete computer
Typically a CPU will be able to obey many different instructions, for example, add two numbers, subtract, multiply, or divide them. Also combine two numbers according to boolean algebra. Also read a number from an input device or write a number to an output device. And test a number and control execution of the program based on the result, for example by going to different parts of the program.
Although all modern computers can execute a variety of different instructions, it turns out that this is not necessary. There are a few instructions that each are all by themselves Turing complete (one instruction set computers). We’ll take advantage of this in designing our simple computer. The instruction we’ll use consists of four numbers, we’ll call them A B C D. The English description of what the instruction does is:
“Read a number from memory location B (for example, location 105) and subtract it from the number in location A. Then put the result into location C. If the result of the subtraction is less than or equal to zero, go to address D in the program, otherwise execute the next instruction in the program.”
Our machine will have an ordinary memory, as large as we like. These are cheap and easy to use these days. It will have a punched paper tape reader for input because these are simple and easy to use, and it will have a paper tape punch for output.
The CPU is very simple. It will have seven registers, each capable of holding a number. One of these is the program counter which holds the memory address of the first of 4 numbers making up the current instruction in the program. The next four registers hold the four numbers of the current instruction The other two registers, called register ! and register 2, are used to hold the numbers referred to by the current instruction.
Here is a complete description of what our CPU does:
- Read the current instruction (the four numbers stored in memory starting at the address in the program counter) into the current instruction registers. For the sake of this description, assume the current instruction, symbolized A B C D, is 105 120 114 1012.
- Read the number from memory location A (location 105) into register 1.
- Read the number from memory location B (location 120) into register 2.
- Subtract the number in register 2 from the number in register 1, leaving the result in register 1.
- Put the result into memory location C (location 114).
- If the result is less than or equal to zero, put D (1012), not the number in location D, into the program counter. Otherwise add 4 to the program counter (the address of the next instruction).
- Repeat.
That’s all our CPU has to do! However, this leaves open the question of how numbers are input from the paper tape reader and output to the paper tape punch. To do this our computer will use a technique called memory mapped I/O. We will design the computer so that memory address 1 does not actually use the memory. Instead, a number read from location 1 will be the next number from the input tape. Similarly, a number written to memory address 2 will be punched onto the output tape. With devices as simple as paper tape readers and punches this is not at all difficult to build.
Simple as this computer is, it actually would be a practical computer. Given a reasonably large memory, we could write for it a compiler for any modern programming language, and then write and run significant programs. Of course, we probably would want to add more peripheral equipment: keyboard, monitor, external disk, etc, all of which could be built using memory mapped I/O.
– Rudd Canaday (ruddcanaday.com)
– Start of blog: My adventures in software
– Previous post: Machines I Have Known
– Next post: More Teaching Computing
Share this post: data-url=””
data-via=”ruddcanaday”
data-text=””
data-count=”none”>Tweet