Algorithmic randomness of continuous functions View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2008-05

AUTHORS

George Barmpalias, Paul Brodhead, Douglas Cenzer, Jeffrey B. Remmel, Rebecca Weber

ABSTRACT

We investigate notions of randomness in the space of continuous functions on . A probability measure is given and a version of the Martin-Löf test for randomness is defined. Random continuous functions exist, but no computable function can be random and no random function can map a computable real to a computable real. The image of a random continuous function is always a perfect set and hence uncountable. For any , there exists a random continuous function F with y in the image of F. Thus the image of a random continuous function need not be a random closed set. The set of zeroes of a random continuous function is always a random closed set. More... »

PAGES

533-546

References to SciGraph publications

  • 2006. Random Closed Sets in LOGICAL APPROACHES TO COMPUTATIONAL BARRIERS
  • 1919-03. Grundlagen der Wahrscheinlichkeitsrechnung in MATHEMATISCHE ZEITSCHRIFT
  • 1971-09. A unified approach to the definition of random sequences in MATHEMATICAL SYSTEMS THEORY
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00153-007-0060-4

    DOI

    http://dx.doi.org/10.1007/s00153-007-0060-4

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1032824312


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Leeds", 
              "id": "https://www.grid.ac/institutes/grid.9909.9", 
              "name": [
                "School of Mathematics, University of Leeds, Leeds, UK"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Barmpalias", 
            "givenName": "George", 
            "id": "sg:person.013527770623.53", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013527770623.53"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Florida", 
              "id": "https://www.grid.ac/institutes/grid.15276.37", 
              "name": [
                "Department of Mathematics, University of Florida, P.O. Box 118105, 32611-8105, Gainesville, FL, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Brodhead", 
            "givenName": "Paul", 
            "id": "sg:person.012444770271.80", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012444770271.80"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Florida", 
              "id": "https://www.grid.ac/institutes/grid.15276.37", 
              "name": [
                "Department of Mathematics, University of Florida, P.O. Box 118105, 32611-8105, Gainesville, FL, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Cenzer", 
            "givenName": "Douglas", 
            "id": "sg:person.014623655733.03", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014623655733.03"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of California, San Diego", 
              "id": "https://www.grid.ac/institutes/grid.266100.3", 
              "name": [
                "Department of Mathematics, University of California at San Diego, La Jolla, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Remmel", 
            "givenName": "Jeffrey B.", 
            "id": "sg:person.010700557277.48", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010700557277.48"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Dartmouth College", 
              "id": "https://www.grid.ac/institutes/grid.254880.3", 
              "name": [
                "Department of Mathematics, Dartmouth College, Hanover, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Weber", 
            "givenName": "Rebecca", 
            "id": "sg:person.010446316643.85", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010446316643.85"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf01203155", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001533942", 
              "https://doi.org/10.1007/bf01203155"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0019-9958(66)80018-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002020706"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(76)90005-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014131822"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01694181", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037526412", 
              "https://doi.org/10.1007/bf01694181"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01694181", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037526412", 
              "https://doi.org/10.1007/bf01694181"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01694181", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037526412", 
              "https://doi.org/10.1007/bf01694181"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11780342_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050561380", 
              "https://doi.org/10.1007/11780342_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11780342_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050561380", 
              "https://doi.org/10.1007/11780342_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2307/2586546", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053479348"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/logcom/exm033", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1059876091"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2008-05", 
        "datePublishedReg": "2008-05-01", 
        "description": "We investigate notions of randomness in the space of continuous functions on . A probability measure is given and a version of the Martin-L\u00f6f test for randomness is defined. Random continuous functions exist, but no computable function can be random and no random function can map a computable real to a computable real. The image of a random continuous function is always a perfect set and hence uncountable. For any , there exists a random continuous function F with y in the image of F. Thus the image of a random continuous function need not be a random closed set. The set of zeroes of a random continuous function is always a random closed set.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00153-007-0060-4", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1136186", 
            "issn": [
              "0933-5846", 
              "1432-0665"
            ], 
            "name": "Archive for Mathematical Logic", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "7-8", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "46"
          }
        ], 
        "name": "Algorithmic randomness of continuous functions", 
        "pagination": "533-546", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "9c5ea0829e784cbe4e2e165da7e419a3531823365364659415183b0067b28437"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00153-007-0060-4"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1032824312"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00153-007-0060-4", 
          "https://app.dimensions.ai/details/publication/pub.1032824312"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T14:30", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000373_0000000373/records_13090_00000001.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1007%2Fs00153-007-0060-4"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00153-007-0060-4'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00153-007-0060-4'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00153-007-0060-4'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00153-007-0060-4'


     

    This table displays all metadata directly associated to this object as RDF triples.

    122 TRIPLES      21 PREDICATES      34 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00153-007-0060-4 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N4c520d29b2fc4d15b1af474a65e05467
    4 schema:citation sg:pub.10.1007/11780342_6
    5 sg:pub.10.1007/bf01203155
    6 sg:pub.10.1007/bf01694181
    7 https://doi.org/10.1016/0304-3975(76)90005-0
    8 https://doi.org/10.1016/s0019-9958(66)80018-9
    9 https://doi.org/10.1093/logcom/exm033
    10 https://doi.org/10.2307/2586546
    11 schema:datePublished 2008-05
    12 schema:datePublishedReg 2008-05-01
    13 schema:description We investigate notions of randomness in the space of continuous functions on . A probability measure is given and a version of the Martin-Löf test for randomness is defined. Random continuous functions exist, but no computable function can be random and no random function can map a computable real to a computable real. The image of a random continuous function is always a perfect set and hence uncountable. For any , there exists a random continuous function F with y in the image of F. Thus the image of a random continuous function need not be a random closed set. The set of zeroes of a random continuous function is always a random closed set.
    14 schema:genre research_article
    15 schema:inLanguage en
    16 schema:isAccessibleForFree true
    17 schema:isPartOf Na439ff3d1a024b94a999aa617de470f7
    18 Nc6673ddd5e404e449788fd76de2ee4af
    19 sg:journal.1136186
    20 schema:name Algorithmic randomness of continuous functions
    21 schema:pagination 533-546
    22 schema:productId N3172c56eab2147b7bb1b47bad771dd4b
    23 Na2394258603c4b279f4e2e70b4881d9a
    24 Ncccc84b2ae4842e5b0fb8b676476a2fb
    25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032824312
    26 https://doi.org/10.1007/s00153-007-0060-4
    27 schema:sdDatePublished 2019-04-11T14:30
    28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    29 schema:sdPublisher N010a3fde4a21400589e34c85663566a1
    30 schema:url https://link.springer.com/10.1007%2Fs00153-007-0060-4
    31 sgo:license sg:explorer/license/
    32 sgo:sdDataset articles
    33 rdf:type schema:ScholarlyArticle
    34 N010a3fde4a21400589e34c85663566a1 schema:name Springer Nature - SN SciGraph project
    35 rdf:type schema:Organization
    36 N3172c56eab2147b7bb1b47bad771dd4b schema:name doi
    37 schema:value 10.1007/s00153-007-0060-4
    38 rdf:type schema:PropertyValue
    39 N4c520d29b2fc4d15b1af474a65e05467 rdf:first sg:person.013527770623.53
    40 rdf:rest Nd809111e00f44baf9b49829f7688e6c6
    41 Na2394258603c4b279f4e2e70b4881d9a schema:name dimensions_id
    42 schema:value pub.1032824312
    43 rdf:type schema:PropertyValue
    44 Na439ff3d1a024b94a999aa617de470f7 schema:volumeNumber 46
    45 rdf:type schema:PublicationVolume
    46 Nc6673ddd5e404e449788fd76de2ee4af schema:issueNumber 7-8
    47 rdf:type schema:PublicationIssue
    48 Ncccc84b2ae4842e5b0fb8b676476a2fb schema:name readcube_id
    49 schema:value 9c5ea0829e784cbe4e2e165da7e419a3531823365364659415183b0067b28437
    50 rdf:type schema:PropertyValue
    51 Nd809111e00f44baf9b49829f7688e6c6 rdf:first sg:person.012444770271.80
    52 rdf:rest Ne993379b937a4565992c2c5eb26334ac
    53 Ne29c22390fc74af3b506a60d0280ba88 rdf:first sg:person.010700557277.48
    54 rdf:rest Ne7a9134d7105493e967b6146ef9def32
    55 Ne7a9134d7105493e967b6146ef9def32 rdf:first sg:person.010446316643.85
    56 rdf:rest rdf:nil
    57 Ne993379b937a4565992c2c5eb26334ac rdf:first sg:person.014623655733.03
    58 rdf:rest Ne29c22390fc74af3b506a60d0280ba88
    59 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    60 schema:name Information and Computing Sciences
    61 rdf:type schema:DefinedTerm
    62 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    63 schema:name Artificial Intelligence and Image Processing
    64 rdf:type schema:DefinedTerm
    65 sg:journal.1136186 schema:issn 0933-5846
    66 1432-0665
    67 schema:name Archive for Mathematical Logic
    68 rdf:type schema:Periodical
    69 sg:person.010446316643.85 schema:affiliation https://www.grid.ac/institutes/grid.254880.3
    70 schema:familyName Weber
    71 schema:givenName Rebecca
    72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010446316643.85
    73 rdf:type schema:Person
    74 sg:person.010700557277.48 schema:affiliation https://www.grid.ac/institutes/grid.266100.3
    75 schema:familyName Remmel
    76 schema:givenName Jeffrey B.
    77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010700557277.48
    78 rdf:type schema:Person
    79 sg:person.012444770271.80 schema:affiliation https://www.grid.ac/institutes/grid.15276.37
    80 schema:familyName Brodhead
    81 schema:givenName Paul
    82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012444770271.80
    83 rdf:type schema:Person
    84 sg:person.013527770623.53 schema:affiliation https://www.grid.ac/institutes/grid.9909.9
    85 schema:familyName Barmpalias
    86 schema:givenName George
    87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013527770623.53
    88 rdf:type schema:Person
    89 sg:person.014623655733.03 schema:affiliation https://www.grid.ac/institutes/grid.15276.37
    90 schema:familyName Cenzer
    91 schema:givenName Douglas
    92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014623655733.03
    93 rdf:type schema:Person
    94 sg:pub.10.1007/11780342_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050561380
    95 https://doi.org/10.1007/11780342_6
    96 rdf:type schema:CreativeWork
    97 sg:pub.10.1007/bf01203155 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001533942
    98 https://doi.org/10.1007/bf01203155
    99 rdf:type schema:CreativeWork
    100 sg:pub.10.1007/bf01694181 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037526412
    101 https://doi.org/10.1007/bf01694181
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1016/0304-3975(76)90005-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014131822
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1016/s0019-9958(66)80018-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002020706
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1093/logcom/exm033 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059876091
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.2307/2586546 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053479348
    110 rdf:type schema:CreativeWork
    111 https://www.grid.ac/institutes/grid.15276.37 schema:alternateName University of Florida
    112 schema:name Department of Mathematics, University of Florida, P.O. Box 118105, 32611-8105, Gainesville, FL, USA
    113 rdf:type schema:Organization
    114 https://www.grid.ac/institutes/grid.254880.3 schema:alternateName Dartmouth College
    115 schema:name Department of Mathematics, Dartmouth College, Hanover, USA
    116 rdf:type schema:Organization
    117 https://www.grid.ac/institutes/grid.266100.3 schema:alternateName University of California, San Diego
    118 schema:name Department of Mathematics, University of California at San Diego, La Jolla, USA
    119 rdf:type schema:Organization
    120 https://www.grid.ac/institutes/grid.9909.9 schema:alternateName University of Leeds
    121 schema:name School of Mathematics, University of Leeds, Leeds, UK
    122 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...