On the computability of Walsh functions.
type: Item
instance of: scholarly article
title: On the computability of Walsh functions.
zbMATH Open document ID: 1042.68048
DOI: 10.1016/S0304-3975(01)00099-8
author: Takakazu Mori
published in: Theoretical Computer Science
publication date: 2002-07-31T00:00:00Z
review text: 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.\).
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 1774170
zbMATH Keywords: Metric space with computability structure
zbMATH Keywords: Computable function
zbMATH Keywords: Dyadic group
zbMATH Keywords: Walsh function
zbMATH Keywords: Walsh-Fourier series
MaRDI profile type: Publication
cites work: Q5422248
cites work: The Generalized Walsh Functions
cites work: On the Walsh Functions
cites work: Q3999467
cites work: Q4217607
cites work: Q3994907
cites work: Q3997391
cites work: Q4546073
cites work: Effective properties of sets and functions in metric spaces with computability structure
cites work: An application of Walsh Fourier analysis to weakly stationary processes
cites work: Computability on computable metric spaces
cites work: Q4436366
description: scientific article; zbMATH DE number 1774170