Thanks for the heads up [LWN.net]

Thanks for the heads up

Posted Mar 31, 2005 17:49 UTC (Thu) by iabervon (subscriber, #722) [Link]

Postscript, even without the procedural bits hacked out, doesn't really have an interaction model. So it would have to be substantially replaced anyway in order to be useful, and then there's still the fact that it's a stack language, which is an obscure class of language.

I suspect that xhtml, xforms, and a spreadsheet-style expression language would apply better to the actual useful applications, but people persist in going for Turing-complete solutions instead of more targetted ones.

Thanks for the heads up

Posted Mar 31, 2005 23:16 UTC (Thu) by gnb (subscriber, #5132) [Link]

>Postscript, even without the procedural bits hacked out, doesn't really
> have an interaction model.
There's Display PostScript, which addressed this long before Javascript.
But yes, the point about not really needing a Turing-complete language
in the first place is a good one.

Thanks for the heads up

Posted Mar 31, 2005 23:20 UTC (Thu) by dvdeug (subscriber, #10998) [Link]

A spreadsheet is Turing complete. Most useful forms of computation are Turing-complete; it really doesn't take that much to be, and if you aren't Turing-complete, you very quickly run into problems you want to solve that you can't. Even most Unix "regexs" aren't really computer science regular expressions; they're Turing-complete.

Thanks for the heads up

Posted Mar 31, 2005 23:30 UTC (Thu) by gnb (subscriber, #5132) [Link]

I'm not sure "useful" quite captures it. "Accessible" may be closer:
I've had explanations from computer scientists about how to solve a
problem in a language that's more limited, and yes the answer works,
but it usually requires far more cleverness than coming up with a
solution to the same problem in a Turing-complete language. That is, yes
Turing-completeness is often overkill, but it's overkill that makes
solving the problem so much _easier_.

Thanks for the heads up

Posted Apr 1, 2005 14:19 UTC (Fri) by iabervon (subscriber, #722) [Link]

If you require cell references to be acyclic, don't have document-defined functions or don't let them be recursive, and don't have unbounded looping constructs, it's obviously not Turing-complete, because every calculation has to halt. I think this is still sufficient for the applications people will expect to use a form for, assuming the library is satisfactory. I believe that the expectation would be that you have a form such that you could fill it out completely yourself (if you printed it out, for example), but some of the fields depend on other fields, and the software will fill in these fields for you if you fill in the necessary other fields.

Complicated as it is, the US tax code (for example) is written with constraints which make the language of potential tax codes not Turing-complete (not counting things you do to acquire the inputs to the tax code; the process of getting a 1099 from a bank may not terminate, but doing your taxes once you have all the necessary documents will). This is the sort of thing that people would like to automate: forward-only calculations with a finite number of steps and an acyclic inclusion of worksheets.

Thanks for the heads up

Posted Apr 1, 2005 7:02 UTC (Fri) by khim (subscriber, #9252) [Link]

:roll: It's not so easy to develop non-turing-complete system without artificial limits. DVD-Video is not turing-complete, for example. The reason is not obscurity of format but trivial fact that it only has limited number of registers (20 plus some special ones with user-visible effects).

This is turing-complete "langauge"!