Skip navigation
Skip navigation

Algorithmic complexity

Hutter, Marcus


The information content or complexity of an object can be measured by the length of its shortest description. For instance the string "01010101010101010101010101010101" has the short description "16 repetitions of 01", while "11001000011000011101111011101100" presumably has no simpler description other than writing down the string itself. More formally, the Algorithmic "Kolmogorov" Complexity (AC) of a string x is defined as the length of the shortest program that computes or outputs x , where...[Show more]

CollectionsANU Research Publications
Date published: 2008-01
Type: Journal article
Source: Scholarpedia
DOI: 10.4249/scholarpedia.2573


File Description SizeFormat Image
Hutter Algorithmic Complexity 2008.pdf586.06 kBAdobe PDFThumbnail

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator