A Computable Kolmogorov Superposition Theorem

Vasco Brattka, in: Computability and Complexity in Analysis, Informatik Berichte 272, FernUniversität Hagen, 7-22, 2000


In the year 1900 in his famous lecture in Paris Hilbert formulated 23 challenging problems which inspired many ground breaking mathematical investigations in the last century. Among these problems the 13th was concerned with the solution of higher order algebraic equations. Hilbert conjectured that such equations are not solvable by functions which can be constructed as substitution of continuous functions of only two variables. Surprisingly, 57 years later Hilbert's conjecture was refuted when Kolmogorov succeeded to prove his Superposition Theorem which states that each multivariate continuous real-valued function can be represented as superposition and composition of continuous functions of only one variable. Again 30 years later this theorem got an interesting application in the theory of neural networks. We will prove a computable version of Kolmogorov's Superposition Theorem in the rigorous framework of computable analysis: each multivariate computable real-valued function can be represented as superposition and composition of computable real number functions of only one variable and such a representation can even be determined effectively. As a consequence one obtains a characterization of the computational power of feedforward neural networks with computable activation functions and weights.

Electronical Versions

© 2000 Vasco Brattka, FernUniversität Hagen