4
$\begingroup$

So, I was reading this pdf on complexity theory. On page 18 pf pdf (Page 12 of book) The Immerman-Szelepcsenyi Theorem is mentioned with proof. The following lines are from the book :

The idea is to cycle through all possible configurations $\sigma$ of $M$, for each one checking whether it is a final configuration that is reachable from the initial configuration by a computation of $M$. In case no such accepting configuration is found we know $x\notin A$ so we let $\overline M$ accept $x$.

My question here that the machine $M$ may not halt for a string $x\notin A$. Then the logic of "cycle through all possible configurations" won't make any sense. What am I missing here?

On a side note is this book too high level for me? (I am graduate in Computer Science) Getting stuck at page 12 is not a good sign right?

$\endgroup$
2
  • $\begingroup$ Sipser's book is probably best to start with. (And one of the best written math texts I've used.) $\endgroup$ – djechlin Jul 10 '17 at 22:38
  • $\begingroup$ @djechlin Thanks...It really is great! $\endgroup$ – User Not Found Jul 11 '17 at 2:39
9
$\begingroup$

As the proof (sketch) itself notes:

Note that on a given input $x$ of length $n$ there are $2^{f(n)}$ possible configurations.

This means there is only a finite space of configurations for a machine that operates in less than $f(n)$ amount of space!

Intuitively, if you have an array [0,1,0,...,] of length $n$, then all possible combinations of configurations of that array is $2^n$, and so a machine which could only modify an array of bits of size at most $n$ will either halt in that time, or end up in a loop with exactly the same state as previously, and this is easy to decide.

If you allow arbitrary amounts of space then as you note, it is undecidable whether or not a state is reachable or not.


It's hard to say whether a given piece of work is "too high level" for someone or not. To paraphrase Euclid, there is no "royal road" to theoretical computer science, so you should expect to have at least some difficulty working through technical material.

As Paul Halmos suggests: "Don't just read it, fight it!". This suggests that difficulty in mathematical reading is rather widespread (I certainly experience it sharply as well).

$\endgroup$
2
  • $\begingroup$ Re "too high level", I'd also recommend the guidance suggested by Paul Halmos' remark in the preface of his 1950 book, Measure Theory. To wit, "Readers should not be discouraged if they find that they do not have the prerequisites to read the prerequisites.":) (P.S. Did you ever meet or hear of Joel Storch, and old friend of mine who also used to work at Draper Labs?) $\endgroup$ – John Forkosh Jul 12 '17 at 0:58
  • $\begingroup$ @JohnForkosh that's a good quote! I wonder how effective telling people to not be discouraged is though (probably as effective as "don't be upset!"). Sadly, I have not met or heard of Joel Storch, though Draper Labs is a really big place and I tend to meet only a few people at a time. $\endgroup$ – cody Jul 12 '17 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.