Skip navigation
Skip navigation

Algorithmic complexity

Hutter, Marcus

Description

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
URI: http://hdl.handle.net/1885/15001
Source: Scholarpedia
DOI: 10.4249/scholarpedia.2573

Download

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:  12 November 2018/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator