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
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?