Sophistication revisited

• Type: Article in International Scientific Journal
• Date: 2003

Authors

antunes, l (Author) FCUP; fortnow, l (Author) Other

Journal

The Journal is awaiting validation by the Administrative Services.

Title: INTERACTIVE SYSTEMS: DESIGN, SPECIFICATION, AND VERIFICATION

Vol. 58

Pages: 267-277

Indexing

ISI Web of Knowledge - 3 Citations

Scopus - 4 Citations

Other information

Authenticus ID: P-000-J78

DOI: 10.1007/3-540-45061-0_23

Abstract (EN): The Kolmogorov structure function divides the smallest program producing a string in two parts: the useful information present in the string, called sophistication if based on total functions, and the remaining accidental information. We revisit the notion of sophistication due to Koppel, formalize a connection between sophistication and a variation of computational depth (intuitively the useful or nonrandom information in a string), prove the existence of strings with maximum sophistication and show that they encode solutions of the halting problem, i.e., they are the deepest of all strings.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 11