{"@context":["https://w3id.org/fdo/context/v1",{"schema":"https://schema.org/","prov":"http://www.w3.org/ns/prov#","fdo":"https://w3id.org/fdo/vocabulary/"}],"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q688792","@type":"DigitalObject","kernel":{"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q688792","digitalObjectType":"https://schema.org/ScholarlyArticle","primaryIdentifier":"mardi:Q688792","kernelVersion":"v1","immutable":true,"modified":"2025-12-31T23:58:10Z"},"profile":{"@context":"https://schema.org","@type":"ScholarlyArticle","@id":"https://portal.mardi4nfdi.de/entity/Q688792","name":"On relative randomness","headline":"On relative randomness","description":"scientific article; zbMATH DE number 438515","url":"https://portal.mardi4nfdi.de/entity/Q688792","datePublished":"1994-06-02","author":[{"@id":"https://portal.mardi4nfdi.de/entity/Q277528"}],"publisher":[{"@id":"https://portal.mardi4nfdi.de/entity/Q122505"}],"identifier":{"@type":"PropertyValue","propertyID":"doi","value":"10.1016/0168-0072(93)90209-V","url":"https://doi.org/10.1016/0168-0072(93)90209-V"},"sameAs":["https://doi.org/10.1016/0168-0072(93)90209-V"],"comment":"In algorithmic complexity theory, an element is declared random iff it does not belong to any constructive set of measure 0. In particular, ``relative'' randomness is defined as follows. Assume that an infinite binary sequence \\(\\alpha\\) is given. By an \\(\\alpha\\)-algorithm, we mean an algorithm that uses \\(\\alpha\\) as an oracle. An interval \\(I\\) on a set of all binary sequences is a set of all sequences \\(\\beta\\) that start with a given finite sequence \\(\\beta_ 1 \\dots \\beta_ p\\). The measure \\(\\mu\\) is defined as follows: for each interval \\(I\\) determined by a sequence \\(\\beta_ 1 \\dots \\beta_ p\\), the measure \\(\\mu(I)\\) of this intervals is \\(2^{-p}\\). We say that a set \\(S\\) of infinite binary sequences has \\(\\alpha\\)-constructive measure 0, if there exists an \\(\\alpha\\)-algorithm that for every \\(n\\), generates a sequence \\(I_{mn}\\) of intervals such that \\(S \\subseteq I_ n=\\cup_ mI_{mn}\\), and \\(\\mu(I_ n) \\leq 2^{- n}\\). A sequence \\(\\beta\\) is called \\(\\alpha\\)-random (or, to be more precise, \\(\\alpha-1\\)-random) if it does not belong to any set of \\(\\alpha\\)- constructive measure 0 (or, equivalently, for which the one-element set \\(\\{\\beta\\}\\) is not of \\(\\alpha\\)-constructive measure 0).   Crudely speaking, if \\(\\beta\\) is \\(\\alpha\\)-random, this means in particular, that knowing \\(\\alpha\\) will not help in computing \\(\\beta\\). A natural question is: does this also mean that knowing \\(\\beta\\) does not help in computing \\(\\alpha\\)? This question was raised by M. van Lambalgen and D. Zambella. The author provides the following answer: there exist \\(\\alpha\\) and \\(\\beta\\) such that \\(\\beta\\) is \\(\\alpha\\)-random while \\(\\alpha\\) is recursive in \\(\\beta\\). Other results on relative randomness are also proved.","citation":[{"@id":"https://portal.mardi4nfdi.de/entity/Q2709403"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3489987"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5677474"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3793412"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3758821"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4723720"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4732457"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3484822"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3764938"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5202179"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4385509"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5656214"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1188502"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4040892"}]},"provenance":{"prov:generatedAtTime":"2025-12-31T23:58:10Z","prov:wasAttributedTo":"MaRDI Knowledge Graph"}}