Thanks for your reply! I had never heard of SKI-Calculus!
In short: If you want to actually get anything done, Turing machines suck! They’re painful to use, and that makes it hard to get insight by experimenting with them.
I feel like one advantage Turing machines have, is that they are in some sense low level (actually quite close to how we build our computers)? They do seem to have a nice abstraction for memory. I would have no idea how to characterize NSPACE with lambda calculus, for example (though of course googling reveals someone seems to have figured it out).
They’re actually quite different from how our computers work (just on the surface already, the program is unmodifiable and separate from the code, and the whole walking around is also a very important difference[1]), but I agree that they feel “electronics-y” / like a big ball of wires.
Don’t forget that most of the complexity theoretic definitions are based on Turing machines, because that happened to become the dominant model for the study of these kinds of things. Similar-but-slightly-different constructions would perhaps be more “natural” on lambda calculus, so if that had been the dominant model, then the Turing machine versions would have been slightly awkward instead.
But memory isn’t actually a problem – see Lisp. Represent everything as a cons cell (a storage unit with two slots) or a “symbol” (basically an unmodifiable string that compares in O(1)), where cons cells nest arbitrarily. (Simplest cell representation is two pointers and maybe a few tag bits to decide what it represents… optionally plus garbage collector stuff. Very close to how our computers operate!) Variable names become symbols, application becomes a cell, and lambdas can either become a specially tagged cell, or a nested construction like (lambda ('var body)) (doesn’t really make a difference memory-wise, just a constant factor.) Time is also easy – just count the number of reductions, or maybe include the number of substitutions if you think that’s important. (But again, constant factor, doesn’t actually matter.)
You could even argue that the problem goes in the other direction: For Turing machines, you largely don’t care about the states (often you don’t even explicitly construct them, just argue that they could be constructed), whereas lambda calculus programs are routinely written out in full. So had lambda calculus become the basis, then program size / “problem description complexity”, the “cost of abstractions”, reusability and other related things might have been considered more important. (You get a bit of that now, under the name of “code quality”, but it could have happened much earlier and way more thoroughly.)
An average normal program is extremely pointer-heavy, but you don’t even have the “alphabet” to efficiently represent pointers. (Unless you make “bytes” from bits and then multiply your state count to deal with that construction.) You also don’t have absolute locations, you can’t really do variables (especially not arbitrary numbers of them), and so on. So if you look deeper, both have a very different approach to state and, by extension, functions.
These are good points. From my understanding of how processors work, it seems one would get most of the benefits you mention by having addresses/absolute locations (and thus being able to use pointers [by using addresses instead of left/right operations]). Does that ring true to you?
I think I got something about what you said, that in a certain sense we don’t care about state with a Turing machine. It just occurred to me that the only reason we can use these more convenient designs in a processor is because its memory is limited. (Not sure if this is true? There is probably a really awkward way you could encode addresses, even if your memory were infinite? You’d probably do some tree-like thing, and figuring out where you actually want to put stuff would take some time.)
Thanks for your reply! I had never heard of SKI-Calculus!
I feel like one advantage Turing machines have, is that they are in some sense low level (actually quite close to how we build our computers)? They do seem to have a nice abstraction for memory. I would have no idea how to characterize NSPACE with lambda calculus, for example (though of course googling reveals someone seems to have figured it out).
They’re actually quite different from how our computers work (just on the surface already, the program is unmodifiable and separate from the code, and the whole walking around is also a very important difference[1]), but I agree that they feel “electronics-y” / like a big ball of wires.
Don’t forget that most of the complexity theoretic definitions are based on Turing machines, because that happened to become the dominant model for the study of these kinds of things. Similar-but-slightly-different constructions would perhaps be more “natural” on lambda calculus, so if that had been the dominant model, then the Turing machine versions would have been slightly awkward instead.
But memory isn’t actually a problem – see Lisp. Represent everything as a cons cell (a storage unit with two slots) or a “symbol” (basically an unmodifiable string that compares in O(1)), where cons cells nest arbitrarily. (Simplest cell representation is two pointers and maybe a few tag bits to decide what it represents… optionally plus garbage collector stuff. Very close to how our computers operate!) Variable names become symbols, application becomes a cell, and lambdas can either become a specially tagged cell, or a nested construction like
(lambda ('var body))(doesn’t really make a difference memory-wise, just a constant factor.) Time is also easy – just count the number of reductions, or maybe include the number of substitutions if you think that’s important. (But again, constant factor, doesn’t actually matter.)You could even argue that the problem goes in the other direction: For Turing machines, you largely don’t care about the states (often you don’t even explicitly construct them, just argue that they could be constructed), whereas lambda calculus programs are routinely written out in full. So had lambda calculus become the basis, then program size / “problem description complexity”, the “cost of abstractions”, reusability and other related things might have been considered more important. (You get a bit of that now, under the name of “code quality”, but it could have happened much earlier and way more thoroughly.)
An average normal program is extremely pointer-heavy, but you don’t even have the “alphabet” to efficiently represent pointers. (Unless you make “bytes” from bits and then multiply your state count to deal with that construction.) You also don’t have absolute locations, you can’t really do variables (especially not arbitrary numbers of them), and so on. So if you look deeper, both have a very different approach to state and, by extension, functions.
These are good points. From my understanding of how processors work, it seems one would get most of the benefits you mention by having addresses/absolute locations (and thus being able to use pointers [by using addresses instead of left/right operations]). Does that ring true to you?
I think I got something about what you said, that in a certain sense we don’t care about state with a Turing machine. It just occurred to me that the only reason we can use these more convenient designs in a processor is because its memory is limited. (Not sure if this is true? There is probably a really awkward way you could encode addresses, even if your memory were infinite? You’d probably do some tree-like thing, and figuring out where you actually want to put stuff would take some time.)