Tuesday, June 25, 2013

Note: Reducing nondeterminism in Machines to branching deterministic processes

"The key to simulating an NFA on a deterministic computer is to find a way to explore all possible executions of the machine. This brute-force approach eliminates the spooky foresight that would be required to simulate only one possible execution by somehow making all the right decisions along the way. When an NFA reads a character, there are only ever a finite number of possibilities for what it can do next, so we can simulate the nondeterminism by somehow trying all of them and seeing whether any of them ultimately allows it to reach an accept state." (Stuart, 2013)
 In my (admittedly shallow) foray into theoretical computer science I've become interested in the way in which nondeterministic machines (and, here, a machine designates anything with a particular formal structure), such as the nondeterministic pushdown automata, differ from purely deterministic machines / versions of themselves.

Daniel I.A. Cohen in his fun (but sometimes too relaxed) "Introduction to computer theory" points out in his discussion of Transition Graphs (the first nondeterministic machine he presents) that with the introduction of nondeterminism we have "changed something more fundamental than just the way the edges are labeled", namely, a nondeterministic machine "makes us exercise some choice in its running" (Cohen, 1997).

Cohen's talk about choice is misleading, because it suggests, as the Stuart quote above notes, that in order for our machine to do its work, it (or the person "running it") somehow has to know precisely how it should read/interpret/act on the input we've provided for. This wont fly because what we're interested in is really how we can do this mechanically. There's no room for human interpretation/choice/whatever. How do we get rid of these notions?

There are two steps.
The first is to note that nondeterminism in these machines doesn't require that the machines themselves control which paths they take when they get to a fork in the road. Cohen's loose talk suggested it was "us" that was determining the pathway through the machine - but this was really just shorthand for saying that in order for a particular machine to be seen as accepting some input there should be at least one possible path through the machine
The second step is to note that we can mechanize this process of checking all possible paths by running our input string through our machine and, at each point where the we are required to "choose" a possible path through the machine, we simply choose all of the paths. Each nondeterministic action in our machine can then be seen as a deterministic step that creates two or more branches (or copies of the machine) that will evolve according to the choice that was made at the point of branching. If any of these new branches lead to a nondeterministic state, the execution branches again, and so on until either (1) the string is rejected by all the branches, or (2) at least one of the branches accept the string.
This is a nice strategy because it reduces these "spooky" nondeterministic choice points into an entirely deterministic process.
The next step for this investigation is to find out whether this kind of branching process will suffice for mechanizing at least a large subset of nondeterministic (finite) machines. Further, I need to clear up my terminology etc. and start defining the machines more precisely.

*EDIT: note that in order to show that a nondeterministic machine accepts a particular string, one has to use a meta-process. In some cases this meta-process/machine can be made of the same "stuff" - one can reduce a Nondeterministic FA to a simple deterministic FA - although I don't believe this is the case for all classes of machine*


Cohen, D. 1997. Introduction to Computer Theory (2nd edition). John Wiley & Sons inc.
Stuart, T. 2013. Understanding Computation. O' Reilly Media inc.