Encoding non-deterministic computations

How far can the ideas of the previous section be pushed?

Hopefully it’s clear that we could do the same thing with any grammar of the type we’ve been considering so far. With an encoding of this type the set of encodings of members of the language will always be an arithmetic set. In fact we could allow more complicated grammars, but won’t pursue this idea for now.

Parsing can, as discussed earlier, be considered as an example of a non-deterministic computation. From this point of view the procedure we’ve just employed is

• Develop a language which allows us to describe the possible states of the computation.
• Extend this language to encompass possible computational paths.
• Apply an encoding of the type described above to the extended language.
• Create an expression to check whether the initial state is one of the allowed ones.
• Create an expression to determine whether the final state is of the type needed for successful termination of the computation.
• Create an expression to check whether the final state is one is the desired one.
• Create an expression to check whether the each state is reachable from the previous one via one of the allowed actions in that state.
• Combine the above expressions to get an expression which determines, for any state, whether there is a possible computational path which terminates successfully in this state.
• Conclude that the set of all possible final states is an arithmetic set.

This is all fairly straightforward, except for the last step, which will only work for certain types of actions. As we’ve seen though, the fact that concatenation is constructively arithmetic allows us to perform fairly sophisticated pattern matching operations, so in practice the class of sets we can prove are arithmetic by this technique is quite large.

If you compare this general procedure to the special case of the balanced parentheses example you may notice one way in which it doesn’t quite fit. There I described checking that each element of the sequence is obtainable by expanding the token ok in some previous list. The recipe given above would require it to expand a token from the immediately previous list. Changing it to conform to the recipe above is possible. If there’s a parsing of the more lenient type considered earlier than there’s one of this more restricted type as well. The possibility to use past states as well as the current one in determining the next state is useful though. In this case it would allow us to write a backtracking parser, i.e. one which can explore branches of the state tree tentatively without firmly committing to them. We don’t even really need to limit ourselves to examining just one past state in determining what we’re allowed to do next. The freedom to make use of more than one previous state would be useful, for example, in showing that the Fibonacci numbers are an arithmetic set, since each number in the sequence depends on two previous ones. This freedom will soon be useful in other contexts. There’s no problem with allowing it. Our method uses concatenation to identify previous states, and that’s just as easy to do, and in fact slightly easier, if we allow our rules to consider all earlier states and not just the preceding one.