2 ms·

> Isn't every existing programming language eventually based on (or at least traceable to) lambda calculus? No. Prolog et. al. is based on Horn Clause represe

• Rochus 5y ago
  Aren't turing machines and the lambda calculus equivalent, i.e. each can efficiently simulate the other?
  • carapace 5y ago
    They're equivalent, but not identical. Lots of formal systems are Turing complete (e.g. Wang Tiles) and so can compute the same results as each other. Wolfram goes on about this some. I sometimes wonder about the possible form of the "Platonic Ideal" is that each of these systems represent. George Spencer-Brown's Laws of Form seems to me to be the ultimate concrete example, but that's not a universally held opinion. :)
    • Rochus 5y ago
      But doesn't that mean you can create a corresponding lambda calculus based version of a programming language, such as Landin did in his 1965 paper?
      • carapace 5y ago
        Of course, but you could do that with the other formal systems too. It's like Roman numerals vs. base-10 numerals, eh? "XXIII" and "23" both denote the same number (which may or may not exist depending on your metaphysical outlook) but neither notation can be said to be "the" notation.
        • Rochus 5y ago
          That's ok; my concern was just whether "every existing programming language eventually based on (or at least traceable to) lambda calculus" responding to the fellow which claimed that "a functional programming language is one which is based on lambda calculus".