# Simulation with Nondeterministic Machines

The nondeterministic machine

*B *= (*States _{B }*,

*Inputs*,

*Outputs*,

*possibleUpdates*,

_{B}*initialState*)

_{B }**simulates** another machine with the same input and output alphabets

A= (States,_{A }Inputs,Outputs,possibleUpdates,_{A}_{}initialState)_{A }

if there is a set *S *⊂* States _{A}*×

*States*such that

_{B}- (
*initialState*,_{A }*initialState*) ∈_{B }*S*

and

- If (
*s*,_{A }*s*) ∈_{B }*S*, then

for all*x*∈*Inputs*and

for all (*s'*,_{A}*y*) ∈_{A}*possibleUpdates*(_{A}*s*,_{A}*x*)

there exists (*s'*,_{B}*y*) ∈_{B}*possibleUpdates*(_{B}*s*,_{B }*x*) such that(

*s'*,_{A }*s'*) ∈_{B }*S*, and

*y*=_{B}*y*_{A}

*S *is called the **simulation relation **between *A *and *B*.

Unlike the simulation relation for deterministic
machines, this says that *B ***can*** *match *A*, not
that it **must*** *match *A*. Thus, this relation is not
symmetric. It is not necessarily true that *A* simulates *B*.

Note that a deterministic machine is a special case of nondeterministic machines
where *possibleUpdates* always returns a set with exactly one element.
Thus, the above definition applies to all state machines, deterministic or not.