Graphs may also be used in knowledge based systems. The idea is that you insert a lot of knowledge in the form of statements (facts) and that you let the system derive new facts on what is given. So, for example, if you say that a Chicago is a city, and that in cities there live people, then it means that people live in Chicago, so any questions relating to "do people live in Chicago?" can be answered. When you approach the boundaries of the scope of the knowledge, the performance degrades considerably.
So what exactly is reasoning? If we look back at the adventure game of Zork, you could consider the flow of an adventure game as a finite state machine:
In adventure games, the players are reasoners and the pre-defined stories are basically FSM's, created by programmers or story writers. Another way of describing the objective of an adventure game is to find the sequence of commands that leads to a successful finish state. Some game commands don't change the game state, but instead inspect the value of some property or attribute (commands like look, listen, smell, etc.) and return a pre-configured string. Succesful manipulative commands always change the game state, but not necessarily in a way that is useful to get to the end of the game. For example, you could open / close a milk bottle in the fridge repeatedly without having any effect towards reaching the objective. For brevity, any commands that change the world state to something non useful are not visualized in the above graph.
Reasoning in the above graph is really easy, because you simply have to follow the graph from start->finish or vice versa and you solved the problem. It's a single path here. End of complexity?! . Actually, real problems are much more complicated than that, because they have different states that are modified at different moments. To put all the information into a single graph would create one that is too complicated to handle. A state machine can and should handle only one specific memory location (the integer describing the current state) and then the state machine should be accompanied with rules on how that state may be changed. The following graph shows three different state machines, where some transitions contain particular restrictions on when the transition can be executed successfully and when it can't.
We've just made a distinction per state machine based on the observed value of the memory location. So, if FSM_1 governs the locations, then each location is described by a single number. If FSM_2 governs having the key or not, then 6 means not having the key and 7 means having the key.
Reasoning has just become a bit harder in this case. Instead of just finding the reverse path, any reasoning program must start with a potential path that may be possible and then for each transition find out if there are constraints along that transition that might prohibit that change. Further complications arise when a given constraint is based on an event very early in the game, so following a path that eventually fails is very costly. This means that the heuristics for evaluating if the value may ever change in the desired direction becomes of great importance.
The above also shows how software is written. The software specification comes up with a set of rules, which are essentially dynamic generators for several state diagrams. The programmer adds his own variables to that. The programmer then glues various state diagrams together through "if" statements, making the diagrams depend on one another. Then add in a couple of state modifiers (which move one machine from state A -> B) and the party is complete.
Reasoning in this model means generating a deconstruction of the program or specification and inverting it. So a computer that can reason about programs should be able to look at the debug info of a computer program and make statements about how to achieve goal states. A bit like:
- For your program to return with code 2, the following paths are possible: "x,y,z,...".
- For path 'x' to be chosen, variable i must be equal to 3, j must contain "bird" and k must be less than 5.
- For path 'y' to be successful, .....
A genuinely new look at computer-based reasoning could research how conditional jumps are used and whether they are useful for a basis of reasoning. Can they be used to model the complexities of actual reasoning itself? The idea is that without looking at the contents of fields and understanding the semantics, as long as we understand the structure of a state machine (the way how states change), we may be able to reason with it. After all, a name to refer to something is just a pointer to some memory about the properties and classification of such a thing. Just like a computer may have a pointer to a piece of memory that has other pointers to other capabilities.
But what if we only have a start and an end goal and a very large ontology? Then we don't have a program to analyze, only fragments of diagrams that are not connected to one another. The added complexity here is that we should use the rules within the ontology to find ways to connect ontologies and subdiagrams together such that it still makes sense.
Is this different from other logic languages like prolog? Hmmm.. I don't know yet. A good test would be to see if there are different consequences of using such a model. Most programming languages require tests to be written for certain things. And it gets very repetitive to insert lots of facts about the things, plus that an ontology depends a lot on the proper classifications. It's probably related to a different look on things, like complete separation of terms (nouns and verbs) or something.