Turing Award lecture on computational complexity and the nature of computer science

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Turing Award lecture on computational complexity and the nature of computer science

Full text

Pdf (1.10 MB)

Source

Communications of the ACM archive
Volume 37 , Issue 10 (October 1994) table of contents

Pages: 37 - 43

Year of Publication: 1994

ISSN:0001-0782

Author

Juris Hartmanis

Department of Computer Science, Cornell University, 5149 Upson Hall, Ithaca, NY

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 109, Citation Count: 8

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/194313.214781 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions, Journal of the ACM (JACM), v.14 n.2, p.322-336, April 1967 [doi>10.1145/321386.321395]
	2	Frederick P. Brooks, Jr., The mythical man-month (anniversary ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
	3	Juris Hartmanis , Herbert Lin, Computing the future: a broader agenda for computer science and engineering, National Academy Press, Washington, DC, 1992
	4	Juris Hartmanis, Some Observations About the Nature of Computer Science, Proceedings of the 13th Conference on Foundations of Software Technology and Theoretical Computer Science, p.1-12, December 15-17, 1993
	5	Hartmanis, J. and Stearns, R.E. On the computational complexity of algorithms. Trans Amer. Math. Soc., 177 (1965), 285-306.
	6	Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications, Springer-Verlag New York, Inc., New York, NY, 1993
	7	Lewis, P.M., Stearns, .R,E., and Hartmanis., .J. Memory bounds for the recognition for context-tree and context- sensitive languages. In Proceedings of IEEE Sixth ANNUALSym- posium on Switching Circuit theory and Logical Design.. (1965), pp. 191-202.
	8	Mccullach, W.S. A historical introduction to the postulational foundations of experimental epistemology. In Cross cultural Understanding.Epistemology in ANTROpoLogy, F.C.S, Northrop, and H.H.. Livingston, Eds., Harper and Row., New York, 1964
	9	John McCarthy, Mathematical logic in artificial intelligence, The artificial intelligence debate: false starts, real foundations, MIT Press, Cambridge, MA, 1989
	10	Savitch W.J. RelatiON ship between delcrnt in is tit: and determinisfic tape contplexities.J, c'omput. Syst. sci., 4. (1970), 177-192.
	11	Adi Shamir, IP = PSPACE, Journal of the ACM (JACM), v.39 n.4, p.869-877, Oct. 1992 [doi>10.1145/146585.146609]
	12	Shahnon, C. the mathematical Theory COmmunication. Bell System TECH. J. 2 7 (1948), 379-656,
	13	STearns, R,E ..... Hartmanis, J., and Lewis, P.M. Hierarchies of memory limited computations. In Proceeding, of IEEE Sixth Annual Symposium of Switching Circuit Theory and Logical Design. (1965), pp. 179-190.
	14	Turing, A.M. On computable numbers with an application to the Entscheidungaproblem Proceeding's of the London Mathematical Society, series 2, 42 (1936), 230-265.
	15	Yamada, H. Real-time computation and recursive functions not real-time Computable, IEEE Trans. Elec. Comput, 11, 6 (1962), 753-760.
	16	Younger, D.H. Recognition and parsing of context-free languages in time. n3. Information and Control 10, 2 (1967), 189-208.

CITED BY 8

	Binh Pham, The changing curriculum of computing and information technology in Australia, Proceedings of the 2nd Australasian conference on Computer science education, p.149-154, July 1997, The Univ. of Melbourne, Australia
	Faron Moller , Scott A. Smolka, On the computational complexity of bisimulation, redux, Proceedings of the Paris C. Kanellakis memorial workshop on Principles of computing & knowledge: Paris C. Kanellakis memorial workshop on the occasion of his 50th birthday, p.55-59, June 08-08, 2003, San Diego, California, USA
	Amr El-Kadi, Viewpoint: stop that divorce!, Communications of the ACM, v.42 n.12, p.27-28, Dec. 1999
	Walter F. Tichy, Should Computer Scientists Experiment More?, Computer, v.31 n.5, p.32-40, May 1998
	Faron Moller , Scott Smolka , Jiří Srba, On the computational complexity of bisimulation, redux, Information and Computation, v.194 n.2, p.129-143, November 1, 2004
	David R. Wright, Research ethics and computer science: an unconsummated marriage, Proceedings of the 24th annual conference on Design of communication, October 18-20, 2006, Myrtle Beach, SC, USA
	Jens Bennedssen , Michael E. Caspersen, Abstraction ability as an indicator of success for learning computing science?, Proceeding of the fourth international workshop on Computing education research, p.15-26, September 06-07, 2008, Sydney, Australia
	David P. Darcy , Chris F. Kemerer , Sandra A. Slaughter , James E. Tomayko, The Structural Complexity of Software: An Experimental Test, IEEE Transactions on Software Engineering, v.31 n.11, p.982-995, November 2005