20 ms·
On Two Views of Computation in Computer Science
- LolWolf 10y agoThis is an interesting article, but I'm still fairly confused about the notion that is made >Harper’s attack on the utility of machine models and lack of modularity is tantamount to an architect saying to a chemist, “both of our disciplines concern the arrangement of molecules, yet my discipline is superior, as yours doesn’t even have the modular notion of a room!” But wouldn't the whole point be that a chemist, seeing the room as nothing less than an abstraction, can also understand the room through their given framework? Much in the same way that, for any computational model, we can think of a TM with an Oracle tape, or some similar IO model, that has the same computational power as any defined language? I'm afraid that I thought I understood the distinction at first: where those who support CT view computation as a fundamental case (e.g. every other mathematical 'primitive' can be derived from a computation with the appropriate oracles[1]) and and the TOP view which sees mathematical foundations as the main case, and then sees computers as being an abstraction of functions in some sense, such that one can construct a calculus of these functions which constitutes a language. Did I get this all wrong? I'm afraid I still don't understand the main distinction to be honest. It seems that both parties are going around in circles on exactly the same thing, but assuming different axiomatic systems and showing that each is equivalent to the other. [1] For example, with no oracles, we receive all of constructive mathematics, etc.
- pron 10y agoYou can translate and transform many things to many others. The important question is what is the computational complexity of the transformation? If it is large, then the two things are very different. As Scott Aaronson once said, waterfalls could be viewed as playing chess, but as the complexity of the translation from the "waterfall language" to a chess language understandable by humans is as great as the complexity of an actual chess-playing program, all the work is done in the translation. So the question you should be asking is where the complexity is being spent and on what.
- LolWolf 10y agoWait, but I thought the question being posed wasn't about the computational complexity of any model but about the power of a given computational model relative to another (e.g. the subject of the CT thesis). Even if we're talking about just computational complexity, if we allow Turing machines with arbitrary oracles, or (equivalently) we allow arbitrary mathematical constructions in languages, I'm still unsure as to why the complexity matters. W.r.t the waterfall case. Sure, I agree with that statement, but I'm unsure as to how it plays into the final case---the question isn't about a specific model performing a specific task, but about a model being able to completely replicate another in terms of computational power. Anything I can do in a language (with some functions) I can do in a Turing machine with the appropriate oracles; and conversely, anything I can do in a Turing machine with some given oracles, I can do in a language.
- marcosdumay 10y agoWhat I get is that the question is "Does it make any sense to compare the two models, or are they just different things?" and the tentative answer is "They are different things, but one end of TOP coincides with TOC". I'm fully convinced. Both concepts answer different questions, and that is my favorite test (instead of the OP's "does one model map into the other?").
- pron 10y agoBoth models are equally powerful in the things they compute in terms of the Church-Turing Thesis. The TOP view also has other consideration. My point in the article was not to settle the debate on Aaronson's blog but to show that language models and machine models are objectively and inherently so different from one another that comparing them in terms of programming concepts (like types) is meaningless.
- LolWolf 10y agoI see, okay; I caught that point in the article through the first part, but the latter part got me stuck back on the same point hence the question. Thank you for the clarification.
- Kenji 10y agoIt’s really weird that the Church-Turing thesis, which is ridiculously robust at first order, falls apart so comprehensively at higher type. A statement like that makes me feel like Neel Krishnaswami does not understand the Church-Turing thesis at all (what does the Church-Turing thesis even mean at a "higher type"), but considering that this person has significant experience in this field, much more than I do, I am just going to assume that it is me who does not understand until I read up on this exactly.
- catnaroek 10y agoThe Church-Turing thesis is a statement about which functions of type `nat -> nat` are computable, either in the lambda calculus or using Turing machines. This completely disregards: (0) Computational complexity. Neither the lambda calculus nor Turing machines were invented to answer questions of computational complexity. (1) Functions at types other than `nat -> nat`. Curiously enough, programming in the real world is seldom about evaluating functions of type `nat -> nat`.
- TelmoMenezes 10y agoDoes a type exist such that it cannot be mapped to the set of natural numbers?
- catnaroek 10y agoYou mean mapped one-to-one? Depends on your model of computation. For example, in the simply typed lambda calculus, equipped with a natural number type, as well as structural recursion on it (but not general recursion), `nat` and `nat -> nat` aren't isomorphic types.
- TelmoMenezes 10y agoHumm... But the set of Turing Machines is countably infinite, and a nat -> nat function is necessarily representable as a Turing Machine.
- pklausler 10y agoThe author contends in the article's abstract that machine models are "self-contained" whereas "language models" (not clearly defined, but meant to encompass at least an untyped lambda calculus) are not. But both can be viewed as a state plus a well-defined set of rewriting rules, so I suspect that the article is struggling to make what is really a distinction without a difference.
- pron 10y agoAuthor here. > But both can be viewed as a state plus a well-defined set of rewriting rules, so I suspect that the article is struggling to make what is really a distinction without a difference. 1. I state that the untyped lambda calculus is, indeed, a borderline case, and is a simple rewriting system which, in turn, is a special case of a nondeterministic abstract state machine. 2. That many things are abstract state machines does not mean that the computational complexity required to validate whether what you have is a well-formed description is similar. 3. That complexity difference is absolutely huge -- zero for the machine models vs. exponential to undecidable for the typed language models. It is hardly a struggle to draw the conclusion that the two are objectively completely different classes. Also, I gave a list of machine and language models. The latter group consists of the process calculi and the lambda calculi.
- amatus 10y agoCould you encode all untyped lambda calculus expressions by just numbering them and writing the number as the string of bits? Maybe this enumeration is the "external collaborator" in this case, but it's a very simple one.
- catnaroek 10y agoInside the lambda calculus, the only thing you can do with a lambda abstraction is apply it. And one thing you can't do using your numbering scheme (which is basically a Gödel numbering) is establish whether two syntactically different functions are extensionally equal (under some fixed reduction strategy).
- 10y ago
- mathgenius 10y agoI think mathematicians would call this "representation theory." This is the whole question of do we think of a calculation as syntax, or can we represent this syntax as a "dynamic", or action; something that is being moved around or transformed. Some people really are driven to just calculate stuff (pushing language itself around), and others seem to want to know "what does it mean?" Ie. what are the representations of this language. Logicians call this semantics: it's a model for the syntax. I'm a theoretical physics grad student, and see plenty of this. Most physicists seem to just want to calculate stuff, and don't care where the symbols "live". For me, a calculation is rarely enlightening. I want the context, the type theory that tells me how the pieces talk to each other.
- j2kun 10y agoI don't think mathematicians would use "representation theory" for this, since representation theory is a very specific and precise subfield that is at best tangentially related to the theory of computation.
- Sniffnoy 10y agoI think you've got an interesting point, and I'd like to add to it a bit and refine/correct it a bit. First off, minor thing, but as Jeremy has pointed out, your terminology is wrong; "representation theory" means something else. You seem to mean something more like "model theory". But anyway -- I'm a mathematician, and I've noticed something like this too when I've dealt with physicists or their writings. But before I discuss physicists, let's discuss mathematicians, because I think you've mischaracterized them a little. (Note, all claims here are just based on my experience.) You talk about considering syntax vs. considering the different models of the syntax. But most mathematicians, unless they are logicians or set theorists or something, don't take either of those views. They take the Platonic view -- they're discussing a world of mathematical objects; the statements just describe it. They're not considering the statements as primary and then considering multiple models of it, they're considering the one true world of mathematical objects and describing it with statements (which might have other models, but who cares). This point of view breaks down somewhat when you have to deal with things like the continuum hypothesis and such, but that sort of thing doesn't really come up in ordinary mathematics. (Note though that taking the Platonic view does not necessarily mean taking the "theory of programming" perspective the article discusses. I mean, I wouldn't take Aaronson's view, that computation is prior to everything else; that's pretty incompatible with it. But to my mind, computation is fundamentally about finite strings over a finite alphabet. Talking about computation with higher types -- where the Church-Turing thesis can fail -- as though it were, well, computation, feels really weird to me.) Also, another terminological correction: Most mathematicans don't care about type theory. They care about types, at least implicitly, though they might not use that term; but they are not going to consider types as an object of study in and of themself. But yes -- when you want to understand a mathematical object, one of the first questions is, "What sort of object is that?" or "What space does that live in?" So anyway -- yeah, physicists. I've noticed this too, and I don't know what to make of it. Where physicists don't tend to fully specify their, let's call it an ontology, and have a hard time answering questions like "What sort of object is that?" or "So that's a function from what to what?" Where they don't seem to properly distinguish between a mathematical model or description, and a method of calculation that's useful when working with that model or description. (I have so often failed to get an answer to, "So are virtual particles an actual physical phenomenon predicted by the quantum field theory, or are they just part of a useful method of calculation for working with quantum field theory?") Where they seem to care primarily about methods for getting numbers out, rather than building full, coherent models. It's all weirdly instrumentalist, which to me seems backwards from what you'd expect -- like, mathematical Platonism is a philosophical question, but the physical world is definitely real! And sure, maybe the bits we can't measure are more of a philosophical question too -- especially since one can quite possibly come up with multiple isomorphic usable models for the laws of physics, whatever they turn out to be -- but still, mathematicians have no trouble just treating their mathematical objects as real things to be reasoned about, so this kind of instrumentalist view among physicists seems weird to me. I hadn't even considered the possibility that they were thinking "syntax-first", so to speak! But I guess that does kind of sum it up pretty nicely. Bugs the hell out of me, though. Makes it pretty difficult to talk about the math of their theories with them, too.
- readams 10y agoI'm not really sure I completely understand where the conflict is here. Even in the "machine model" the church-turing thesis "fails spectacularly" once you start adding in unreasonable things like halting oracles. TM+Halting oracle > TM. It's just that the TM+halting oracle doesn't exist in our universe, even though you can define it mathematically. When building a language, it's similarly easy to introduce "unreasonable" things that either require huge complexity to translate to the machine representation or might even be completely unrealizable in the real world! Even ignoring higher types, compiling a C++ program requires a potentially unbounded amount of work because templates are a turing-complete functional programming language. As stated in the article, just determining if a C++ program is valid is undecidable! Nothing stops you from designing these languages, but you can't say that Church-Turing fails until you consider also the systems required to actually execute these languages in the real world. If you can't, then your programming language is perhaps an interesting mathematical abstraction, but just as useful ultimately as that TM+halting oracle model of computation.
- j2kun 10y ago> TM+Halting oracle > TM Why is this a failure of the Church-Turing thesis? The Church-Turing thesis says, "Anything that can be computed in our reality (i.e. by a human, ignoring resource constraints) can be computed by a TM." TM+Halting oracle doesn't satisfy the hypothesis.
- readams 10y agoIt's not a failure of Church-Turing. The whole point of my comment is that you can easy construct more powerful models that are "unreasonable" because they don't exist in our universe. It's the same for programming language models.
- Double_Cast 10y ago> You’re free to think about computation as acting on bits… but for those bits to do us any good, they have to actually represent something (e.g., data structures). I suspect this is a case of confusing epistemology with ontology. Galaxies are ontologically composite in that they're the highest holonym in the supervenience hierarchy [0]. Atoms are ontologically fundamental in that they're the the lowest meronym in the supervenience heirarchy. Galaxies are epistemically abstract in that the notion of galaxy is far removed from everyday experience. Atoms are also epistemically abstract in that the notion of atoms are also far removed from everyday experience. What's epistemically fundamental are the immediate objects of our everyday experience, like chairs and food. (My impression of Zen is that it advises to focus more on things like chairs and food [1].) https://www.xkcd.com/435/ https://www.xkcd.com/435/ In the xkcd, which is more "fundamental", Math or Economics? Well, it depends. Likewise, what's more "fundamental", bits or ADT's? Well, it depends. [0] powers of 10: https://www.youtube.com/watch?v=0fKBhvDjuy0 https://www.youtube.com/watch?v=0fKBhvDjuy0 [1] http://www.itsokblog.com/2011/01/wash-your-bowl-zen-of-mothering_3089.html http://www.itsokblog.com/2011/01/wash-your-bowl-zen-of-mothe...
- pron 10y agoWell, in this case all models are quite abstract, and there's a very real computational complexity difference between them. The key, if I were to use your way of presenting the issue, is the recognition that some epistemological abstractions are more computationally costly than others. So it's true that you can choose either representation as a foundation, but the representations objectively and radically differ in their computational complexity.
- Double_Cast 10y agoThe key is to recognize how it's not just that TOP and TOC both measure X with different models. It's that TOP measures X while TOC measures Y. It's as if we claimed Spell Checking were as complex as Natural Language Processing because they were both called "linguistics". Yes, they both abstract over language. But the primitives of Spell Checking are glyphs while the primitives of NLP are morphemes. Glyphs don't exhibit the same patterns as morphemes. Which is why Spell Checking uses a Trie while NLP uses a Matrix. Debating whether glyphs or morphemes are "more fundamental" is a distraction. Likewise, bits don't follow the same patterns as ADT's. Calling both the study of bits and the study of ADT's "Complexity Analysis" is misleading, which I believe is what Pressler was getting at. But we've put bits and ADT's in the same bucket for the entire history of computing, because the Church Turing thesis (i.e. anything a TM can do, lambdas can do too) lead us to believe Turing and Church were studying the same primitives.
- Ericson2314 10y agoAcademia is feudal and thus no answer to this is about to become widely accepted. :(
- ittekimasu 10y agoActually it's a bit more like 42.
- pron 10y agoHow is showing that two representations are fundamentally different because they objectively and radically differ in computational complexity open to interpretation?
- Ericson2314 10y agoIt shouldn't be. I'm skeptical of your parsing argument because the normal way to construct type theory terms is inductively in their "native" tree form, which is cheap. Looking at them as a formal language isn't so convenient. As a PLer, I hope dependently typed langauges see wide use not because they are the one true foundation of everything, but because they are the richest lingua franca for every academic discipline to represent their ideas—I'm personally enamored of such theories as a foundation for math, but I don't know much about the theory of computation and I'm fine if others just see it as a tool. Anyways once that happens and fields have distilled their intentions into precise models in the lingua franca, perhaps the walls between fields can be broken down and we finally grok each other's concepts.
- pron 10y ago> their "native" tree form, which is cheap It is not cheap at all, as type checking can be arbitrarily hard, depending on the type system, and perform arbitrary computation at the "validation" stage. This is real, significant (and useful, depending on circumstance) computational work, that no formalism or representation can reduce (only hide, by pushing it over to the collaborator). > but because they are the richest lingua franca for every academic discipline to represent their ideas I disagree. I strongly recommend you (and everyone) read this terrific essay by Lamport on a lingua franca for algorithms: http://research.microsoft.com/en-us/um/people/lamport/pubs/state-machine.pdf http://research.microsoft.com/en-us/um/people/lamport/pubs/s... Not only is TLA just as powerful as dependent types, it is far simpler[1]. Lamport says that the reason PLers aren't interested in TLA+ is because it's so simple, so there's not much to write about it. You see plenty of papers about embedding all kinds of things (separation logic, cost models, concurrency etc. etc.) with dependent types, things that are so trivial in TLA+ that they're barely worth a mention. Ideas from Hoare logic, behavioral refinement, differences between notions of program equivalence from process calculi (trace equivalence vs. bisimulation) simply collapse into simple, familiar logic in TLA (the only thing missing is probabilistic reasoning). Lamport wrote about his experience trying to publish a paper showing that specifying real-time systems with TLA is trivial (it's a matter of defining a time variable): http://research.microsoft.com/en-us/um/people/lamport/pubs/pubs.html#real-simple http://research.microsoft.com/en-us/um/people/lamport/pubs/p... You can only write a few papers on a simple approach that solves many problems, but lots and lots of papers that show how to use complicated approaches to solve them. A lingua-franca must be simple. TLA+ uses notation and concepts that are familiar to all mathematicians and all computer scientists, plus a couple of new concepts that can be learned in a few days. Dependent types (and intuitionistic logic) are almost as arcane today as they were decades ago, virtually unknown outside the circles of logic and PLT, each of them is a particularly isolated sub-discipline within math and computer science. That so many papers are written about dependent types is strong evidence that they cannot serve as the lingua franca, and pretty conclusive proof that they cannot serve as the lingua franca just yet. That PLers, as Lamport writes in his comment on my post, fail to see that Plotkin's SOS is an abstract state machine, and that some fail to see that computing a set-theory function and a type-theory function are two different computational problems with radically different computational complexity is further evidence that language models obscure rather than reveal. Of course, as Lamport also says, real-world programming is very complicated, and so programming languages are justifiably complex (and whether dependent types can help with that remains to be seen[2]). But that complexity is absolutely not required for the purpose of a lingua franca with clear and simple semantics (TLA's semantics are far simpler than any programming language) for the purpose of specifying and analyzing algorithms. Disclosure: I've contributed some code to the TLA+ project. [1]: Not only do properties ("types") and algorithms share the same terms in TLA+, they are the same objects. This confuses some people to believe that TLA+ doesn't support higher-order algorithms, when, in fact, it becomes a non-issue. Instead of a parameter of a certain type, you have a concrete program that is the type (e.g., the program that nondeterministically returns, say, any even integer). [2]: I'm skeptical because I believe we're close to the "Brooks limit": http://blog.paralleluniverse.co/2016/07/23/correctness-and-complexity/ http://blog.paralleluniverse.co/2016/07/23/correctness-and-c...
- ankurdhama 10y agoThe article refers to one quora answer where the author says - "The machine-based models offer no notion of composition of programs from parts". The instructions are the parts of the so called machine model, isn't sequencing of those instructions and control flow instructions are nothing but composition?
- kd0amg 10y agoIt's a very impoverished form of composition if the only things you can really compose are the absolute primitives, rather than allowing you to compose things that are themselves composed. When you "program" with Turing machines, you don't have a way to take a section of "code" and paste it into another, larger program. You'll have to deal with two pieces numbering their states the same, overwriting each other's tape data, etc. If you have two Turing machines that solve separate pieces of the problem, you know there exists a single machine that does both things, but nobody actually goes and constructs that machine. Instead, they just mention its existence as justification for writing "do this; do that;" in a higher-level machine description.
- ankurdhama 10y agoI think the problem can be defined as "Composition without isolation", each composed sequence of instruction has this same global context (all of memory) to work with which can lead to problems.
- more_original 10y agoWhat he means is that complicated programs can be built from simple parts. In programming languages you can just take simple parts and compose them into a single program. If the simple parts are given by machines, then in general there is no canonical way of composing them into a machine for the composed program. You have to construct a new machine from the machines for the parts. An example is the sequential composition of two functions with logarithmic space usage. You cannot just use run one machine after the other, but you have to modify both machines and then build a new machine that contains them in the right way. Of course, one may use systematic constructions to combine simple machines into more complicated ones. But this amounts to the implementation of a programming model.
- joe_the_user 10y agoHonestly, I think Aaronson is clearly and transparently correct about Church-Turing and higher types. Computation on higher types is just a higher-order construct having no more to do with computation as we understand it than other higher order constructs like Hilbert Spaces.