Ramblings |
A Blog By Aidan Evans |
Ramblings |
A Blog By Aidan Evans |
When most computer scientists hear "Cook's 1971 paper", they think about NP-completeness and of his paper proving the Cook half of the Cook-Levin theorem. That same year, however, he also published a paper on the relationship between time and space on a Turing machine when a pushdown tape is introduced. Like how adding a pushdown tape to finite automata increases the power of the machine from recognizing regular languages to context-free languages, adding a pushdown tape to a Turing machine also changes things up.
Take a Turing machine with an input tape and a work tape. Now say we also give the machine a pushdown tape like PDAs have. Cook's 1971 paper calls this machine an Auxiliary Pushdown Machine (PDM) and until I stumbled upon the original paper, I had not seen this machine before. In fact, to my knowledge, the only textbook or teaching/reference material to ever include the results of this work is the 1979 edition of Hopcroft and Ullman --- just the 1979 edition. Not the earlier 1969 precurser or any of the later editions include it. Now, while a Turing machine with a pushdown tape doesn't sound very interesting at first, there turns out to be some very interesting properties of PDMs and this is what Cook shows. In this post, I will focus on two main results of the paper.
Say we bound the work tape of a PDM to use only \(S(n)\) space but we leave the pushdown tape unbounded. Define the class of problems decidable when restricted to only \(S(n)\)-space on the worktape as \( PDM\text{-}SPACE(S(n)) \). We will denote the class of problems for time-bounded deterministic Turing machines using the standard notation of \(DTIME(\cdot)\). Here's the interesting part: Cook proved the following relationship between space-bounded computation on a PDM and time-bounded computation on a Turing machine:\[ PDM\text{-}SPACE(S(n)) = DTIME(2^{O(S(n))}) \] It follows that \[ PDM\text{-}SPACE(\log(n)) = DTIME(2^{O(\log(n))}) = DTIME(n^{O(1)}) = P \]
We, therefore, have that log-space computation on a PDM is equivalent to polynomial-time computation on a Turing machine. That's the first cool part about PDMs. There's another.
Let \(PDM\text{-}NSPACE(\cdot)\) be the non-deterministic counterpart to \(PDM\text{-}SPACE(\cdot)\). Cook also proved that \[ PDM\text{-}NSPACE(S(n)) = PDM\text{-}SPACE(S(n)) \] Therefore, all together we have, \[ PDM\text{-}SPACE(S(n)) = PDM\text{-}NSPACE(S(n)) = DTIME(2^{O(S(n))}) \]
Thus, we can rephrase the L vs P (NL vs P) problem as follows: "Does adding a pushdown tape to a log-space bounded (non-deterministic) Turing machine increase the computational power? I.e., can we solve more problems?". A very interesting reformulation if you ask me!
-- Aidan
| [1] | Stephen A Cook. Characterizations of pushdown machines in terms of time-bounded computers. Journal of the ACM (JACM), 18(1):4--18, 1971. |
