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

  • 1986. Maxwell’s Demon, Szilard’s Engine and Quantum Measurements in FRONTIERS OF NONEQUILIBRIUM STATISTICAL PHYSICS
  • 1988-03. The ultimate in undecidability in NATURE
  • 1975-05. Randomness and Mathematical Proof in SCIENTIFIC AMERICAN
  • 1982-12. The thermodynamics of computation—a review in INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS
  • 1982-04. Conservative logic in INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS
  • 1929-11. über die Entropieverminderung in einem thermodynamischen System bei Eingriffen intelligenter Wesen in ZEITSCHRIFT FÜR PHYSIK A HADRONS AND NUCLEI
  • 1985-07. The Fundamental Physical Limits of Computation in SCIENTIFIC AMERICAN
  • 1987-11. Demons, Engines and the Second Law 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/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Theoretical Division, Los Alamos National Laboratory, 87545, Los Alamos, New Mexico, USA", 
              "id": "http://www.grid.ac/institutes/grid.148313.c", 
              "name": [
                "Theoretical Division, Los Alamos National Laboratory, 87545, Los Alamos, New Mexico, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Zurek", 
            "givenName": "W. H.", 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "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": "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/bf02084158", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014354438", 
              "https://doi.org/10.1007/bf02084158"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4613-2181-1_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043415809", 
              "https://doi.org/10.1007/978-1-4613-2181-1_11"
            ], 
            "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": "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.1038/scientificamerican1187-108", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1056630356", 
              "https://doi.org/10.1038/scientificamerican1187-108"
            ], 
            "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"
          }
        ], 
        "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": "article", 
        "id": "sg:pub.10.1038/341119a0", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1018957", 
            "issn": [
              "0028-0836", 
              "1476-4687"
            ], 
            "name": "Nature", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "6238", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "341"
          }
        ], 
        "keywords": [
          "algorithmic complexity", 
          "binary strings", 
          "information metric", 
          "complexity", 
          "computation", 
          "computer program", 
          "string S", 
          "thermodynamic cost", 
          "measure of randomness", 
          "bits", 
          "cost", 
          "metrics", 
          "randomness", 
          "Shannon", 
          "demons", 
          "strings", 
          "probability", 
          "limitations", 
          "program", 
          "distance", 
          "measures", 
          "size", 
          "Maxwell's demon", 
          "recourse", 
          "short computer program", 
          "contrast", 
          "s.", 
          "limit", 
          "new light", 
          "light", 
          "binary string S", 
          "output s."
        ], 
        "name": "Thermodynamic cost of computation, algorithmic complexity and the information metric", 
        "pagination": "119-124", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1046123811"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1038/341119a0"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1038/341119a0", 
          "https://app.dimensions.ai/details/publication/pub.1046123811"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2021-12-01T19:06", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/article/article_208.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1038/341119a0"
      }
    ]
     

    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.

    121 TRIPLES      22 PREDICATES      66 URIs      50 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1038/341119a0 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N3645e23340b34594825d9456d0118206
    4 schema:citation sg:pub.10.1007/978-1-4613-2181-1_11
    5 sg:pub.10.1007/bf01341281
    6 sg:pub.10.1007/bf01857727
    7 sg:pub.10.1007/bf02084158
    8 sg:pub.10.1038/332115a0
    9 sg:pub.10.1038/scientificamerican0575-47
    10 sg:pub.10.1038/scientificamerican0785-48
    11 sg:pub.10.1038/scientificamerican1187-108
    12 schema:datePublished 1989-09
    13 schema:datePublishedReg 1989-09-01
    14 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.
    15 schema:genre article
    16 schema:inLanguage en
    17 schema:isAccessibleForFree false
    18 schema:isPartOf N9d0265cbaa47441fa89bca26bc876be6
    19 Nc49d9021b76b4c708107fdeafd51ee41
    20 sg:journal.1018957
    21 schema:keywords Maxwell's demon
    22 Shannon
    23 algorithmic complexity
    24 binary string S
    25 binary strings
    26 bits
    27 complexity
    28 computation
    29 computer program
    30 contrast
    31 cost
    32 demons
    33 distance
    34 information metric
    35 light
    36 limit
    37 limitations
    38 measure of randomness
    39 measures
    40 metrics
    41 new light
    42 output s.
    43 probability
    44 program
    45 randomness
    46 recourse
    47 s.
    48 short computer program
    49 size
    50 string S
    51 strings
    52 thermodynamic cost
    53 schema:name Thermodynamic cost of computation, algorithmic complexity and the information metric
    54 schema:pagination 119-124
    55 schema:productId Na790712529c6465ca10e5352e5fc282c
    56 Ne91f39833e8641579de8ceeaf450e212
    57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046123811
    58 https://doi.org/10.1038/341119a0
    59 schema:sdDatePublished 2021-12-01T19:06
    60 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    61 schema:sdPublisher N0df06f38497a41299c82ded2d4c154a3
    62 schema:url https://doi.org/10.1038/341119a0
    63 sgo:license sg:explorer/license/
    64 sgo:sdDataset articles
    65 rdf:type schema:ScholarlyArticle
    66 N0df06f38497a41299c82ded2d4c154a3 schema:name Springer Nature - SN SciGraph project
    67 rdf:type schema:Organization
    68 N2c87df967b1f4cdeb8e2992e087f01a7 schema:affiliation grid-institutes:grid.148313.c
    69 schema:familyName Zurek
    70 schema:givenName W. H.
    71 rdf:type schema:Person
    72 N3645e23340b34594825d9456d0118206 rdf:first N2c87df967b1f4cdeb8e2992e087f01a7
    73 rdf:rest rdf:nil
    74 N9d0265cbaa47441fa89bca26bc876be6 schema:volumeNumber 341
    75 rdf:type schema:PublicationVolume
    76 Na790712529c6465ca10e5352e5fc282c schema:name dimensions_id
    77 schema:value pub.1046123811
    78 rdf:type schema:PropertyValue
    79 Nc49d9021b76b4c708107fdeafd51ee41 schema:issueNumber 6238
    80 rdf:type schema:PublicationIssue
    81 Ne91f39833e8641579de8ceeaf450e212 schema:name doi
    82 schema:value 10.1038/341119a0
    83 rdf:type schema:PropertyValue
    84 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    85 schema:name Information and Computing Sciences
    86 rdf:type schema:DefinedTerm
    87 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    88 schema:name Computation Theory and Mathematics
    89 rdf:type schema:DefinedTerm
    90 sg:journal.1018957 schema:issn 0028-0836
    91 1476-4687
    92 schema:name Nature
    93 schema:publisher Springer Nature
    94 rdf:type schema:Periodical
    95 sg:pub.10.1007/978-1-4613-2181-1_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043415809
    96 https://doi.org/10.1007/978-1-4613-2181-1_11
    97 rdf:type schema:CreativeWork
    98 sg:pub.10.1007/bf01341281 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007509467
    99 https://doi.org/10.1007/bf01341281
    100 rdf:type schema:CreativeWork
    101 sg:pub.10.1007/bf01857727 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032661873
    102 https://doi.org/10.1007/bf01857727
    103 rdf:type schema:CreativeWork
    104 sg:pub.10.1007/bf02084158 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014354438
    105 https://doi.org/10.1007/bf02084158
    106 rdf:type schema:CreativeWork
    107 sg:pub.10.1038/332115a0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002735580
    108 https://doi.org/10.1038/332115a0
    109 rdf:type schema:CreativeWork
    110 sg:pub.10.1038/scientificamerican0575-47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1056542031
    111 https://doi.org/10.1038/scientificamerican0575-47
    112 rdf:type schema:CreativeWork
    113 sg:pub.10.1038/scientificamerican0785-48 schema:sameAs https://app.dimensions.ai/details/publication/pub.1056571549
    114 https://doi.org/10.1038/scientificamerican0785-48
    115 rdf:type schema:CreativeWork
    116 sg:pub.10.1038/scientificamerican1187-108 schema:sameAs https://app.dimensions.ai/details/publication/pub.1056630356
    117 https://doi.org/10.1038/scientificamerican1187-108
    118 rdf:type schema:CreativeWork
    119 grid-institutes:grid.148313.c schema:alternateName Theoretical Division, Los Alamos National Laboratory, 87545, Los Alamos, New Mexico, USA
    120 schema:name Theoretical Division, Los Alamos National Laboratory, 87545, Los Alamos, New Mexico, USA
    121 rdf:type schema:Organization
     




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


    ...