It’s often useful to think in terms of non-deterministic calculations. In some sense, as we’ll see, any non-deterministic computation can be turned into a deterministic one, but often the non-deterministic formulation is more natural. By non-deterministic I do not mean probabilistic. Probabilistic computation is also often useful, but is not really relevant to this module.
Deterministic algorithms have
a well defined initial state
a definite rule for what action to take in each state, possibly dependent on input, environment, etc.
a termination condition
(probably) a distinction between successful and unsuccessful termination
Non-deterministic algorithms have
one or more initial states
a set of possible actions to take in each state
a termination condition, probably with a distinction between successful and unsuccessful termination
Usually we’re interested in whether a non-deterministic algorithm can terminate successfully, not whether it happens to for a particular choice of actions, so unsuccessful terminations are generally to be regarded as unsuccessful only in a local sense. There may be other computational paths which lead to successful termination.
We usually illustrate the possible computational paths with a tree diagram. Unfortunately the terminology for trees is a mess. In keeping with the tree metaphor we have the “root” and “leaves”. For some reason trees are usually drawn growing downwards, so the “root” is at the top of the diagram. We also have “parents” and “children”, though. Every node has exactly one parent, except the root, which has none. Leaves are nodes with no children. Nodes which share the same parent are called “siblings”. Similarly we talk about “ancestors” and “descendents”, which mean what you would guess, based on the family tree metaphor, except that usually we consider each node to be one of its own ancestors and descendents.