patternMinor
Halting problem with Proof of The Immerman-Szelepcenyi Theorem (knowledge of the theorem might not be necessary to clear my doubt)
Viewed 0 times
problemmighttheszelepcenyiknowledgenecessarywithdoubthaltingimmerman
Problem
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?
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?
Solution
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
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).
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).
Context
StackExchange Computer Science Q#77773, answer score: 9
Revisions (0)
No revisions yet.