Normality, Relativization, and Randomness.
Saved in:
| Title: | Normality, Relativization, and Randomness. |
|---|---|
| Authors: | Calvert, Wesley1 (AUTHOR) wcalvert@siu.edu, Gruner, Emma2 (AUTHOR) eeg67@psu.edu, Mayordomo, Elvira3 (AUTHOR) elvira@unizar.es, Turetsky, Daniel4 (AUTHOR) dan.turetsky@vuw.ac.nz, Villano, Java Darleen5 (AUTHOR) javavill@uconn.edu |
| Source: | Theory of Computing Systems. Sep2025, Vol. 69 Issue 3, p1-16. 16p. |
| Subjects: | Algorithmic randomness, Random numbers, Computational complexity, Number systems |
| Abstract: | 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. [ABSTRACT FROM AUTHOR] |
| Copyright of Theory of Computing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 186103713 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Normality, Relativization, and Randomness. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Calvert%2C+Wesley%22">Calvert, Wesley</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> wcalvert@siu.edu</i><br /><searchLink fieldCode="AR" term="%22Gruner%2C+Emma%22">Gruner, Emma</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> eeg67@psu.edu</i><br /><searchLink fieldCode="AR" term="%22Mayordomo%2C+Elvira%22">Mayordomo, Elvira</searchLink><relatesTo>3</relatesTo> (AUTHOR)<i> elvira@unizar.es</i><br /><searchLink fieldCode="AR" term="%22Turetsky%2C+Daniel%22">Turetsky, Daniel</searchLink><relatesTo>4</relatesTo> (AUTHOR)<i> dan.turetsky@vuw.ac.nz</i><br /><searchLink fieldCode="AR" term="%22Villano%2C+Java+Darleen%22">Villano, Java Darleen</searchLink><relatesTo>5</relatesTo> (AUTHOR)<i> javavill@uconn.edu</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Theory+of+Computing+Systems%22">Theory of Computing Systems</searchLink>. Sep2025, Vol. 69 Issue 3, p1-16. 16p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Algorithmic+randomness%22">Algorithmic randomness</searchLink><br /><searchLink fieldCode="DE" term="%22Random+numbers%22">Random numbers</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+complexity%22">Computational complexity</searchLink><br /><searchLink fieldCode="DE" term="%22Number+systems%22">Number systems</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Theory of Computing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=186103713 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s00224-025-10227-w Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 16 StartPage: 1 Subjects: – SubjectFull: Algorithmic randomness Type: general – SubjectFull: Random numbers Type: general – SubjectFull: Computational complexity Type: general – SubjectFull: Number systems Type: general Titles: – TitleFull: Normality, Relativization, and Randomness. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Calvert, Wesley – PersonEntity: Name: NameFull: Gruner, Emma – PersonEntity: Name: NameFull: Mayordomo, Elvira – PersonEntity: Name: NameFull: Turetsky, Daniel – PersonEntity: Name: NameFull: Villano, Java Darleen IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 09 Text: Sep2025 Type: published Y: 2025 Identifiers: – Type: issn-print Value: 14324350 Numbering: – Type: volume Value: 69 – Type: issue Value: 3 Titles: – TitleFull: Theory of Computing Systems Type: main |
| ResultId | 1 |
