Could be implemented as a graph where each node represents a situation, and each connection is an action.
If different actions are avaiable from the beginning, they could be tried out to see wich situation it would produce, building the graph piece by piece.
Then, the ai would just be a path finding algorithm.
That's called a Nondeterministic Finite Automata (NFA). These are not turing-complete by themselves, and are rather computationally "weak". They can be used to encode regular expressions, but certainly not thinking.
Anyhow, if you're interested in "thinking" in relational terms, using logic, you might want to loop up knowledge bases such as CyC (http://en.wikipedia.org/wiki/Cyc).
You may also want to look into automated theorem proving (http://en.wikipedia.org/wiki/Automated\_theorem\_proving), which is a form of "automated reasoning". It starts from a set of axiom (pre-existing knowledge), and attempts to assert the validity of a proof from what it knows. This can be used to prove things like mathematical identities, but it could also prove that a door can be opened using your hands provided that a door can be opened by turning its handle, and your hands can turn a door handle.
The limitations of such systems, however, are that in real life, you obviously don't know everything you need to know... You need to guess and try... And well, once a knowledge base contains a million items, it's very hard to prove things using brute force (very time consuming).
It's interesting to see that our brain, because of its biological (neural) nature, functions in a very variable way. We don't really rely on heuristics, hard logic. We often rely on "gut feelings", intuition and educated guesses. My personal guess is that if "thinking" computers are ever invented, they will have to imitate some of this. I would propose that its actually our innate capability to learn that makes us able to think in the way we do... And this is because of the way our brain was constructed. However, artificial neural networks, while they have proven efficient at "learning" simple tasks, have never really been used for artificial "reasoning" per-se.