Problems in the Theory of Computation. AIM028
 Title:
 Problems in the Theory of Computation. AIM028
 Author:
 McCarthy, John, 19272011
 Author (no Collectors):
 McCarthy, John, 19272011
 Collector:
 McCarthy, John, 19272011
 Description:

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
recognizers?
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?
 Topic:
 Artificial intelligence
 Subject:
 Stanford Artificial Intelligence Laboratory and Memo (Stanford Artificial Intelligence Laboratory)
 Language:
 English
 Physical Description:
 1 text file
 Publication Info:
 Stanford (Calif.) and cau
 Date:
 March 1965
 Place created:
 Stanford (Calif.)
 Imprint:
 Stanford (Calif.), March 1965
 Genre:
 memorandums
 Identifier:
 AIM028
 Repository:
 Stanford University. Libraries. Department of Special Collections and University Archives
 Collection:
 Stanford Artificial Intelligence Laboratory records, 19632009
 Manuscript number:
 SC1041