4 ms·

If you can't define an algorithm as a step-by-step process, what can you define it as? That's the whole point: it is a process, manifested as sets of discrete s

by imode 8y ago

If you can't define an algorithm as a step-by-step process, what can you define it as? That's the whole point: it is a process, manifested as sets of discrete steps, towards an end result by following sets of rules. Lambda Calculus, Turing Machines, etc. are no different in this regard. One has its steps realized in reduction and substitution rules, the other has its steps realized in movements of the head and manipulations of the tape. You'll need more to disprove my hypothesis. All software is built compositionally, up from smaller pieces. It's why we commonly refer to everything as a "software stack": we can reason about smaller making up larger. If you examine most of the code written today, this very minute, you'll see it's compositional, in the way that larger codebases are built from components. Neither LC or TMs are "natural ways of thought", they're mechanisms. Turns out that TMs won out not only because they admit an easy physical implementation, but also because they're compositional. I can wire up two TMs and get them to perform operations in sequence, perform conditional branching, etc. JavaScript is hardly Lisp in a C-suit, but that's beside the point, because C is pretty terrible (despite it being my favorite) regardless of what paradigm you choose. I'm not going to devote much of this comment towards that. All software is compositional, regardless of the medium, and all computation is purely mechanical, regardless of the model of computation, because unless you want to stare at a lambda expression and infer the value, you need to perform some kind of step-wise reduction. That, after all, was Church's point.

chriswarbo 8y ago
> Neither LC or TMs are "natural ways of thought" I agree. I think it's like Moravec's paradox: we tend to forget how hard it was to first grasp the concepts of programming, and go on to treat whatever's most familar as being "obvious", even if it's not. Still, there are a few specific points I take issue with: > Lambda Calculus, Turing Machines, etc. are no different in this regard. One has its steps realized in reduction and substitution rules, the other has its steps realized in movements of the head and manipulations of the tape. There is a very big difference between TMs and LC in this regard: each step of a TM takes a constant amount of resources (time, energy, whatever https://en.wikipedia.org/wiki/Blum_axioms https://en.wikipedia.org/wiki/Blum_axioms ); whilst a single beta-reduction "step" in LC may require an arbitrary amount of work (depending on how many times a variable occurs, whether we need to rename to avoid name capture, etc.). My (perhaps naive) assumption is that the work required for beta-reduction is only bounded by the busy beaver function. This is probably why most computational complexity research sticks with machine models (operational semantics) like TMs. Still, there are alternative approaches which are very natural for LC-style programming, like "cost semantics" (essentially an alternative set of reduction rules for LC, which evaluate a program into its the algorithmic complexity, rather than into its return value). > Turns out that TMs won out not only because they admit an easy physical implementation, but also because they're compositional. I'd hesitate to call TMs compositional. As I wrote at https://cstheory.stackexchange.com/questions/21705/what-is-the-contribution-of-lambda-calculus-to-the-field-of-theory-of-computatio/21860#21860 https://cstheory.stackexchange.com/questions/21705/what-is-t... TMs can't really be re-used. Consider a TM (or program for a universal TM) for adding two numbers: it's hard to actually use that as part of any other TM/program, since it may clobber the rest of the tape, we need to setup the contents of the tape, state and read-head just right before invoking it, and clean up afterwards, those may require that we shuttle the rest of the tape contents along to make room, and so on. In contrast, LC lives in an abstract world where subexpressions can expand and contract without bumping into each other, terms can be duplicated and rearranged without having to drag them across the intermediate symbols, etc.
- imode 8y ago
  I think you're right w.r.t re-usability, though I've found semi-Thue systems more useful for formulating Turing Machines in order to avoid shifting things around. The string can just expand as needed, though the complexity probably changes.

by imode 8y ago

chriswarbo 8y ago

> Neither LC or TMs are "natural ways of thought" I agree. I think it's like Moravec's paradox: we tend to forget how hard it was to first grasp the concepts of programming, and go on to treat whatever's most familar as being "obvious", even if it's not. Still, there are a few specific points I take issue with: > Lambda Calculus, Turing Machines, etc. are no different in this regard. One has its steps realized in reduction and substitution rules, the other has its steps realized in movements of the head and manipulations of the tape. There is a very big difference between TMs and LC in this regard: each step of a TM takes a constant amount of resources (time, energy, whatever https://en.wikipedia.org/wiki/Blum_axioms https://en.wikipedia.org/wiki/Blum_axioms ); whilst a single beta-reduction "step" in LC may require an arbitrary amount of work (depending on how many times a variable occurs, whether we need to rename to avoid name capture, etc.). My (perhaps naive) assumption is that the work required for beta-reduction is only bounded by the busy beaver function. This is probably why most computational complexity research sticks with machine models (operational semantics) like TMs. Still, there are alternative approaches which are very natural for LC-style programming, like "cost semantics" (essentially an alternative set of reduction rules for LC, which evaluate a program into its the algorithmic complexity, rather than into its return value). > Turns out that TMs won out not only because they admit an easy physical implementation, but also because they're compositional. I'd hesitate to call TMs compositional. As I wrote at https://cstheory.stackexchange.com/questions/21705/what-is-the-contribution-of-lambda-calculus-to-the-field-of-theory-of-computatio/21860#21860 https://cstheory.stackexchange.com/questions/21705/what-is-t... TMs can't really be re-used. Consider a TM (or program for a universal TM) for adding two numbers: it's hard to actually use that as part of any other TM/program, since it may clobber the rest of the tape, we need to setup the contents of the tape, state and read-head just right before invoking it, and clean up afterwards, those may require that we shuttle the rest of the tape contents along to make room, and so on. In contrast, LC lives in an abstract world where subexpressions can expand and contract without bumping into each other, terms can be duplicated and rearranged without having to drag them across the intermediate symbols, etc.

imode 8y ago
I think you're right w.r.t re-usability, though I've found semi-Thue systems more useful for formulating Turing Machines in order to avoid shifting things around. The string can just expand as needed, though the complexity probably changes.