# Ramblings

A Blog By Aidan Evans

## The Power of a Pushdown Tape

#### Post 5 | February 13, 2023

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.

### Introduction

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.

### PDM Space versus TM Time

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.

### Deterministic versus Non-Deterministic PDMs

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

  Stephen A Cook. Characterizations of pushdown machines in terms of time-bounded computers. Journal of the ACM (JACM), 18(1):4--18, 1971.