Thanks for the heads up [LWN.net]

Thanks for the heads up

Posted Mar 31, 2005 23:20 UTC (Thu) by dvdeug (subscriber, #10998)
In reply to: Thanks for the heads up by iabervon
Parent article: Unexpected features in Acrobat 7

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.

(Log in to post comments)

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.