𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Refined Model of Computation for Continuous Problems

✍ Scribed by Klaus Weihrauch


Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
160 KB
Volume
14
Category
Article
ISSN
0885-064X

No coin nor oath required. For personal study only.

✦ Synopsis


The real-number model of computation is used in computational geometry, in the approach suggested by Blum, Shub, and Smale and in information based complexity.

In this paper we propose a refinement of this model, the TTE-model of computation. In contrast to the real-number model, which is unrealistic or at least too optimistic, the TTE-model is very realistic; i.e., for TTE-algorithms there are digital computers, which behave exactly the same way as predicted by the theoretical model. We start with a detailed discussion of some objections to the real-number model. We introduce the refined model by adding the condition "every partial input or output information of an algorithm is finite" to the assumptions of the IBC-model of computation. First, we explain computability and computational complexity in TTE for the simple case of real functions. Then we apply the refined model to two typical IBC-problems, integration and zero-finding on the space C [0; 1] of continuous real functions. We study computability and computational complexity and compare TTE-results with IBC-results. Finally, we briefly discuss the computation of discontinuous problems. This paper does not present new technical results but should be considered as a fresh impetus to reflect on models of computation for numerical analysis and as an invitation to try out the TTE-model of computation in information based complexity.


πŸ“œ SIMILAR VOLUMES


A model for iterative computation
✍ D. Tsichritzis πŸ“‚ Article πŸ“… 1973 πŸ› Elsevier Science 🌐 English βš– 596 KB
A refined index of model performance
✍ Cort J. Willmott; Scott M. Robeson; Kenji Matsuura πŸ“‚ Article πŸ“… 2011 πŸ› John Wiley and Sons 🌐 English βš– 354 KB

## Abstract In this paper, we develop, present and evaluate a refined, statistical index of model performance. This β€˜new’ measure (__d__~r~) is a reformulation of Willmott's index of agreement, which was developed in the 1980s. It (__d__~r~) is dimensionless, bounded by βˆ’ 1.0 and 1.0 and, in genera