• DocumentCode
    2204373
  • Title

    Computational complexity of recursive sequnces

  • Author

    Hartmanis, J. ; Stearns, R.E.

  • fYear
    1964
  • fDate
    11-13 Nov. 1964
  • Firstpage
    82
  • Lastpage
    90
  • Abstract
    In this paper we investigate how numbers, functions, and sequences can be classified according to their computational complexity. The computational complexity is measured by how fast the number or function can be computed by a multitape computer (Turing machine). It is shown that by means of this measure the computational complexity of numbers and functions can be submitted to rigorous mathematical study and a number of results are obtained.
  • Keywords
    Computational complexity; Laboratories; Turing machines;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Switching Circuit Theory and Logical Design, 1964 Proceedings of the Fifth Annual Symposium on
  • Conference_Location
    Princeton, NJ, USA
  • Type

    conf

  • DOI
    10.1109/SWCT.1964.6
  • Filename
    4569809
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2204373