| Kara Home Page | Turing Machine | Automata Theory |
In this version of the program Kara is used to simulate a Turing machine. A Turing machine is an abstract computer that was described by Alan Turing in 1936. A Turing machine simulates the behaviour of a computing machine (what later became known as a 'computer') by allowing an abstract machine to execute algorithms. The original intention was to show what problems could be solved algorithmically and what problems could not. The Turing machine was so conceptually similar to what became the modern computer that whatever can be executed on a Turing machine can be executed on an electronic computer and whatever cannot be executed on a Turing machine cannot be executed on an electronic computer; and vice versa: whatever can be executed on a computer can be executed on a Turing machine and whatever cannot be executed on a computer cannot be executed on a Turing machine.
Turing described his machine as follows: there is a paper tape of infinite length which is broken into squares, each of which can hold a character; there is a 'head' that moves along the tape (or the tape moves under it), reading the characters and taking action according to what it finds. The head can delete and write characters as well as reading them and the actions it performs are determined by its current 'state'. If the Turing machine is in state A and reads, say, a zero, then it may do something to the tape, move to the left or the right and enter a new state such as 'B'. If you are used to programming in a high level language then the slow, laborious steps of a Turing machine may strike you as tedious and scarcely worth the bother to follow. But if you put yourself back in the 1930s (no computers, no TV, few cars or telephones, coal and the steam engine still the dominant sources of energy) and steep yourself in the mathematical issues of the time then you may start to see the point. The computer did not come about by accident nor was it the inspired invention of a single genius; Alonzo Church, Stephen Kleene and Emil Post reached similar conclusions to Turing in the 1930s and their theoretical work laid the foundations for the development of the electronic computer a decade later.
The following exercises, taken from the Kara Exercises collection, give a flavour of how a Turing machine works. Turing's machine had a tape that was one character wide; Turing Kara employs a two-dimensional approach and allows the tape to be 2 or more characters wide, which makes the solutions much simpler and more compact as they fit more neatly into the Kara grid.
"Computing is normally done by writing certain symbols on paper. We may suppose this paper is divided into squares like a child’s arithmetic book. In elementary arithmetic the two-dimensional character of the paper is sometimes used. But such a use is always avoidable, and I think that it will be agreed that the two-dimensional character of paper is no essential of computation. I assume then that the computation is carried out on one-dimensional paper, i.e., on a tape divided into squares." (Alan Turing)
| NOT | OR | AND |
| XOR | n Zeroes, n Ones | Binary Addition |
| Palindromes | n Queens |
Look at further problems in the Turing Kara guide: