5 ms·

lambda calculus is turing complete. But so are turing machines. So why not have turing machines be the Maxwells equations of software. Maybe there's an infinit

• tromp 4y ago
  Because Turing machines are so cumbersome compared to lambda calculus that a universal Turing machine takes thousands of bits [1]. [1] http://www.verostko.com/tur-doc.html#B0,%20Universal%20Turing%20Machine0 http://www.verostko.com/tur-doc.html#B0,%20Universal%20Turin...
  • deleted 4y ago
    [deleted]
• mejutoco 4y ago
  I find Lambda calculus and term rewriting much more elegant and easy to understand. I don't think there is a simpler Turing-complete language (maybe Game of Life?). For Turing machines I recommend the book "The annotated Turing".
  • deltasevennine 4y ago
    Well if game of life is simpler, why not game of life? What does it mean to be Maxwells Equations? Does it mean absolutely most fundamental? Most practical? What? Maybe there's something more fundamental then turing. Thanks for the book recommendation
    • d0mine 4y ago
      > What does it mean to be Maxwells Equations? In a word: elegant.
      • sfpotter 4y ago
        It means much more than just being elegant! Maxwell’s equations are arguably the most successful existing physical theory. They are incredibly accurate over a huge range of scales. They are used in essentially unaltered form all over modern day engineering and have astonishing predictive power. On top of this, they are a useful tool without modification! They are the working tool for all electrical engineers. They’re not some lower-level substrate that exists in the background. They are used directly to model and generate other, simpler approximate theories (such as geometric and physical optics) which are powerful and elegant in their own right. I don’t think Lisp, lambda calculus, Turing machines, or similar can make this kind of claim.
        • kragen 4y ago
          what it means to say maxwell's equations have 'predictive power' is that we can 1. take a situation observed or designed in the contingent universe, 2. translate it into the abstract entities maxwell's equations talk about, 3. deduce consequences in the world of abstract entities, 4. translate those consequences back into the contingent universe, and then 5. find that the consequences in the contingent universe are within narrow uncertainty bounds we translated from the abstract world of ideas the meaning of turing universality is precisely that any turing-complete programmable system can be used to model any other logical or mathematical system, including other turing-complete systems, in exactly the same way that maxwell's equations model electromagnetism for example, you can model risc-v execution in lisp and predict what a risc-v processor will do, you can model lisp execution in the λ-calculus and predict what a lisp interpreter will do, you can model the λ-calculus in a turing machine and predict what λ-reduction will do, and you can model a turing machine in a risc-v processor and predict what the turing machine will do there is a significant sense in which this sort of modeling is much more perfect than the kind done with maxwell's equations when we apply maxwell's equations, we are subject to measurement error in steps 1 and 5; our measurements are never complete and correct, and heisenberg's uncertainty principle strongly suggests that they never can be. and in step 3, because maxwell's equations are continuous-time continuous-space differential equations, we often also introduce numerical error in our calculations as well, because we usually have to integrate them numerically rather than algebraically on the other hand, in the case of computational universality all the entities being discussed are discrete, algebraic, mathematically abstract entities, so our simulations are absolutely perfect unless we run out of memory or suffer a rare hardware error obviously these universal machines are not limited to modeling other universal machines; we can also use lisp or turing machines or risc-v processors to model things like gravitation, taxation, or maxwell's equations. and they are obviously also the main working tool for all electrical engineers today, having displaced slide rules and load lines generations ago ultimately, though, we are also using maxwell's equations (and other equations describing electromagnetism, like the ebers-moll transistor model) to design our electronic computers which we use to simulate lisp