In the Immerman-Szelepcsenyi Theorem, two algorithms are specified that use non-determinisim. There is a rather lengthy algorithm using "inductive counting", which determines the number of reachable configurations for a given non-deterministic turing machine. The algorithm looks like this:

Let m_{i+1}=0
For all configurations C
  Let b=0, r=0
  For all configurations D
    Guess a path from I to D in at most i steps
    If found
      Let r=r+1
      If D=C or D goes to C in 1 step
        Let b=1
  If r<m_i halt and reject
  Let m_{i+1}=m_{i+1}+b

I is the starting configuration.

m_i is the number of configurations reachable from the starting configuration in i steps. This algorithm only calculates the "next step", i.e. m_i+1 from m_i. This seems pretty reasonable, but since we have nondeterminisim, why don't we just write:

  Let m_i = 0
  For all configurations C
    Guess a path from I to C in at most i steps
    If found
      m_i = m_i + 1

What is wrong with this algorithm?

• I am using nondeterminism to guess a path from I to C, and I verify reachability
• I am iterating through the list of ALL configurations, so I am sure to not miss any configuration
• I respect space bounds
• I can generate a certificate (the list of reachable configs)

I believe I have a misunderstanding of the "power" of non-determinisim, but I can't figure out where to look next. I am stuck on this for quite a while and I would really appreciate any help.