On Two Views of Computation in Computer Science

https://pressron.wordpress.com/2016/08/30/what-we-talk-about-when-we-talk-about-computation/

by pron • 10 years ago

107 187 10 years ago

pressron.wordpress.com

LolWolf3• 10 years ago

This 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.

pron63• 10 years ago

You 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.

LolWolf3• 10 years ago

Wait, 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.

clusmore• 10 years ago

The important question is what is the computational complexity of the transformation?

In my view it makes no sense to use metrics from one model on the other. There is no computational complexity involved in the transformations defined in ToP. This is like measuring the computational complexity of a mathematical proof - it has no complexity, it's delcarative.

Kenji• 10 years ago

It’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.

catnaroek43• 10 years ago

The 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`.

TelmoMenezes5• 10 years ago

Does a type exist such that it cannot be mapped to the set of natural numbers?

SilasX5• 10 years ago

Sorry if I'm missing something fundamental, but (1) shouldn't matter if there's some mapping between a) those types and b) functions of type `nat -> nat`. AIUI, the CTT is equivalent to saying that anything that can be computed at all (regardless of type signature) can be done via the `nat -> nat` functions representable on some TM. IOW, whatever transformation it is that the other-typed function makes (edit: or whatever input-output mapping), it is isomorphic to one on `nat -> nat`.

Since computers regularly implement exactly such a mapping, it doesn't sound like a problem.

Curiously enough, programming in the real world is seldom about evaluating functions of type `nat -> nat`.

How is it not about that? Everything you do is converted down to CPU ops that just implement (something expressible as) functions on natural numbers (technically, fixed-with binary numbers). The whole job of programming can be described as "converting a problem to a format suitable for a fast `nat->nat`-implementing machine"; it's just that several of the layers of the conversion are hidden from you.

marcosdumay4• 10 years ago

Computers in the real world pass all their time evaluating functions from nat -> nat. It is programmers that use different types.

pron63• 10 years ago

The 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 is how Krishnaswami frames things. From the TOC perspective, there is no such thing as functions at all. Computations consume and produce strings. Both Church and Turing explain how those strings can encode the natural numbers (there was no talk of types by either). Interpreting a computation as one computing functions on the natural numbers or any other set is an entirely interpretive activity that is external to the computation itself.

tome27• 10 years ago

Regarding (1), can you give a compelling higher-order example for which Church-Turing fails?

On Scott's blog Neel talked about functions '(unit -> bool) -> (unit -> bool) -> bool', but this example seems spurious. He asserted that Turing Machines could receive the arguments Godel encoded but the Lambda Calculus couldn't. I don't see why. If you also let the Lambda Calculus receive its arguments Godel encoded then it can inspect them and perform the same dovetailing that the Turing Machine would.

Do you know of a more compelling example?

joe_the_user2• 10 years ago

Well,

Another factor is that Church-Turing "at first order" isn't a mathematical theorem - (notice "thesis", not theorem).

The thesis is that all determinant computation is equivalent to Turing machines and lambda calculus (which are each computable with each other). This is a hypothesis about the physical world (or the "imaginable" world).

Thus Church-Turing is very significant - but not necessarily mathematically significant, as a mathematical theory, it's taken as the equivalence of Turing machines and Church's recursive functions (but that's just a theorem which only suggests the (nonmathematical) thesis.

The thing is, a lot of mathematicians are much more enamored of the mathematical world than the physical world. For an enthusiastic mathematician playing with high order recursive functions, a generalization of the Church-Turing theorem seems much cooler than the statement about the physical world that the Church-Turing thesis implies.

pklausler• 10 years ago

The 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.

pron63• 10 years ago

Author 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• 10 years ago

Could 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.

l_dopa2• 10 years ago

Why is the complexity of parsing well-formed states from strings somehow interesting? If you generalize to trees and pick the right alphabet, suddenly every element of your datatype is a well-formed lambda term.

It's also unclear if you're talking about the complexity of type inference or type checking, what annotations you're allowing, etc. Your claims about complexity re: states of typed languages are too hand-wavy to engage with.

And yet there's still a glaring error: for a very popular machine model, namely the C abstract machine, it's undecidable whether a state is meaningful (regardless of how you set up your parsing problem).

So, you have an interesting idea about the difference between machine models and languages but it clearly doesn't hold together. People have been studying the relationship between machine models and languages for quite some time, and it's relatively well understood. Machine models are one of the many ways to give semantics to languages. They just don't have many useful properties compared to more "abstract" approaches, and are mostly used to reason about implementation.

tome27• 10 years ago

zero for the machine models

That's absolutely not true. It takes non-zero effort to determine whether the code for a Turing machine actually implements a valid Turing machine.

mathgenius2• 10 years ago

I 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.

j2kun3• 10 years ago

I 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• 10 years ago

I 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.

mathgenius2• 10 years ago

your terminology is wrong; "representation theory" means something else. You seem to mean something more like "model theory".

I really do mean representation theory, in the widest sense of the word. Wide because I am trying to make connections here, not distinctions.

So for instance, of course group representations. On the one hand there is an abstract group multiplication, and on the other side we are representing this as a geometric action.

The same thing goes for "bigger" gadgets, lie algebras, hall algebras, etc. All kind of algebraic objects that we can define abstractly (syntactically) but then lo! it is actually represented by some kind of (geometric?) action.

And then in a more logical vein you have the lattice type theories. Boolean algebras, heyting algebras. These things have topological representations (or is it functions on topological spaces). And then to denotational semantics of lambda calculus. And it's all kind of a syntax on one side, and a semantics on the other.

I don't know much about models of set theory, but I'm assuming these also involve a kind of "active" representation of syntax. I would also include things like algebraic topology, topological quantum field theory. These are all "functors" which act to represent an algebraic gadget in a more dynamic way (i'm possibly over-generalizing here.)

Anyway, there's no concrete definition for what I mean by a "representation" so that's why i gave some examples. It's quite mysterious imho.

So anyway -- yeah, physicists.

Well, it's easy to criticize physicists, but I also think mathematicians are guilty of this. Ok, so they define their calculations rigorously (not always), but then it's gloves off and away we go! I've come to realize that the whole program of categorification is an attempt to bring more context to these calculations (this is what I would call type theory for mathematics btw.) And most mathematics is written down as calculations, without this context. Probably because it's much harder to categorify everything. The simplest example of what I mean is this: "why keep track of a (finite) set when you can just say how many elements are in the set?" And so on. I really do think that alot of mathematicians are just as guilty as physicists of the "shut up and calculate" attitude. But, they are certainly much more humble :-)

pron63• 10 years ago

The point of the article is that different representations incur different computational complexity costs. Those costs are objective and absolute. If two different representations each require wildly different computational complexity, then the two can't be meaningfully compared on the same terms, because the two are clearly and objectively different.

readams2• 10 years ago

I'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.

j2kun3• 10 years 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.

readams2• 10 years ago

It'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_Cast2• 10 years 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/

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

[1] http://www.itsokblog.com/2011/01/wash-your-bowl-zen-of-mothe...

pron63• 10 years ago

Well, 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_Cast2• 10 years ago

The 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.

Ericson23143• 10 years ago

Academia is feudal and thus no answer to this is about to become widely accepted. :(

ittekimasu• 10 years ago

Actually it's a bit more like 42.

pron63• 10 years ago

How is showing that two representations are fundamentally different because they objectively and radically differ in computational complexity open to interpretation?

ankurdhama3• 10 years ago

The 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?

kd0amg4• 10 years ago

It'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.

ankurdhama3• 10 years ago

I 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_original2• 10 years ago

What 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.

ankurdhama3• 10 years ago

I think you are confusing the word machine in this context. It is not the usual general purpose word machine that people use in every day life to denote a physical system. The word machine in context of model of computation means a specific type of "formal system" to describe computation. The problem of composition is about how this formal system does or doesn't support it.

joe_the_user2• 10 years ago

Honestly,

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.

On Two Views of Computation in Computer Science

Related Stories