Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: computable analysis

Sortuj według:

Ogranicz wyniki do:

Physical Computational Complexity and First-order Logic

Whyman Richard

Fundamenta Informaticae

2021

Vol. 181, nr 2-3

129--161

We present the concept of a theory machine, which is an atemporal computational formalism that is deployable within an arbitrary logical system. Theory machines are intended to capture computation on an arbitrary system, both physical and unphysical, including quantum computers, Blum-Shub-Smale machines, and infinite time Turing machines. We demonstrate that for finite problems, the computational power of any device characterisable by a finite first-order theory machine is equivalent to that of a Turing machine. Whereas for infinite problems, their computational power is equivalent to that of a type-2 machine. We then develop a concept of complexity for theory machines, and prove that the class of problems decidable by a finite first order theory machine with polynomial resources is equal to 𝒩𝒫 ∩ co-𝒩𝒫.

Randomness with Respect to the Signed-Digit Representation

Archibald M., Brattka V., Heuberger C.

Fundamenta Informaticae

2008

Vol. 83, nr 1-2

1-19

The ordinary notion of algorithmic randomness of reals can be characterised as Martin-Löf randomness with respect to the Lebesgue measure or as Kolmogorov randomness with respect to the binary representation. In this paper we study the question of how the notion of algorithmic randomness induced by the signed-digit representation of the real numbers is related to the ordinary notion of algorithmic randomness. We first consider the image measure on real numbers induced by the signed-digit representation. We call this measure the signed-digit measure and using the Fourier transform of this measure and the Riemann-Lebesgue Lemma we prove that this measure is not absolutely continuous with respect to the Lebesgue measure. We also show that the signed-digit measure can be obtained as a weakly convergent convolution of discrete measures and therefore, by the classical Theorem of Jessen and Wintner the Lebesgue measure is not absolutely continuous with respect to the signed-digit measure. Finally, we provide an invariance theorem which shows that if a computable map preserves Martin-Löf randomness, then its induced image measure has to be absolutely continuous with respect to the target space measure. This theorem can be considered as a loose analog for randomness of the Banach-Mazur theorem for computability. Using this Invariance Theorem we conclude that the notion of randomness induced by the signed-digit representation is incomparable with the ordinary notion of randomness.