Sub-computable Boundedness Randomness
This paper defines a new notion of bounded computable randomness for certain classes of sub-computable functions which lack a universal machine. In particular, we define such versions of randomness for primitive recursive functions and for PSPACE functions. These new notions are robust in that there...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2014-12-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/979/pdf |
| _version_ | 1797268610308112384 |
|---|---|
| author | Sam Buss Douglas Cenzer Jeffrey B. Remmel |
| author_facet | Sam Buss Douglas Cenzer Jeffrey B. Remmel |
| author_sort | Sam Buss |
| collection | DOAJ |
| description | This paper defines a new notion of bounded computable randomness for certain
classes of sub-computable functions which lack a universal machine. In
particular, we define such versions of randomness for primitive recursive
functions and for PSPACE functions. These new notions are robust in that there
are equivalent formulations in terms of (1) Martin-L\"of tests, (2) Kolmogorov
complexity, and (3) martingales. We show these notions can be equivalently
defined with prefix-free Kolmogorov complexity. We prove that one direction of
van Lambalgen's theorem holds for relative computability, but the other
direction fails. We discuss statistical properties of these notions of
randomness. |
| first_indexed | 2024-04-25T01:35:13Z |
| format | Article |
| id | doaj.art-1c87cf73aa5c4752ac4bb27d07fae3e2 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:35:13Z |
| publishDate | 2014-12-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-1c87cf73aa5c4752ac4bb27d07fae3e22024-03-08T09:37:58ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742014-12-01Volume 10, Issue 410.2168/LMCS-10(4:15)2014979Sub-computable Boundedness RandomnessSam BussDouglas CenzerJeffrey B. RemmelThis paper defines a new notion of bounded computable randomness for certain classes of sub-computable functions which lack a universal machine. In particular, we define such versions of randomness for primitive recursive functions and for PSPACE functions. These new notions are robust in that there are equivalent formulations in terms of (1) Martin-L\"of tests, (2) Kolmogorov complexity, and (3) martingales. We show these notions can be equivalently defined with prefix-free Kolmogorov complexity. We prove that one direction of van Lambalgen's theorem holds for relative computability, but the other direction fails. We discuss statistical properties of these notions of randomness.https://lmcs.episciences.org/979/pdfcomputer science - logic in computer science |
| spellingShingle | Sam Buss Douglas Cenzer Jeffrey B. Remmel Sub-computable Boundedness Randomness Logical Methods in Computer Science computer science - logic in computer science |
| title | Sub-computable Boundedness Randomness |
| title_full | Sub-computable Boundedness Randomness |
| title_fullStr | Sub-computable Boundedness Randomness |
| title_full_unstemmed | Sub-computable Boundedness Randomness |
| title_short | Sub-computable Boundedness Randomness |
| title_sort | sub computable boundedness randomness |
| topic | computer science - logic in computer science |
| url | https://lmcs.episciences.org/979/pdf |
| work_keys_str_mv | AT sambuss subcomputableboundednessrandomness AT douglascenzer subcomputableboundednessrandomness AT jeffreybremmel subcomputableboundednessrandomness |