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:
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.
Copyright © 2017, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds