Live data from Hacker News

On Two Views of Computation in Computer Science

pressron.wordpress.com

111–120 of 191 posts

Re: On Two Views of Computation in Computer Science

#111
post #94
post #85

Earlier quoted context omitted.

No,it's actually right. See my post comment answering the same question. It is the circuit models that actually pose a harder challenge, but even if you won't accept my reasonable zero-cost encoding where a misconnected input is interpreted as a constant 0,the cost of validation is still less than even untyped LC.

You state there that "at worst I would need O(n) time" so are you in fact conceding that my claim "It takes non-zero effort to determine whether the code for a Turing machine actually implements a valid Turing machine." was correct? https://pressron.wordpress.com/2016/08/30/what-we-talk-about...

I gave a natural, reasonable encoding that requires zero validation: every string is a valid TM, and every TM can be easily represented by that encoding and directly executed. However, some may object to the encoding on some grounds, so I said that even the strictest critic would agree to a more complex validation, which is still lower than that of untyped LC. Similarly, I made lenient assumptions about untyped LC (variable shadowing). Without it, you'd need to keep track of every variable that's in scope, so as not to accidentally bind it again. With it, evaluation becomes complex by a bigger factor than a TM becomes under my zero-cost representation.

It's important to understand that encoding is always a tricky subject, because every different encoding requires a different interpreter, and one could ask whether that interpreter is really the "original" TM or "original" LC (of course, there's no argument over huge complexity differences, but slight ones are up for some debate). I think that under very natural, reasonable encodings, the machine models require zero validation; I also think that allowing variable shadowing in LC is reasonable and doesn't completely change the model. It's perfectly OK to disagree with me on this point, but it really doesn't make a difference.

As to providing more detail in the post, well, I don't want to get lost in details that are ultimately inconsequential, and no matter what level of detail you choose, there will always be those who don't find it detailed enough. I prefer the interactive approach of an online discussion.

Re: On Two Views of Computation in Computer Science

#112
post #110

Earlier quoted context omitted.

> and solves a harder problem than necessary to compute that function in the normal set-theory sense People who use set theory as their foundations impose on themselves the even harder task of making sure their mappings are coherent w.r.t. whatever notion of structure they want to work with, i.e., homomorphisms in a category of interest. > Otherwise, I could create a language model that solves all NP problems in poly…

> People who use set theory as their foundations... Let's not get into this old debate because we'll never get out of it. Suffice it to say that it that there is no doubt that Turing and Church (and Gödel and von Neumann) used set theory as their foundation, and when they said "function" they meant a set-theoretic function, namely a mapping from a domain (set) to a range/co-domain (set). If by "function" you mean a t…

Of course, proving things, that is, doing mathematics requires work. But at least it's work that produces a useful result, unlike carrying out computations without paying attention to their meaning. (By the way, this meaning always exists, even if you don't particularly care about it.) And the best moment to study the meaning of a computation, in the sense of minimizing the amount of long-term work, is as early as possible, which is exactly what types force you to do.

Re: On Two Views of Computation in Computer Science

#113
post #108
post #104

Earlier quoted context omitted.

The notion of a function having any inherent complexity is rather at odds with your earlier assertion that putting any sort of meaning on the result of running a Turing machine is strictly human interpretation rather than a hard fact of computation (and of course, you also turn around and favor certain interpretations over others based on the cost of embedding them in your favorite computation model).

> The notion of a function having any inherent complexity is rather at odds with your earlier assertion that putting any sort of meaning on the result of running a Turing machine is strictly human interpretation rather than a hard fact of computation I don't see how. That inherent complexity is precisely that computed by the machine (provided that you're talking about a function in the ordinary, set theory sense, rat…

> I don't see how. That inherent complexity is precisely that computed by the machine

The same function may be computed by different procedures with different complexity.

> rather than in the type theory sense, in which case a function is a set-theoretic functions plus a proof of set membership

Not all types denote sets.

> There is no room for (significant) interpretation here: the typed formalisms can perform computations of possibly arbitrary complexity during their validation stage.

This is the price of capturing the meaning of computation. Of course it doesn't come for free. But, in general, the earlier you do it, the less work it requires. In the limit, if you do it really late (e.g., test suites), it requires an infinite amount of work (searching infinite input spaces).

Re: On Two Views of Computation in Computer Science

#114
post #89

Earlier quoted context omitted.

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

It 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 discipl…

> 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/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/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-c...

Re: On Two Views of Computation in Computer Science

#115
post #42
post #34

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 "unreason…

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

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.

Re: On Two Views of Computation in Computer Science

#116
post #110

Earlier quoted context omitted.

> People who use set theory as their foundations... Let's not get into this old debate because we'll never get out of it. Suffice it to say that it that there is no doubt that Turing and Church (and Gödel and von Neumann) used set theory as their foundation, and when they said "function" they meant a set-theoretic function, namely a mapping from a domain (set) to a range/co-domain (set). If by "function" you mean a t…

Of course, proving things, that is, doing mathematics requires work. But at least it's work that produces a useful result, unlike carrying out computations without paying attention to their meaning. (By the way, this meaning always exists, even if you don't particularly care about it.) And the best moment to study the meaning of a computation, in the sense of minimizing the amount of long-term work, is as early as po…

But this is now a programming discussion, not a computation discussion. Also, I don't think it's right to declare things "useful" only if they're useful to the particular problems you're trying to solve.

BTW, any logical formalism forces you to pay attention to meaning; choosing to encode the logic in types has advantages and disadvantages, but it is not at all the only way to logically describe a program.

Re: On Two Views of Computation in Computer Science

#117
post #116

Earlier quoted context omitted.

Of course, proving things, that is, doing mathematics requires work. But at least it's work that produces a useful result, unlike carrying out computations without paying attention to their meaning. (By the way, this meaning always exists, even if you don't particularly care about it.) And the best moment to study the meaning of a computation, in the sense of minimizing the amount of long-term work, is as early as po…

But this is now a programming discussion, not a computation discussion. Also, I don't think it's right to declare things "useful" only if they're useful to the particular problems you're trying to solve. BTW, any logical formalism forces you to pay attention to meaning; choosing to encode the logic in types has advantages and disadvantages, but it is not at all the only way to logically describe a program.

> Also, I don't think it's right to declare things "useful" only if they're useful to the particular problems you're trying to solve.

Pray tell, what's the use of a computation without paying attention to its meaning? My use case is simply “knowing the meaning as early as possible”, and there ought to be no discussion that this should be everyone else's use case as well. Nobody performs a computation without some sort of expectation about the relation between the inputs and the outputs.

> BTW, any logical formalism forces you to pay attention to meaning

I never said types are the only way. For instance, you could use Hoare logic, but it's notoriously more difficult to use, precisely because it gives programs no a priori meaning.

Re: On Two Views of Computation in Computer Science

#118
post #114

Earlier quoted context omitted.

It 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 discipl…

> 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…

A couple of clear, encouraging, articles about how to use TLA and the benefits it provides would pay dividends (to both you and your readers) orders of magnitude greater than this obscure, roundabout, oblique approach.

> This confuses some people to believe that TLA+ doesn't support higher-order algorithms, when, in fact, it becomes a non-issue.

An article explaining this would be astonishingly interesting (and probably clarify this whole discussion).

Re: On Two Views of Computation in Computer Science

#119
post #44

Earlier quoted context omitted.

>In practice, people write their programs in a programming language. Some languages (e.g., C, Java, Lisp) only provide leaky abstractions, so programmers always have access to the internal representation of everything, to the detriment of modularity. But there are languages (e.g., Standard ML) that aren't hobbled in this way. ... writing a function that inspects the representation of an abstract type isn't “difficult…

> You're right that some languages simply lack certain capabilities, but that's an issue of access, not computation per se. Types determine what computations make sense. > If you're going to go that route, then yeah the CTT is false -- likewise, TMs can't see inside black holes, so they can't "compute" that either. Careful! I never said the CTT is false. I only said it guarantees nothing about functions whose type is…

>Types determine what computations make sense.

Types determine what the developer has certified as making sense. There can (and as far as we know, always does) exist an isomorphism between the higher-typed function that the developer has implemented and the TM-computable nat->nat.

So, a TM can "make sense" of the higher-order function, even when it only has the nat->nat type.

>Careful! I never said the CTT is false. I only said it guarantees nothing about functions whose type is anything other than `nat -> nat` (up to isomorphism).

And and I was saying that the CTT is equivalent to saying that there is an isomorphism between a TM-computable nat->nat and any function that can be computed at all.

>These are properties of programs, not functions. Two syntactically different programs may compute the same function, so you can't conflate programs with functions (and hope to make sense).

Fair enough -- I should have said "function" there but the point stands: you can't refute by CTT by defining Turing-complete language that lacks some critical access and say, "well, that's a function I guess it can't compute!"

Re: On Two Views of Computation in Computer Science

#120
post #114

Earlier quoted context omitted.

It 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 discipl…

> 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…

That PLers, as Lamport writes in his comment on my post, fail to see that Plotkin's SOS is an abstract state machine

Is this even true? I don't think I've ever met a PLer who didn't know that an operational semantics describes an abstract machine.

Post reply on HN