Introduction : To better understand what it means "to compute" a number of theoretical models for computing have been developed. These models are simple to understand yet powerful enough so that anything done by a computer can be done by one of these models - although not as quickly - but speed is not an issue here, understanding is.
Any model ought to be able to implement an algorithm. Recall that an algorithm is "an ordered sequence of unambiguous and well-defined instructions that performs some task and halts in a finite time". An "unambiguous and well-define instruction" can be understood and executed by a "computing agent". This "computing agent" will be the model for our computer.
A "computing agent" ought to be able to do four things
The Turing Machine - the Turing machine is the primary model for a computing agent. It consists of
Example : We can visualize a Turing machine below as a two way tape all of whose cells are blank except for the four contiguous cells containing the symbols '0110'. The read/write head is positioned "on" the first (left -most) non-blank cell containing a '0'. The machine is "in" (internal) state 'A'.
---+---+---+---+---+---+---+---+---+---+---+---+---
|
| | | 0 | 1 | 1 | 0 | | |
| |
---+---+---+---+---+---+---+---+---+---+---+---+---
^
+-+-+
| A | <- internal state
+---+
The operation of a Turing machine is simple. The current (internal) state and the current symbol read by the read/write head, determine the next (internal) state, the next symbol which overwrite the current symbol and whether the read/write head moves left or right. Turing machine instructions can be represented as quintuples
(current state, current symbol, next symbol, next state, move left or right)
For example the quintuple (A, 0, 1, B, R) which cause the above Turing machine configuration to change to
---+---+---+---+---+---+---+---+---+---+---+---+---
|
| | | 1 | 1 | 1 | 0 | | |
| |
---+---+---+---+---+---+---+---+---+---+---+---+---
^
+-+-+
| B | <- internal state
+---+
where the current state = "A" and current symbol = "0" causes the Turing machine to overwrite the "0" with a "1", change the internal state to "B" and move the read/write head to the Right.
An Example Turing Machine Program : The following set of quintuples will increment any binary number. The Turing Machine starts in state "A" with the read/write head on the left-most non-blank symbol (0 or 1). When in state 'A' the R/W head moves to the right until it finds the right end of the string (a blank) where is changes the state to 'B'. State 'B' is the increment state. While in state 'B' the Turing Machine searches for a 0 to change to a 1 while changing all1's to 0 (carry).When it finds the 0 it changes it to a 1 and goes to state 'C'. If the Turing Machine encounters the left hand side of the string first (the string was all 1's) it makes the blank a 1 (carry into a new position) and goes to state 'D'. State 'C' is the clean up state; while in state 'C' the Turing Machines moves the R/W head left looking for the left end of the string (a blank). When it finds the end, it goes to state 'D', the final state. Since no quintuple begins with 'D', the Turing Machine halts. With Turing Machines execution continues as long as there is some quintuple that begins with the current state and current current symbol under the R/W head. Execution halts when the current state, current symbol for the Turing machine does not match the first two components of some quintuple.
(A, 0, 0, A, R) move to the right
(A, 1, 1, A, R) move to the right
(A, , , B, L) when you find a blank cell
(right end)change to state B and move left
(B, 0, 1, C, L) when you find a 0 convert to
1 and go to state C
(B, 1, 0, B, L) when you find a 1 convert to
0 but stay in state B
(B, , 1, D, R) when you find a blank (left
end) change it to 1 and go to state D
(C, 0, 0, C, L) move to the left
(C, 1, 1, C, L) move to the left
(C, , , D, R) when you encounter
a blank move right and go to state D
Step 1 : Start
---+---+---+---+---+---+---+---+---+---+---+---+---
|
| | | 1 | 0 | 0 | 1 | | |
| |
---+---+---+---+---+---+---+---+---+---+---+---+---
^
+-+-+
| A | <- internal state
+---+
Step 2 - 5 : Move Right
---+---+---+---+---+---+---+---+---+---+---+---+---
|
| | | 1 | 0 | 0 | 1 | | |
| |
---+---+---+---+---+---+---+---+---+---+---+---+---
^
+-+-+
| A | <- internal state
+---+
Step 6 : Found Right End - Go to State B
---+---+---+---+---+---+---+---+---+---+---+---+---
|
| | | 1 | 0 | 0 | 1 | | |
| |
---+---+---+---+---+---+---+---+---+---+---+---+---
^
+-+-+
| B | <- internal state
+---+
Step 7 : Convert 1 to a 0 and move Left
---+---+---+---+---+---+---+---+---+---+---+---+---
|
| | | 1 | 0 | 0 | 0 | | |
| |
---+---+---+---+---+---+---+---+---+---+---+---+---
^
+-+-+
| B | <- internal state
+---+
Step 8 : Found a 0 - convert to 1; Go to state C
---+---+---+---+---+---+---+---+---+---+---+---+---
|
| | | 1 | 0 | 1 | 0 | | |
| |
---+---+---+---+---+---+---+---+---+---+---+---+---
^
+-+-+
| C | <- internal state
+---+
Step 9 - 10: Move Left
---+---+---+---+---+---+---+---+---+---+---+---+---
|
| | | 1 | 0 | 1 | 0 | | |
| |
---+---+---+---+---+---+---+---+---+---+---+---+---
^
+-+-+
| C | <- internal state
+---+
Step 11 : Found Left End of String - Go to State D
---+---+---+---+---+---+---+---+---+---+---+---+---
|
| | | 1 | 0 | 1 | 0 | | |
| |
---+---+---+---+---+---+---+---+---+---+---+---+---
^
+-+-+
| D | <- internal state
+---+
At this point the calculation halts since no quintuple begins with state "D". Observe that the binary number 1001 is incremented to 1010.
Church Turing Thesis :
Essentially anything a Turing machine can do can be done by a modern digital computer and anything that a modern digital computer can do can be done by a Turing machine. A Turing machine defines what it means "to mechanically compute". It should be pointed out that this is a thesis; it cannot be logically proved from more primitive laws since we know of no other way to define mechanical computation. But since every other model of mechanical computation proposed has been shown to be equivalent to a Turing machine and since no one has found an task that has an algorithmic solution which cannot be solved using a Turing machine, we generally accept the Church-Turing thesis.
Finite State Machines (FSM) and State Transition Diagrams : Another model for computation is the Finite State Machine. A FSM uses a finite input tape exactly as long as its input (in the example below, the input is 11 symbols long). It reads the input left to right so unlike a Turing machine it cannot back up. Thus a FSM is a "weaker" model of computation. The computation ends when it runs out of input (tape). Thus only quadruples (current state, current symbol, next symbol, next state) are used to "program" a FSM.
+---+---+---+---+---+---+---+---+---+---+---+
| 0 | 1 | 1 | 0 | 1 | 1
| 0 | 0 | 1 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+---+---+
^
+-+-+
| A | <- internal state
+---+
For example the following FSM program counts the number of 1's on the tape modulo 3
(A, 0, 0, A)
(A, 1, 1, B)
(B, 0, 1, B)
(B, 1, 2, C)
(C, 0, 2, C)
(C, 1, 0, A)
After executing the above FSM program, the last synbol on the tape is a 2 and the final state is "C" - which indicates the number of 1's on the tape modulo 3 is 2 (there are 5 one's)..
+---+---+---+---+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 2 | 0 | 1
| 1 | 1 | 2 | 2 | 2 |
+---+---+---+---+---+---+---+---+---+---+---+
^
+-+-+
| C | <- internal state
+---+
State-Transition Diagrams : The action of a FSM is more easily understood using a State-Transition diagram. States are represented by circles and transitions by labeled arrows (symbol read/symbol written) between states. For example the quadruple (A,1,1,B) is the arrow labeled 1/1 between states A and B. Starting in state A and "reading" the input string 01101100100, the
FSM follows the transitions 0/0, 1/1, 1/2 etc to enter the states A, B, C, C, A, B, B, B, C, C, C thus ending in state C with 2 being the last output character.
Finite State Acceptors & State Transition Diagrams : A Finite State Acceptor is a FSM which does not generate output. Instead it accepts the input if the final state is a special "accept" state. The State-Transition diagram for an FSA is simpler since transitions are only labeled with the "symbol read" character. The special accept state is indicated using a double circle for the state - see below.
State Transition diagrams for Finite State Acceptors (FSA) can be used
to model algorithms that "recognize" strings that satisfy certain rules.
For example, an identifer in C++ is defined as a string of characters beginning
with a letter and followed by zero or more letters, digits or underscore
('_') characters. Typically leading blanks are ignored by embedded blanks
ro trailing blanks are not permitted. Consider the State-Transition diagram
below. Any legal identifier will "drive" the State-Transition into the Ok
state which is the "accept state" (denoted by the double rings); illegal string
will end up in the Start or Error states and will not be accepted.
Coding C++ functions from State-Transition Diagrams : State-Transition diagrams are easily coded using enum types and switch statements. States become the values of an enum type (e.g. enum StateType {start, ok, error}). Transitions are implemented using a switch statement whose cases are the states and whose actions are if else if ... else statements which advance the current state to the next state depending on the current character. The switch statement is enbedded in a for loop which examines each character in the input string. At the end, after the last character has been scanned, if the value of state is an accept state, a value of true is returned.
bool IsIdentifier(char str[])
// Returns true if str contains a legal C++ identifier
{
enum StateType {start, ok, error};
Statetype state = start;
// initial state
char ch;
for (int i = 0; i < strlen(str); i++)
// for each character in the string
{
ch = str[i];
switch (state)
{
case start : if (ch == ' ')
// if blank
state = start;
else if ((ch >= 'A') && (ch <= 'Z') || //
if letter
(ch >= 'a') && (ch <= 'z'))
state = ok;
else
state = error; // else
break;
case ok : if ((ch >= 'A') && (ch <= 'Z') ||
// if letter, digit or '_'
(ch >= 'a') && (ch <= 'z') ||
(ch >= '0') && (ch <= '9') ||
(ch == '_'))
state = ok;
else
state = error;
break;
case error : ;
default :
}
if (state == ok)
// accept state is Ok
return true;
else
return false;
}
In general a State-Transition diagram can be easily generated to identify most classes of substrings. (Note: Such classes are called regular.) Once the State-Transition diagram is written down, it can be easily implemented as a boolean valued C++ function which takes any string and return true or false depending on whether the final value of state is an "accept" state or not.