8 ms·
“Maxwell's equations of software” examined (2008)
- ncmncm 6y agoThere is really nothing to it. A Lisp interpreter runtime can be made to interpret a subset of Lisp. It is very much more impressive that you can make a whole computer out of nothing but NAND or NOR gates, but still the same sort of thing.
- jmiskovic 6y agoDepends very much on gates. They would have to be idealized, with constant non-zero input-to-output propagation time. Best approach is then to simulate them, perhaps in Lisp.
- gradschool 6y agoI'm guessing that's because you envision using some of those gates to fake a clock. Wouldn't you also have to make some assumptions about wire propagation delays to guarantee hazard-free operation?
- jmiskovic 6y agoAny wire propagation would work, zero or positive, as long as it is deterministic (it can all be compensated by extra NAND/NOR gates). And with negative propagation delays you could do wonders! Anyway, my comment was a quick jab to circle back to Lisp after parent dismissed its elegant core.
- ncmncm 6y agoAre you aware that CDC did, in fact, make mainframe computers out of physical NOR gates? One gate per PC board.
- bsaul 6y agoside question : i remember a course in my logic class where our teacher showed us a programming language made of only two letters, and where all operations, numbers, etc were all defined with just those two letters. It was created by some famous logician but i can't find anything on the web about it. Anyone here knows what that could be ? edit : i think the lesson was showing curry's work on combinator logic..
- ummwhat 6y agoPerhaps this is related. I learned that in fact you do not need for "God made the integers". The definition of every object in mathematics can be bootstrapped from the empty set. 0 is the set containing the empty set. 1 is the set containing 0 and the empty set. Etc. Perhaps the two symbols you are thinking of are equivalent to "{" and "}".
- JadeNB 6y ago> 0 is the set containing the empty set. 1 is the set containing 0 and the empty set. Etc. Perhaps the two symbols you are thinking of are equivalent to "{" and "}". This is not the usual von Neumann encoding (https://en.wikipedia.org/wiki/Ordinal_number#Von_Neumann_definition_of_ordinals https://en.wikipedia.org/wiki/Ordinal_number#Von_Neumann_def...), so I think you may have started one level too encoded. The usual encoding puts 0 equal to the empty set, and n + 1 equal to the union of n (a set with n elements) and {n} (a singleton with 1 element). In other words, if I understand the meaning of 'Etc.', your encoding puts 0 = {Ø}, 1 = {0, Ø} = {{Ø}, Ø}, 2 = {1, Ø} = {{{Ø}, Ø}, Ø}, …, whereas the usual encoding puts 0 = Ø, 1 = 0 ∪ {0} = {Ø}, 2 = 1 ∪ {1} = {Ø, {Ø}}, …. One advantage of this latter encoding is that the set n has n elements, and that the set n is n-times nested, in the sense that longest chain of elements x ∈ y ∈ z ∈ … ∈ n has length n. It also generalises nicely to ordinals (a transfinite generalization of the natural numbers), as explained in the above link (https://en.wikipedia.org/wiki/Ordinal_number#Von_Neumann_definition_of_ordinals https://en.wikipedia.org/wiki/Ordinal_number#Von_Neumann_def...).
- Rerarom 6y agoProbably it was indeed combinatory logic, but see also https://en.wikipedia.org/wiki/Iota_and_Jot https://en.wikipedia.org/wiki/Iota_and_Jot
- tromp 6y agoIn my opinion, "Maxwell's equations of software" ought to be based on the simplest possible computational framework, which one could argue is the lambda calculus. A meta circular interpreter working on a simple binary encoding of lambda calculus (where abstraction is 00, application is 01, and a variable is 1^{n}0) is only 206 bits long [1][2], over 20 times smaller than the article's equations. [1] https://tromp.github.io/cl/cl.html https://tromp.github.io/cl/cl.html [2] https://tromp.github.io/cl/LC.pdf https://tromp.github.io/cl/LC.pdf
- cjfd 6y agoI think the SKI combinators are quite a bit simpler than lambda calculus. In lambda calculus the renaming of dummy variables is quite tricky. E.g., these lecture notes actually get substitution wrong: https://www21.in.tum.de/teaching/lambda/WS1718/lambda.pdf https://www21.in.tum.de/teaching/lambda/WS1718/lambda.pdf but I only found out after using the substitution rules on page 7 in a formalization of lambda calculus.
- tromp 6y agoAs mentioned in my other comment, combinatory logic is simpler, but it's also less expressive, and results in a larger self-interpreter in the corresponding language. For conciseness in language self-interpreters, (binary) lambda calculus is hard to beat.
- esmi 6y agoHow about a 2 state 3 symbol Turing machine? That’s pretty simple, and universal too. https://en.m.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol_Turing_machine https://en.m.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol...
- arethuza 6y agoAs tromp has a meta-circular implementation of lambda calculus maybe that Turing Machine could be implemented in lambda calculus and we could have an objective measure of which one is "simplest"?
- amelius 6y agoMaxwell's equations are linear (solutions are superimposable etc.) I think if you'd call something "Maxwell's equations of software", a similar property should hold, somehow ...
- evanb 6y agoOnly if you take U(1) as your gauge group. If you pick a non-abelian group the equations are not linear and solutions are not superposable.
- mrfox321 6y agoMaxwell's equations are linear. The nonlinearity of quantum field theory is not relevant here.
- evanb 6y agoI was trying to convey that "Maxwell's equations" can name not just the equations that describe electromagnetism, which has a U(1) gauge group, but can name an entire category of gauge theory equations---one for each gauge group. If the gauge group isn't abelian Maxwell's equations are _not_ linear.
- a1369209993 6y agoCan you give a example of a set of gauge theory equations for a non-U(1) gauge group? This seems interesting but I'm not really sure what it would actually look like.
- evanb 6y agoQCD is a nonabelian gauge theory, for example. The generalized Maxwell action is called the Yang-Mills action. The corresponding equations are very similar, except the gauge-covariant derivatives do not take a particularly simple form (which they do in the U(1) case because U(1) is abelian). https://physicstravelguide.com/equations/yang_mills_equations#tab__why_is_it_interesting https://physicstravelguide.com/equations/yang_mills_equation...
- z29LiTp5qUC30n 6y agoI think current bootstrapping work clearly shows that the Maxwell equations of software are: pop rx -> sp--; rx := mem[sp] push rx -> mem[sp] := rx; sp++ sub rx ry -> rx := rx - ry jmp rx $I -> if rx is zero jump $I bytes from end of instruction. One might also argue: call rx -> mem[sp] := IP; sp++; IP := rx ret -> sp--; IP := mem[sp] nand rx ry -> rx := rx nand ry but those are just optimizations
- andrewflnr 6y agoExactly what bootstrapping work? Looks interesting (and like Forth, but that's no surprise).
- neutronicus 6y agoAs someone who spent years studying Computational Plasma Physics, it feels strange to see someone cite "Maxwell's Equations" as some sort of platonic form of simplicity
- trianglesphere 6y agoI think the comparison might be subtly apt. Maxwell's is clean when deriving EM waves in a vacuum, but once you add in particles and go to the real world it becomes a mess just as you need much more than lambda expressions and evals to build software.
- adameast1978 6y agoI have never understood the need in the Computer field or other fields for that matter to make unnecessary and incorrect analogies to physics. It is silly and I have to look past this as many things have worth where the author does this as some sort of way to make what they did seem more impressive rather than just advance something on its own merits.
- Koshkin 6y agoI guess there's something to be gained by doing that. (By contrast, electrodynamics wouldn't gain anything by calling Maxwell's equations "the lambda calculus of physics.")
- adameast1978 6y agoI would say that we as CS people could learn from physics but when name things God Particle... Arguably to grab headlines I wonder about the Physics world... Then again I guess things like funding and getting people interested are important.
- Koshkin 6y agoAs Lederman explains, "This boson is so central to the state of physics today, so crucial to our final understanding of the structure of matter, yet so elusive, that I have given it a nickname: the God Particle. Why God Particle? Two reasons. One, the publisher wouldn't let us call it the Goddamn Particle, though that might be a more appropriate title, given its villainous nature and the expense it is causing. And two, there is a connection, of sorts, to another book, a much older one..."