Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Size Arguments in the Study of Computation Speeds

Size Arguments in the Study of Computation Speeds

File(s)
70-73.ps (527.51 KB)
70-73.pdf (1.19 MB)
Permanent Link(s)
https://hdl.handle.net/1813/5932
Collections
Computer Science Technical Reports
Hartmanis, Juris
Author
Hartmanis, Juris
Abstract

In this paper we use arguments about the size of the computed functions to investigate the computation speed of Turing machines. It turns out that the size arguments yield several new results which we have not been able to obtain previously by diagonalization. For example, we show that for arbitrarily complex running times $T(n)$ there exist functions which can be computed on a one-tape Turing machine in time $T(n)$ but not in time $t(n)$ provided $\stackrel{\lim}{n \rightarrow \infty} \frac{t(n)}{T(n)}=0$. The same result is also shown to hold for many-tape machines. We show furthermore, that there exist arbitrarily complex computations for which one-tape machines are slower than two-tape machines by a factor equal to the logarithm of the computation time of the two-tape machine. We conclude by discussing several other computational complexity measures and compare results obtained by diagonalization and size arguments.

Date Issued
1970-08
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR70-73
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance