On the complexity of online computations of real functions

✍ Scribed by Klaus Weihrauch

• Publisher: Elsevier Science
• Year: 1991
• Tongue: English
• Weight: 813 KB
• Volume: 7
• Category: Article
• ISSN: 0885-064X
• DOI: 10.1016/0885-064x(91)90026-t

✦ Synopsis

A reasonable computational complexity theory for real functions is obtained by using the modified infinite binary representation with digits 0, 1, and -1 for the real numbers and Turing machines which transform with one-way output modified binary input sequences into modified binary output sequences. As the main result of this paper it is shown that there is a trade-off between the input lookahead, i.e., the deviation of online computation and the computational complexity for machines computing certain real functions.