Members of the second machine class do not provide realistic representations of the complexity costs of concretely embodied computation

On the other hand, if \(x \not\in X\), then all of \(N\)’s computations from \(C_0(x)\) are required to lead to rejecting states. Non-deterministic machines are sometimes described as making undetermined ‘choices’ among different possible successor configurations at various points during their computation. But what the foregoing definitions actually describe is a tree \(\mathcal{T}^N_{C_0}\) of all possible computation sequences starting from a given configuration \(C_0\) for a deterministic mac