We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
On the Necessity of Formal Models for Real-Time Parallel Computations.
- Authors
Bruda, Stefan D.; Akl, Selim G.; Baker, J.
- Abstract
We assume the multitape real-time Turing machine as a formal model for parallel real-time computation. Then, we show that, for any positive integer k, there is at least one language L[sub k] which is accepted by a k-tape real-time Turing machine, but cannot be accepted by a (k - 1)-tape real-time Turing machine. It follows therefore that the languages accepted by real-time Turing machines form an infinite hierarchy with respect to the number of tapes used. Although this result was previously obtained elsewhere, our proof is considerably shorter, and explicitly builds the languages L[sub k]. The ability of the real-time Turing machine to model practical real-time and/or parallel computations is open to debate. Nevertheless, our result shows how a complexity theory based on a formal model can draw interesting results that are of more general nature than those derived from examples. Thus, we hope to offer a motivation for looking into realistic parallel real-time models of computation.
- Subjects
REAL-time clocks (Computers); PROGRAMMING languages
- Publication
Parallel Processing Letters, 2001, Vol 11, Issue 2/3, p353
- ISSN
0129-6264
- Publication type
Article
- DOI
10.1142/S0129626401000646