article · Parallel Processing Letters · 2001

ON THE NECESSITY OF FORMAL MODELS FOR REAL-TIME PARALLEL COMPUTATIONS

Cited by 6Abstract and details only

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 k which is accepted by a k-tape real-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 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.

Cite this paper

APA 7

Bruda, S. D., & Akl, S. G. (2001). ON THE NECESSITY OF FORMAL MODELS FOR REAL-TIME PARALLEL COMPUTATIONS. Parallel Processing Letters, 11(02n03), 353–361. https://doi.org/10.1142/s0129626401000646

MLA 9

Bruda, Stefan D., and Selim G. Akl. “ON THE NECESSITY OF FORMAL MODELS FOR REAL-TIME PARALLEL COMPUTATIONS.” Parallel Processing Letters, vol. 11, no. 02n03, 2001, pp. 353–61, https://doi.org/10.1142/s0129626401000646.

Chicago

Bruda, Stefan D., and Selim G. Akl. 2001. “ON THE NECESSITY OF FORMAL MODELS FOR REAL-TIME PARALLEL COMPUTATIONS.” Parallel Processing Letters 11 (02n03): 353–61. https://doi.org/10.1142/s0129626401000646.

Harvard

Bruda, S.D. and Akl, S.G. (2001) ‘ON THE NECESSITY OF FORMAL MODELS FOR REAL-TIME PARALLEL COMPUTATIONS’, Parallel Processing Letters, 11(02n03), pp. 353–361. Available at: https://doi.org/10.1142/s0129626401000646.

BibTeX

@article{bruda2001necessity,
  title = {{ON THE NECESSITY OF FORMAL MODELS FOR REAL-TIME PARALLEL COMPUTATIONS}},
  author = {Bruda, Stefan D. and Akl, Selim G.},
  journal = {Parallel Processing Letters},
  volume = {11},
  number = {02n03},
  pages = {353--361},
  year = {2001},
  doi = {10.1142/s0129626401000646}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.