On the computability of Walsh functions

The Haar and the Walsh functions are proved to be computable with respect to the Fine-metric d(F) which is induced from the infinite product Omega = {0,1}{(1,2,...}) with the weighted product metric d(C) of the discrete metric on {0, 1}. Although they are discontinuous functions on [0, 1] with respect to the Euclidean metric, they are continuous functions on (Omega, d(C)) and on ([0, 1], d(F)). On (Q, d(C)), computable real-valued cylinder functions, which include the Walsh functions, become computable and every computable function can be approximated effectively by a computable sequence of cylinder functions. The metric space ([0, 1], d(F)) is separable but not complete nor effectively complete. We say that a function on [0, 1] is uniformly Fine-computable if it is sequentially computable and effectively uniformly continuous with respect to the metric dF. It is proved that a uniformly Fine-computable function is essentially a computable function on Q. It is also proved that Walsh-Fourier coefficients of a uniformly Fine-computable function f form a computable sequence of reals and there exists a subsequence of the Walsh-Fourier series which Fine-converges effectively uniformly to f. (C) 2002 Elsevier Science B.V. All rights reserved.