2013/11/04 by Kojiro Higuchi, W. M. Phillip Hudelson, Higuchi, Kojiro +5
Computer Science · Mathematics · #03C62 #03F30 #03H15 #68Q30 #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #Primary 03D32 #Secondary 03D28 #math.LO #msc:03C62 #msc:03D28 #msc:03D32 #msc:03F30 #msc:03H15 #msc:68Q30 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1311.0724
27 pages. A version of this paper will appear in Annals of Pure and Applied Logic
arxiv created 2013/11/04 · openalex publication_date 2013/11/04 · arxiv updated 2013/11/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let f be a computable function from finite sequences of 0's and 1's to real numbers. We prove that strong f-randomness implies strong f-randomness relative to a PA-degree. We also prove: if X is strongly f-random and Turing reducible to Y where Y is Martin-L"of random relative to Z, then X is strongly f-random relative to Z. In addition, we prove analogous propagation results for other notions of partial randomness, including non-K-triviality and autocomplexity. We prove that f-randomness relative to a PA-degree implies strong f-randomness, hence f-randomness does not imply f-randomness relative to a PA-degree.