Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
How about adding a link to the blog? –  Lazer Jul 28 '10 at 13:46
    
Actually, the blog is here, but I agree a link to the post itself would be useful! –  yatima2975 Jul 28 '10 at 14:32
add comment

2 Answers 2

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...8} instead of {1...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 <-- R_a + x_b R_c or R_i <-- R_a + x_b R_c + R_d (where x_1...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 <-- 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 NOT(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 <-- R_3 + R_1 to get the desired output.

If the circuit is AND(f_1,f_2), then life is a tad more complicated. By induction, we then execute the following 4 instructions

R_2 <-- R_2 + f_1 R_1
R_3 <-- R_3 + f_2 R_2
R_2 <-- R_2 + f_1 R_1
R_3 <-- R_3 + f_2 R_2

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. OR 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.


Edit to answer Casebash's questions:

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 AND, 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).

share|improve this answer
    
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
4  
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 at 21:57
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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