Who Says I Don't Do Anything Fun?
Today, I helped break the world record for largest coconut orchestra on Trafalgar square, to the tunes of over 4000 people and "Always Look on the Bright Side of Life". Then after dark most people stuck around to watch Monte Python and the Holy Grail together on a big screen on the square, and we all played our coconuts at the appropriate times in the movie.
And the nerdiness doesn't end there! Today in the climax lecture of complexity theory we proved that every NP problem is reducible in polynomial time to clause satisfiability by making a bijection between Turing machines and conjunctions of binary clauses! That is, we represented a computer with a binary function!
8 Comments:
ok, so how many notebooks of binary functions does it take to represent an iBook with 1GB of RAM and the latest versions of OS X and Photoshop installed??
That is an excellent question. The proof is for a Turing Machine, which a mac certainly is at some level. However, the Turing Machine's job is to take a word (a sequence of symbols in an abstract alphabet) and a certificate (another word written with the alphabet) and together decide whether or not the first word is in a particular language, which is a subset of all possible words, in time polynomial on the size of the word and certificate. I have a hard time imagining how photoshop can be said to do that, but we'll let that be for the sake of argument.
According to the proof we did in class, the literals are derived from the Turing Machine as follows:
T_isk will be mapped to true if the Turing Machine's tape contains s in space i at step k, and false otherwise
H_ik = true if the Turing Machine's head is at space i at step k and
Q_qk = true if the Turing Machine is in state q at step k.
The number if T's are consequently at most the number of spaces to execute the program times the number of steps times the number of symbols in the alphabet. The number of H's are the number of spaces times the number of steps, and the last is the number of states times the number of steps. The domain of the function is the sum of all of these.
Obviously, k depends on the particular problem. For the proof in class, we only needed that it was polynomially dependent on the size of x and y. Here, let's just say the computer runs for an hour. If it has the nicer of the two processors the Ibook ships with, it runs at 2GHz, which we'll call 7.2 trillion operations. Of course, for every computer operation, a Turing Machine must perform many more, but this is a guess anyway, so we'll ignore that.
S is easy. We have only 0 and 1.
The variable i can be limited by the amount of memory. Including the hard drive, we have 201GB of memory available. That's roughly 1.6 trillion binary digits, which we will take as the Turing Machine's tape size.
The number of states of the machine is a little harder to wrap my head around. Maybe someone who knows more than me about the details of how a processor works, but I see on Wikipedia that a normal 8086 processor has about 130 different assembly-level instructions, each of which I'll take as a separate state. I'd be interested if anyone had a better idea about how to estimate this. Besides, it doesn't have much effect on the final number.
So our domain is of size 7.2T * 1.6T * 2 + 7.2T * 1.6T + 7.2T * 130, which is obviously dominated by the trillion squared terms, and about 3.46E25. To define our function, it would suffice to list a binary digit, indicating true or false, for each of these literals. I think I could write about four thousand ones and zeros on a notebook page, so say eight thousand per piece of paper. This is 4.33E21 pieces of paper. The notebook I use has two hundred sheets, so that's about 2.17E19 notebooks. Because it's fun, let's write it out:
2,170,000,000,000,000,000,000 notebooks.
In summary: forget the notebooks, keep the ibook, and make sure abstract math stays abstract.
Um, it just occurred to me that I'm way off on the number of states. The turing machine transition function takes as its argument a symbol from the alphabet, but the ibook takes as its argument a sixty-four bit value (Sixty-four on new processors, right? I don't really know.). The simplest way for me to imagine this in a Turing Machine is branching at every bit into two states as you read all sixty-four. That would give over 2^64 states to represent a single assembly instruction...which is a whole lot of states. But this is obviously not what a computer actually does, and this estimate is really high. This needs more thought.
ok, so first, on turing machines in general -- see http://en.wikipedia.org/wiki/Turing_machine -- computer science people will refer to something as "turing complete" to show that a programming language really can do anything that any other programing language or "computer" in general can do. It's the standard as a basic theoretical definition of a "computer" -- which a quantum computer surpasses.
Note that the laptop follows a von Neumann architecture where the "state machine" (i.e. program) and the "tape" (i.e. input/output) are one and the same. And wiki pedia links get me to http://en.wikipedia.org/wiki/Random_access_stored_program_machine which ties it to the turing machine.
As for the states and all of that -- the states really amount to the "program" -- so your metric there would be the number of assembly instructions in Mac OS + Photoshop. -- which basically puts some limits on how much of the state of the disk is pertinent.
I suppose, if you want to be more general, you'd use the number of assembly instructions with the size of memory+disk to decide how many possible programs there could be.... which certainly is much larger than taking just Mac OS + Photoshop.
.... I hope that made some sense.
That's definitely better than what I had. The problem is that the proof in question represents a standard (one head, one tape) Turing machine as a binary function to prove that SAT is NP complete. Proving that a van Neumann computer is representable as a Turing machine still doesn't give you an idea about how many states you need to implement it. As an example, a simple command like "move 500 steps to the right on the tape" takes 500 states to implement in a standard Turing machine since it has no built-in counting or addressing mechanism. I don't see a way to get any sense of how many states a van Neumann machine would require, except that it would be a lot more than the size of a program.
I think maybe instead of thinking of the state machine as the program, it could be useful to see it as the processor's internal logic. A typical processor will proceed sequentially through memory, reading and executing instructions, keeping track of the current instruction in the Instruction Pointer register (sometimes called the Program Counter). Each instruction will modify the processor's state, possibly write to memory, and potentially cause execution to jump elsewhere in memory.
To model this via the Turing Machine, the tape contains both program and data, the position of the head is the instruction pointer, and the state machine uses the instruction at the head location to change state and move the head. The big limitation here is that Turing Machines only allow the head to be moved by one slot at a time, whereas pretty much every actual CPU allows arbitrary jumps. Seems like it might be easier to redo the proof for a modified Turing Machine that allows that than to figure out how to rework the architecture not to rely on arbitrary jumps.
Anyway, the PowerPC instruction set uses fixed-length, 32-bit instructions, and as far as I know, requires memory accesses to be made on 32-bit boundaries, so it's not much of a stretch to make the set of symbols the integers 0-2^32, giving the tape size as 1.6trillion/32 = 50 billion 32-bit words. The list of possible states is then an enumeration of possible states of the PPC processor.
The base PPC architecture specifies 32 32-bit general purpose registers, although one of them, r0, is hard-wired to always contain the value 0, so we will ignore it. It also has some number (let's say 16) 32-bit special purpose registers, a 64-bit accumulator, a 32-bit condition register, and 13 read-only 32-bit performance monitoring registers. That gives a total of 2^(32*31 + 32*16 + 32 + 64 + 32 * 13) = 2^2016 states. This is the base architecture -- I'm sure the model in the iBook has more.
This gives i=0..50 billion, s=0..2^32, k=0..7.2 trillion (as before), and q=0..2^2016
It seems to me that the Q term then clearly dominates with 2^2016 * 7.2 trillion literals. I think that comes out to about 5.2e213. At 1.6 million symbols per notebook, that's 3.25e207 notebooks. Ouch.
I see that the estimate for number of atoms in the universe is 1e81 at the high end. I'm not sure if this implies that my estimate is way off or that this representation is more astronomically impractical than I have the imagination to contemplate.
PS: I am curious as to what sort of impact your concert had on the availability of coconuts in greater London.
PPS: The computation for a MacBook would be a bit harder, as Intel processors support variable-sized instructions from 8 to 40 (or more?) bits in length, memory accesses in 1, 2, and 4 byte lengths, and unaligned memory accesses -- meaning that the CPU can read from or write to memory in an arbitrary chunk of 1,2, or 4 consecutive bytes. Many architectures (including, I believe PPC) limit memory accesses to 32-bit chunks where the address of the first byte must be 0 modulo 4.
Post a Comment
Links to this post:
Create a Link
<< Home