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.