3 ms·
> There are no computational models of any wide utility -- no matter how limited -- that we can feasibly reason about in the general case. I gave you an exampl
by vidarh 9y ago
> There are no computational models of any wide utility -- no matter how limited -- that we can feasibly reason about in the general case.
I gave you an example: Sieve.
> If you have no loops (even bounded by a depth of 2) and no subroutines or no variables -- then verification is feasible, otherwise it is at least PSPACE-hard. Such languages may be useful for something, but obviously the vast majority of tasks cannot be done in them.
Sieve, as I mentioned fits in this category (though I'd not be surprised if there are extensions that break this; there are many, but the basic language is sufficiently constrained and still useful).
The point is not to do "the vast majority of tasks" in them, but that a wide range of tasks are constrained enough to achievable within different sets of such models, and this is a common way of seeking to contain computational complexity that works well when it is done by care.
(... but leads to unexpected Turing completeness now and again when people don't take care, as the article points out)
E.g. aforementioned Sieve is constrained this way explicitly to be safe to let end-users -- or scripts on their behalf -- construct Sieve filters to run during delivery on mail servers without e.g. having to impose any other restrictions than a size limit.
> This is provably impossible unless your don't mind your programs being as long as the worst-case time complexity that they solve.
I think you misunderstood what I wrote. The sentence you quoted here is arguing that people make mistakes when defining the kind of restricted languages I'm discussing all the time so that verification gets harder. You seem to think it was talking about making verification easier.
> In general, the idea that a weaker computational model makes reasoning easy is a myth
And again: This is flat out wrong without adding the caveat that you're talking about arbitrary computation rather than languages that are specifically and intentionally constructed to prevent arbitrary computation.
Here's one:
Consider a machine whose only instruction is "halt", which halts execution.
Clearly this model is trivial to reason about. You may intend a "useful" in there somewhere, in which case I point you again to Sieve, which is still trivial enough unless you carelessly add extensions.
- pron 9y ago> I gave you an example: Sieve. I said "of wide utility". BTW, I don't know Sieve, but if it has regular expressions then reasoning about it is also infeasible (e.g. checking whether two filters based on regular expressions are equivalent). > but that a wide range of tasks are constrained enough to achievable within different sets of such models, and this is a common way of seeking to contain computational complexity that works well when it is done by care. I don't know what "a wide range of tasks" means, but even regular expressions are not limited enough for general reasoning. Anything that requires regular expressions and beyond is already infeasibly verified in the general case. > This is flat out wrong without adding the caveat that you're talking about arbitrary computation rather than languages that are specifically and intentionally constructed to prevent arbitrary computation. No. I'm talking about arbitrary programs in whatever language you give me. If your language has regular expressions -- game over. If it has variables and subroutines/limited loops -- game over. And those are just the PSPACE-hard cases. If all you have in your language is boolean connectives (i.e., it's a propositional calculus) -- no subroutines, no loops and no mutable variables -- verifying it is "just" NP-hard. Special cases, on the other hand, are often possible to reason about even automatically even in Turing complete languages. > You may intend a "useful" in there somewhere, in which case I point you again to Sieve, which is still trivial enough unless you carelessly add extensions. I did say useful, and either Sieve is not very widely applicable and/or, if it has regular expressions it cannot be feasibly reasoned about.
- vidarh 9y ago> I said "of wide utility". And they are of wide utility, even though they may not satisfy your expectations to just how wide utility you want. But that is exactly the point - they're not meant to. The claim I made, and that others here have made, that you've been arguing against is not about general purpose languages. I've pointed that out several times. On the contrary the point is explicitly that there are benefits in isolating parts of problems and explicitly avoiding general purpose languages exactly because I agree that you won't gain much from trying to find weaker models for general purpose languages. So when you keep bringing up more general computation, you keep arguing against a point I at least have not made. I've never disputed that there is little to gain from trying to weaken the computational models for general purpose computation. What we can do, and often do is to reduce the practical problems of working on these systems by lifting subsets of problems out of general purpose languages and into much weaker special purpose environments. Since you keep bringing up regular expressions, for example: > but if it has regular expressions then reasoning about it is also infeasible ... this is exactly one of the reasons why Sieve doesn't have them (at least not the base language) - it's limited to basic wildcards ("","?", specific strings). On top of that the implementation is allowed to terminate execution after an implementation defined number of execution steps, so it does not need to even deal with the worst case for a wildcard engine if someone tries to feed it pathological strings. > I don't know what "a wide range of tasks" means, but even regular expressions are not limited enough for general reasoning. Anything that requires regular expressions and beyond is already infeasibly verified in the general case. I've repeatedly pointed out that the entire goal of these languages is to prevent* general reasoning. That is a feature, not a flaw. > No. I'm talking about arbitrary programs in whatever language you give me. ... in which case you're not addressing the comments of mine that you've replied to, and we're in violent agreement about something that is irrelevant to my argument.
- pron 9y ago> What we can do, and often do is to reduce the practical problems of working on these systems by lifting subsets of problems out of general purpose languages and into much weaker special purpose environments. A language that has no variables, no loops and no subroutines (and no regexps) is as far as you can go while remaining feasibly verifiable. There aren't many other options. What portion of our applications can be written in such languages? That people add extensions to Sieve only shows that its trusted portion isn't widely-enough useful even for the task of filtering email. It's not a question of general-purpose vs. DSL. Regardless of what the language is for, with no loop, subroutines and variables there is very little you can do. > I've repeatedly pointed out that the entire goal of these languages is to prevent* general reasoning. That is a feature, not a flaw. It's not important, but that's not what I meant by general reasoning or arbitrary computation. What I meant is that no matter the language you give me (assuming it's useful enough etc.), answering arbitrary questions about arbitrary programs in that language is not feasible. For example, regular expressions do not allow "arbitrary computation" in the Turing completeness sense, yet it is infeasible to feasibly answer arbitrary questions about arbitrary regular expressions, such as the question "are two regular expressions equivalent?" This is a very important question about regular expressions, but it cannot be feasibly answered for arbitrary regular expressions.