Problems in the Theory of Computation. AIM-028
The purpose of this paper is to identify and discuss a number of
theoretical problems whose solutions seem feasible and likely to
advance the practical art of computation. The problems that will be
discussed include the following:
1. Semantics of programming languages. What do the strings of
symbols representing computer programs, statements, declarations,
labels, etc., denote? How can the semantics of programming
languages be described formally?
2. Data spaces. What are the spaces of data on which computer
programs act and how are they built up up from simpler spaces?
3. How can time dependent and simultaneous processes be described?
4. Speed of computation. What can be said about how much
computation is required to carry out certain processes?
5. Storage of information. How can information be stored so that
items identical or similar to a given item can be retrieved?
6. Syntax directed computation. What is the appropriate domain for
computations described by productions or other data format
7. What are the appropriate formalisms for writing
proofs that computer programs are equivalent?
8. In the view of Godel's theorem that tells us that any formal
theory of computation must be incomplete, what is a reasonable
formal system that will enable us to prove that programs terminate
in practical cases?
|Type of resource
|1 text file
|McCarthy, John, 1927-2011
|Stanford Artificial Intelligence Laboratory
|Memo (Stanford Artificial Intelligence Laboratory)
|Stanford University. Libraries. Department of Special Collections and University Archives
- Use and reproduction
- The materials are open for research use and may be used freely for non-commercial purposes with an attribution. For commercial permission requests, please contact the Stanford University Archives (firstname.lastname@example.org).
- Copyright © The Board of Trustees of the Leland Stanford Junior University. All rights reserved.
Stanford Artificial Intelligence Laboratory records, 1963-2009View other items in this collection in SearchWorks
Also listed in
Loading usage metrics...