Computation with a memory wiped computer

Here is another result from Scott Aaronson's blog:

If every second or so your computer’s memory were wiped completely clean, except for the input data; the clock; a static, unchanging program; and a counter that could only be set to 1, 2, 3, 4, or 5, it would still be possible (given enough time) to carry out an arbitrarily long computation — just as if the memory weren’t being wiped clean each second. This is almost certainly not true if the counter could only be set to 1, 2, 3, or 4. The reason 5 is special here is pretty much the same reason it’s special in Galois’ proof of the unsolvability of the quintic equation.

Does anyone have idea of how to show this?

• Actually, the blog is here, but I agree a link to the post itself would be useful! – yatima2975 Jul 28 '10 at 14:32

1) Why does a small number of states suffice?

Regardless of whether the constant is 5 or 500, its still very surprising. Thankfully, it's fairly straightforward to prove this if you allow the counter to be $\{1, \ldots, 8\}$ instead of $\{1, \ldots, 5\}$. [This proof is by Ben-Or and Cleve.]. Start by representing the computation as a circuit, and ignore the whole wiping-clean thing.

Define a register machine as follows: It has 3 registers $(R_1,R_2,R_3)$, each of which holds a single bit. At each step, the program performs some computation on the registers of the form $R_i \gets R_a + x_b R_c$ or $R_i \gets R_a + x_b R_c + R_d$ (where $x_1\ \ldots x_n$ is the input).

Initially, set $(R_1,R_2,R_3) = (1,0,0)$. The machine should end in the state $R_3 + f R_1$. We'll simulate the circuit using a register machine.

We now proceed by induction on the depth of the circuit. If the circuit has depth 0, then we just copy the appropriate bit: $R_3 \gets R_3 + x_i R_1$.

For the induction, we have 3 cases, according to whether the final gate is NOT, AND, or OR.

Suppose that the circuit is $\neg f$. By induction, we can compute $f$, yielding the state $(R_1,R_2,R_3 + f R_1)$. We can therefore perform the instruction $R_3 \gets R_3 + R_1$ to get the desired output.

If the circuit is $f_1 \wedge f_2$, then life is a tad more complicated. By induction, we then execute the following 4 instructions:

\begin{align*} R_2 &\gets R_2 + f_1 R_1 \\ R_3 &\gets R_3 + f_2 R_2 \\ R_2 &\gets R_2 + f_1 R_1 \\ R_3 &\gets R_3 + f_2 R_2 \end{align*}

Assuming I haven't made any typos, we are left with the state $(R_1,R_2,R_3+f_1f_2R_1)$, as desired. $f_1 \vee f_2$ works similarly.

QED.

Take a moment to process what just happened. It's a slick proof that you have to read 2 or 3 times before it begins to sink in. What we've shown is that we can simulate a circuit by applying a fixed program that stores only 3 bits of information at any time.

To convert this into Aaronson's version, we encode the three registers into the counter (that's why we needed the extra 3 spaces). The simple program uses the input and the clock to determine how far we've made it through the computation and then applies the appropriate change to the counter.

2) But what's the deal with 5?

To get from 8 states down to 5, you use a similar argument, but are much more careful about exactly how much information needs to be propagated between stages and how it can be encoded. A formal proof requires lots of advanced group theory.

1) Correct. Any computation can be expressed as a circuit composed solely of "NOT", binary-"AND", and binary-"OR" gates.

2) The notation $f R_1$ means (boolean) multiplication.

3) The program for computing $f$ should take input $(R_1,R_2,R_3)$ to $(R_1,R_2,R_3 + f R_1)$. We insist that the first two registers are unchanged since we use those as temporary storage in the induction. For example, when computing $f_1 \wedge f_2$, we compute the first branch and store the result in $R_2$ while computing the second branch.

4) The single bit of output is the final value of $R_3$. Since we started with $(1,0,0)$, we end with $(1,0,f)$.

• 1. So we only need AND/OR/NOT to simulate a computer? 2. Does f R_1 mean function application or multiplication? 3. What do you mean by: "The machine should end in the state R_3 + f R_1"? Are you talking about the third counter? If so, it is unclear what that means. It can't mean the end state of R_3, as that would be a recursive definition. Also, do we care about the final state of R_1 and R_2? 4. Doesn't our computation only produce a single bit as output? – Casebash Jul 29 '10 at 13:36
• Good questions. I've edited the post to answer them. Sorry for the really long delay in answering! – Jeremy Hurwitz Dec 6 '10 at 23:24
• I think "lots of advanced group theory" is an exaggeration. You need to know how to multiply permutations in $S_5$. – Yuval Filmus Dec 7 '10 at 2:31
• I don't see any assignments to R_1 whatsoever. Why can't we just throw that register out and replace all references to it with 1? – Pastafarianist Jul 12 '14 at 21:57
• @Pastafarianist, that's an excellent question. It took me longer than I'd like to admit to figure it out. The short answer is that it's hidden in the recursion, specifically AND(f1, AND(f2, f3)). To compute R3<--R3+f1f2R1, we need the same value to be in R1 in lines 1 and 3. So the intermediate results from lines 1 and 2 must be stored in R2 and R3. Now look at the recursion in line 2, and suppose f2=AND(g1,g2). When computing f2, R2 is now the register that must remain fixed, so the intermediate results for g1 and g2 are stored in R1 and R3. – Jeremy Hurwitz Aug 3 '14 at 1:14

As Scott himself states in comments section of the post in question (comment #9):

(4) Width-5 branching programs can compute NC1 (Barrington 1986); corollary pointed out by Ogihara 1994 that width-5 bottleneck Turing machines can compute PSPACE

Unfortunately, I don't have any ideas how this is proved.

• The proof is pretty easy (about 1 page), have a look at Barrington's original paper (available from his website). What's special about $5$ is that $S_5$ is not solvable. – Yuval Filmus Dec 7 '10 at 0:14
• See the paper people.cs.umass.edu/~barrington/publications/bwbp.pdf, on bottom of page 159, he is talking about solvable groups. – Watson Nov 30 '18 at 8:52