During the 1930s-1950s many researchers debated over what was computable, and what wasn't. Many had argued over formal approaches to computability. In 1937, Alan Turing, a British mathematician who is now considered the father of computing and artificial intelligence sought to seek an answer to this dilemna. He constructed the theory of a Turing machine. His theorem (the Church-Turing thesis) states that
So what are Turing machines? Turing machines are abstract mathematical entities that are composed of a tape, a read-write head, and a finite-state machine. The head can either read or write symbols onto the tape, basically an input-output device. The head can change its position, by either moving left or right. The finite state machine is a memory/central processor that keeps track of which of finitely many states it is currently in. By knowing which state it is currently in, the finite state machine can determine which state to change to next, what symbol to write onto the tape, and which direction the head should move (left or right). (Note: the tape shall be assumed to be as large as is neccessary for the current computation it was assigned) As seen in the above figure, input onto the tape comprises of some finite alphabet (in this case it consists of 0, 1, blank). Thus, the Turing machine can do three possible things.
This machine is (by the Church-Turing thesis) capable of making any computation. This is not a provable theorem (it has yet to be disproved) nor a strictly formal definitive approach, the Church-Turing thesis is based on our intuition of what computation is about. By understanding what Turing machines can compute, we can also gain a better grasp of the potential of production systems for computing. If a production system can emulate a Turing machine, then we can say that it can make any computation by the Church-Turing thesis. Production systems are simulated by digital computers, thus if the statement that we just made was true, then today's digital computers can make any computation. To recap, a production system contains a control structure, a knowledge base and a global database. By then you can probably infer how such a case for emulation would be possible. In the Turing machine, the position of the head, the symbols written onto the tape, and their relative positions would be stored into the global database of the production system. (The global database shall be assumed to be as large as is neccessary to complete the computation). The production rules can be generalized as for every given state and symbol (from the Turing machine) then do one of the three possible actions (move head, change state, write symbol). For example, If reading symbol 1 and in state A write symbol 0 etc. As many production rules which would be needed would be produced. The control structure would then choose whichever rule would satisfy the current state of the system (applying this to the last example, if the system was reading symbol 1, and if it was in state A, then that production rule would be applied). With this in mind, we have proven that production systems can do what Turing machines do, including having the ability to compute anything that is computable. We can conclude that production systems are powerful computing tools. 
|
