We prove the existence of a manifold of exact solutions (mean-square error E = 0) of weights and thresholds for sigmoidal networks for XOR and other 2-variable Boolean functions. We also prove the existence of a manifold of local minima of E where E ≠ 0.

Much of the research on semantic theories has concentrated on qualitative properties such as definability (of such programming concepts as recursive procedures), equivalence (of different language constructs), and verifiability (of the correctness, or consistency, of one expression relative to another). Current qualitative theories are in a tentative state and much remains to be done. However, there is also a quantitative side to semantics. Indeed, many of the questions which any semantic theory must answer are at once qualitative and quantitative. We would like to draw upon complexity-theoretic techniques to answer such questions. We are currently working on the development of new algebraic constructs to provide a mathematical framework for both qualitative and quantitative analysis of semantic problems.

The concept of imbedding a programming language L into a formal system is introduced and used as the basis of defining the semantics Θ of the language. Θ is an operator which maps a program p in L onto a function. The pair (L, Θ) is called a programming system. If (L, Θ) and (L,' Θ') are two programming systems, a mapping Γ from L into L' is called a compiler. A compiler is said to be correct if Θ'(Γ(p)) = Θ(p) for p in L. These ideas are illustrated in terms of two programming systems, one for recursive functions and the other for Turing machines.

A formal system is presented for the differentiation of mathematical formulas which can be implemented on a digital computer. The system departs in concept from others in that the programming language is nonprocedural, permitting the statement of the problem for the machine to more closely resemble the corresponding statement for the human. Although limited ostensibly to the narrow and well-defined problem of mechanizing differentiation, many of the ideas and techniques presented can be applied in the broader context of the deeper problem of mechanizing mathematics. They should also be useful in programming theory, where the fundamental problem continues to be the narrowing of the gap between a natural language statement of a problem and a formal language statement acceptable to a computer.

Let ƒ ( x ) be a real-valued function defined and continuous on [- 1, +1] and let T ( x ) = a 0 /2 + Σ ∞ k =1 a k T k ( x ) be the Fourier-Tschebycheff expansion for ƒ ( x ), that is, T k ( x ) = cos klθ , a k = 2/π ∫ π 0 ƒ (cos θ ) cos kθ dθ where x = cos θ . If P n is the class of real polynomials in x of degree less than or equal to n , we let M n = inf pϵPn sup -1≤ x ≤1 | ƒ ( x ) - p ( x ) |. M n is called the best Tschebycheff approximation to ƒ ( x ) by a polynomial of degree less than or equal to n .