Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: Computational Complexity of Random Access Stored Program Machines
Authors: Hartmanis, Juris
Keywords: computer science
technical report
Issue Date: Aug-1970
Publisher: Cornell University
Abstract: In this paper we explore the computational complexity measure defined by running times of programs on random access stored program machines, RASP'S. The purpose of this work is to study more realistic complexity measures and to provide a setting and some techniques to explore different computer organizations. The more interesting results of this paper are obtained by an argument about the size of the computed functions. For example, we show (without using diagonalization) that there exist arbitrarily complex functions with optimal RASP programs whose running time cannot be improved by any multiplicative constant. We show, furthermore, that these optimal programs cannot be fixed prodecures and self-modifying programs. The same technique is used to compare computation speed of machines with and without built in multiplication. We conclude the paper with a look at machines with associative memory and distributed logic machines.
Appears in Collections:Computer Science Technical Reports
Hartmanis, Juris

Files in This Item:

File Description SizeFormat
70-70.pdf1.66 MBAdobe PDFView/Open
70-70.ps456.52 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us