On the computability of Walsh functions. (Q1607297): Difference between revisions

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,\ldots}}\) 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 \((\Omega,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 \(d_{F}.\) It is proved that a uniformly Fine-computable function is essentially a computable function on \(\Omega\). 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.\).