Thermodynamic cost of computation, algorithmic complexity and the information metric View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1989-09

AUTHORS

W. H. Zurek

ABSTRACT

Algorithmic complexity is a measure of randomness. In contrast to Shannon's entropy it is defined without a recourse to probabilities; for a binary string s it is given by the size, in bits, of the shortest computer program with the output s. I show that algorithmic complexity sets limits on the thermodynamic cost of computations, casts a new light on the limitations of Maxwell's demon and can be used to define distance between binary strings. More... »

PAGES

119-124

References to SciGraph publications

  • 1929-11. über die Entropieverminderung in einem thermodynamischen System bei Eingriffen intelligenter Wesen in ZEITSCHRIFT FÜR PHYSIK
  • 1985-07. The Fundamental Physical Limits of Computation in SCIENTIFIC AMERICAN
  • 1982-04. Conservative logic in INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS
  • 1988-03. The ultimate in undecidability in NATURE
  • 1975-05. Randomness and Mathematical Proof in SCIENTIFIC AMERICAN
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1038/341119a0

    DOI

    http://dx.doi.org/10.1038/341119a0

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "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": [
          {
            "familyName": "Zurek", 
            "givenName": "W. H.", 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1038/332115a0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002735580", 
              "https://doi.org/10.1038/332115a0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01341281", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007509467", 
              "https://doi.org/10.1007/bf01341281"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/321356.321363", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012160236"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0019-9958(64)90223-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027287787"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01857727", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032661873", 
              "https://doi.org/10.1007/bf01857727"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01857727", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032661873", 
              "https://doi.org/10.1007/bf01857727"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0003-4916(88)90094-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050844650"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0378-4754(88)90136-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051799685"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0378-4754(88)90136-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051799685"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1038/scientificamerican0575-47", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1056542031", 
              "https://doi.org/10.1038/scientificamerican0575-47"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1038/scientificamerican0785-48", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1056571549", 
              "https://doi.org/10.1038/scientificamerican0785-48"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1063/1.3067010", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1057907404"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevlett.53.391", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1060790898"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevlett.53.391", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1060790898"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tit.1968.1054210", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061646524"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0218053", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062842152"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1147/rd.176.0525", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1063180324"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1147/rd.214.0350", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1063180624"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1147/rd.321.0016", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1063181580"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/cbo9780511608858", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098739441"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1989-09", 
        "datePublishedReg": "1989-09-01", 
        "description": "Algorithmic complexity is a measure of randomness. In contrast to Shannon's entropy it is defined without a recourse to probabilities; for a binary string s it is given by the size, in bits, of the shortest computer program with the output s. I show that algorithmic complexity sets limits on the thermodynamic cost of computations, casts a new light on the limitations of Maxwell's demon and can be used to define distance between binary strings.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1038/341119a0", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1018957", 
            "issn": [
              "0090-0028", 
              "1476-4687"
            ], 
            "name": "Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "6238", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "341"
          }
        ], 
        "name": "Thermodynamic cost of computation, algorithmic complexity and the information metric", 
        "pagination": "119-124", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "dbb57f270348bd2ac2f04a45e18fc9bbee2ba205f14221d19b8953109b676c72"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1038/341119a0"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1046123811"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1038/341119a0", 
          "https://app.dimensions.ai/details/publication/pub.1046123811"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T15:39", 
        "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/0000000001_0000000264/records_8664_00000426.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://www.nature.com/nature/journal/v341/n6238/full/341119a0.html"
      }
    ]
     

    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.1038/341119a0'

    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.1038/341119a0'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1038/341119a0'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1038/341119a0'


     

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

    112 TRIPLES      21 PREDICATES      44 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1038/341119a0 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Nc7ff199f2fc94101aed91453e864b711
    4 schema:citation sg:pub.10.1007/bf01341281
    5 sg:pub.10.1007/bf01857727
    6 sg:pub.10.1038/332115a0
    7 sg:pub.10.1038/scientificamerican0575-47
    8 sg:pub.10.1038/scientificamerican0785-48
    9 https://doi.org/10.1016/0003-4916(88)90094-2
    10 https://doi.org/10.1016/0378-4754(88)90136-x
    11 https://doi.org/10.1016/s0019-9958(64)90223-2
    12 https://doi.org/10.1017/cbo9780511608858
    13 https://doi.org/10.1063/1.3067010
    14 https://doi.org/10.1103/physrevlett.53.391
    15 https://doi.org/10.1109/tit.1968.1054210
    16 https://doi.org/10.1137/0218053
    17 https://doi.org/10.1145/321356.321363
    18 https://doi.org/10.1147/rd.176.0525
    19 https://doi.org/10.1147/rd.214.0350
    20 https://doi.org/10.1147/rd.321.0016
    21 schema:datePublished 1989-09
    22 schema:datePublishedReg 1989-09-01
    23 schema:description Algorithmic complexity is a measure of randomness. In contrast to Shannon's entropy it is defined without a recourse to probabilities; for a binary string s it is given by the size, in bits, of the shortest computer program with the output s. I show that algorithmic complexity sets limits on the thermodynamic cost of computations, casts a new light on the limitations of Maxwell's demon and can be used to define distance between binary strings.
    24 schema:genre research_article
    25 schema:inLanguage en
    26 schema:isAccessibleForFree false
    27 schema:isPartOf N08bdab6348674c7db5037c81ae7f1636
    28 N521cd76d0433484ab9bd9f85e333142b
    29 sg:journal.1018957
    30 schema:name Thermodynamic cost of computation, algorithmic complexity and the information metric
    31 schema:pagination 119-124
    32 schema:productId N78cdd7cd402c4cb593b31fdc47c3c31e
    33 Ne0df6a73819342249d4baa6b03013c8b
    34 Nf29824583bd644e0b16343516bfcfa22
    35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046123811
    36 https://doi.org/10.1038/341119a0
    37 schema:sdDatePublished 2019-04-10T15:39
    38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    39 schema:sdPublisher N75c393dcba12474ab77cd14be0541a3e
    40 schema:url http://www.nature.com/nature/journal/v341/n6238/full/341119a0.html
    41 sgo:license sg:explorer/license/
    42 sgo:sdDataset articles
    43 rdf:type schema:ScholarlyArticle
    44 N08bdab6348674c7db5037c81ae7f1636 schema:volumeNumber 341
    45 rdf:type schema:PublicationVolume
    46 N3b035f3964cb4abf96e405b8f7f223d3 schema:familyName Zurek
    47 schema:givenName W. H.
    48 rdf:type schema:Person
    49 N521cd76d0433484ab9bd9f85e333142b schema:issueNumber 6238
    50 rdf:type schema:PublicationIssue
    51 N75c393dcba12474ab77cd14be0541a3e schema:name Springer Nature - SN SciGraph project
    52 rdf:type schema:Organization
    53 N78cdd7cd402c4cb593b31fdc47c3c31e schema:name readcube_id
    54 schema:value dbb57f270348bd2ac2f04a45e18fc9bbee2ba205f14221d19b8953109b676c72
    55 rdf:type schema:PropertyValue
    56 Nc7ff199f2fc94101aed91453e864b711 rdf:first N3b035f3964cb4abf96e405b8f7f223d3
    57 rdf:rest rdf:nil
    58 Ne0df6a73819342249d4baa6b03013c8b schema:name doi
    59 schema:value 10.1038/341119a0
    60 rdf:type schema:PropertyValue
    61 Nf29824583bd644e0b16343516bfcfa22 schema:name dimensions_id
    62 schema:value pub.1046123811
    63 rdf:type schema:PropertyValue
    64 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    65 schema:name Information and Computing Sciences
    66 rdf:type schema:DefinedTerm
    67 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    68 schema:name Computation Theory and Mathematics
    69 rdf:type schema:DefinedTerm
    70 sg:journal.1018957 schema:issn 0090-0028
    71 1476-4687
    72 schema:name Nature
    73 rdf:type schema:Periodical
    74 sg:pub.10.1007/bf01341281 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007509467
    75 https://doi.org/10.1007/bf01341281
    76 rdf:type schema:CreativeWork
    77 sg:pub.10.1007/bf01857727 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032661873
    78 https://doi.org/10.1007/bf01857727
    79 rdf:type schema:CreativeWork
    80 sg:pub.10.1038/332115a0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002735580
    81 https://doi.org/10.1038/332115a0
    82 rdf:type schema:CreativeWork
    83 sg:pub.10.1038/scientificamerican0575-47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1056542031
    84 https://doi.org/10.1038/scientificamerican0575-47
    85 rdf:type schema:CreativeWork
    86 sg:pub.10.1038/scientificamerican0785-48 schema:sameAs https://app.dimensions.ai/details/publication/pub.1056571549
    87 https://doi.org/10.1038/scientificamerican0785-48
    88 rdf:type schema:CreativeWork
    89 https://doi.org/10.1016/0003-4916(88)90094-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050844650
    90 rdf:type schema:CreativeWork
    91 https://doi.org/10.1016/0378-4754(88)90136-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1051799685
    92 rdf:type schema:CreativeWork
    93 https://doi.org/10.1016/s0019-9958(64)90223-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027287787
    94 rdf:type schema:CreativeWork
    95 https://doi.org/10.1017/cbo9780511608858 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098739441
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1063/1.3067010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1057907404
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1103/physrevlett.53.391 schema:sameAs https://app.dimensions.ai/details/publication/pub.1060790898
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1109/tit.1968.1054210 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061646524
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1137/0218053 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842152
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1145/321356.321363 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012160236
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1147/rd.176.0525 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063180324
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1147/rd.214.0350 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063180624
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1147/rd.321.0016 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063181580
    112 rdf:type schema:CreativeWork
     




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


    ...