4 ms·

Here's a Feynman mystery that I've asked about for years: http://longnow.org/essays/richard-feynman-connection-machine/ http://longnow.org/essays/richard-feynm

Here's a Feynman mystery that I've asked about for years: http://longnow.org/essays/richard-feynman-connection-machine/ http://longnow.org/essays/richard-feynman-connection-machine... By the end of that summer of 1983, Richard had completed his analysis of the behavior of the router, and much to our surprise and amusement, he presented his answer in the form of a set of partial differential equations. To a physicist this may seem natural, but to a computer designer, treating a set of boolean circuits as a continuous, differentiable system is a bit strange. Feynman's router equations were in terms of variables representing continuous quantities such as "the average number of 1 bits in a message address." I was much more accustomed to seeing analysis in terms of inductive proof and case analysis than taking the derivative of "the number of 1's" with respect to time. Our discrete analysis said we needed seven buffers per chip; Feynman's equations suggested that we only needed five. We decided to play it safe and ignore Feynman. How do you analyze boolean circuits using partial differential equations? What else can you accomplish with this technique? No one seems to know how he did it.

tlb 8y ago
There's an idea used in the analysis of error correcting codes, to set up a polynomial where the coefficients are the number of codewords with each Hamming weight. It works out the same as adding up all the codewords, where you replace each 0 by x and each 1 by y. So a code 010 101 => xyx + yxy = x^2y + xy^2 https://en.wikipedia.org/wiki/Enumerator_polynomial https://en.wikipedia.org/wiki/Enumerator_polynomial Then you can use real (or even complex) analysis on these polynomials. There's a thick book of things you can prove about sets of binary words using those techniques: https://www.elsevier.com/books/the-theory-of-error-correcting-codes/macwilliams/978-0-444-85193-2 https://www.elsevier.com/books/the-theory-of-error-correctin... And Noam Elkies' course notes on it: http://www.math.harvard.edu/~elkies/M256.13/index.html http://www.math.harvard.edu/~elkies/M256.13/index.html
- sillysaurus3 8y ago
  mic drop Thank you. This was a legendary answer. I really have been hunting this question for years: https://news.ycombinator.com/item?id=13764917 https://news.ycombinator.com/item?id=13764917 This seems like how he did it. Error correcting codes are a natural domain for questions like "What are the fewest gates gates required to transmit some information?" But the missing puzzle piece was that you can analyze them with polynomials.
  - graycat 8y ago
    Error correcting codes, coding theory, etc. is an old, serious, and deep field. Once I took a grad course in it. The course was heavily abstract algebra, especially finite fields. A respected text is W.\ Wesley Peterson and E.\ J.\ Weldon, Jr., {\it Error-Correcting Codes, Second Edition.\/} Last I heard, there has been some surprisingly good progress in the field. Might look up, say, "turbo codes".
danbruc 8y ago
I mean 1 - x * y can be interpreted as !(x & y) in a straight forward manner and the NAND gate is universal, so you could certainly express any combinational logic. Obviously x and y can be time dependent functions and I think it would not be too hard to find a suitable equation for some kind of flip-flop and then you already got everything for building arbitrary finite state machines. I guess you could even introduce things like gate delays and more realistic impulse responses without too much trouble. There are certainly many other ways to model different aspects of digital logic and I have no idea what exactly Feynman needed and used.
CrI0gen 8y ago
Here's a thread from last year which have a few insightful discussions on the topic: https://news.ycombinator.com/item?id=13762614 https://news.ycombinator.com/item?id=13762614 I imagine he used some of the "tools in his toolbox" he acquired from various fields of Physics. Given that it was a PDE his answer also probably was an approximation
pfortuny 8y ago
You may call v the density (time-dependent) of 1 in the flow (hence 1-v is the density of 0). Now you simply assume the flow is a differentiable function. As a matter of fact, it will ressemble reality much better than many economic models, for example (if not all): there is a HUGE amount of bits per second.
jandrese 8y ago
His analysis was on a machine with a very unique architecture. I've generally assumed that the problem he was analyzing was somewhat unique to that design. The Thinking Machines computers he was analyzing were massively parallelized, they had thousand of processors, but the processors were unbelievably primitive. They operated on a single bit and had a tiny number of instructions. The part Fenyman analyzed was the routing between the processors. You also missed the followup. When the design was nearing completion they realized that they wouldn't have the silicon for 7 buffers per chip so the hardware was finalized with 5 buffers per chip. It was enough.
carapace 8y ago
(Cheers for asking! I've been wondering about that too, ever since reading it.)

tlb 8y ago

There's an idea used in the analysis of error correcting codes, to set up a polynomial where the coefficients are the number of codewords with each Hamming weight. It works out the same as adding up all the codewords, where you replace each 0 by x and each 1 by y. So a code 010 101 => xyx + yxy = x^2y + xy^2 https://en.wikipedia.org/wiki/Enumerator_polynomial https://en.wikipedia.org/wiki/Enumerator_polynomial Then you can use real (or even complex) analysis on these polynomials. There's a thick book of things you can prove about sets of binary words using those techniques: https://www.elsevier.com/books/the-theory-of-error-correcting-codes/macwilliams/978-0-444-85193-2 https://www.elsevier.com/books/the-theory-of-error-correctin... And Noam Elkies' course notes on it: http://www.math.harvard.edu/~elkies/M256.13/index.html http://www.math.harvard.edu/~elkies/M256.13/index.html

sillysaurus3 8y ago
mic drop Thank you. This was a legendary answer. I really have been hunting this question for years: https://news.ycombinator.com/item?id=13764917 https://news.ycombinator.com/item?id=13764917 This seems like how he did it. Error correcting codes are a natural domain for questions like "What are the fewest gates gates required to transmit some information?" But the missing puzzle piece was that you can analyze them with polynomials.
- graycat 8y ago
  Error correcting codes, coding theory, etc. is an old, serious, and deep field. Once I took a grad course in it. The course was heavily abstract algebra, especially finite fields. A respected text is W.\ Wesley Peterson and E.\ J.\ Weldon, Jr., {\it Error-Correcting Codes, Second Edition.\/} Last I heard, there has been some surprisingly good progress in the field. Might look up, say, "turbo codes".

danbruc 8y ago

I mean 1 - x * y can be interpreted as !(x & y) in a straight forward manner and the NAND gate is universal, so you could certainly express any combinational logic. Obviously x and y can be time dependent functions and I think it would not be too hard to find a suitable equation for some kind of flip-flop and then you already got everything for building arbitrary finite state machines. I guess you could even introduce things like gate delays and more realistic impulse responses without too much trouble. There are certainly many other ways to model different aspects of digital logic and I have no idea what exactly Feynman needed and used.

CrI0gen 8y ago

Here's a thread from last year which have a few insightful discussions on the topic: https://news.ycombinator.com/item?id=13762614 https://news.ycombinator.com/item?id=13762614 I imagine he used some of the "tools in his toolbox" he acquired from various fields of Physics. Given that it was a PDE his answer also probably was an approximation

pfortuny 8y ago

You may call v the density (time-dependent) of 1 in the flow (hence 1-v is the density of 0). Now you simply assume the flow is a differentiable function. As a matter of fact, it will ressemble reality much better than many economic models, for example (if not all): there is a HUGE amount of bits per second.

jandrese 8y ago

His analysis was on a machine with a very unique architecture. I've generally assumed that the problem he was analyzing was somewhat unique to that design. The Thinking Machines computers he was analyzing were massively parallelized, they had thousand of processors, but the processors were unbelievably primitive. They operated on a single bit and had a tiny number of instructions. The part Fenyman analyzed was the routing between the processors. You also missed the followup. When the design was nearing completion they realized that they wouldn't have the silicon for 7 buffers per chip so the hardware was finalized with 5 buffers per chip. It was enough.

carapace 8y ago

(Cheers for asking! I've been wondering about that too, ever since reading it.)