Normality, Relativization, and Randomness

Calvert, Wesley ; Gruner, Emma ; Mayordomo, Elvira (Universidad de Zaragoza) ; Turetsky, Daniel ; Villano, Java Darleen

Resumen: Normal numbers were introduced by Borel and later proven to be a weak notion of algorithmic randomness. We introduce here a natural relativization of normality based on generalized number representation systems. We explore the concepts of supernormal numbers that correspond to semicomputable relativizations, and that of highly normal numbers in terms of computable ones. We prove several properties of these new randomness concepts. Both supernormality and high normality generalize Borel absolute normality. Supernormality is strictly between 2-randomness and effective dimension 1, while high normality corresponds exactly to sequences of computable dimension 1 providing a more natural characterization of this class.

Idioma: Inglés

DOI: 10.1007/s00224-025-10227-w

Año: 2025

Publicado en: THEORY OF COMPUTING SYSTEMS 69, 3 (2025), [16 pp.]
ISSN: 1432-4350

Financiación: info:eu-repo/grantAgreement/ES/DGA/T64-20R
Financiación: info:eu-repo/grantAgreement/ES/MICINN/PID2019-104358RB-I00
Financiación: info:eu-repo/grantAgreement/ES/MICINN/PID2022-138703OB-I00

Tipo y forma: Artículo (Versión definitiva)

Área (Departamento): Área Lenguajes y Sistemas Inf. (Dpto. Informát.Ingenie.Sistms.)