Sophistication revisited

• Tipo: Artigo em Revista Científica Internacional
• Data: 2003

Autores

antunes, l (Autor) FCUP; fortnow, l (Autor) Outra

Revista

A Revista está pendente de validação pelos Serviços Administrativos.

Título: INTERACTIVE SYSTEMS: DESIGN, SPECIFICATION, AND VERIFICATION

Vol. 58

Páginas: 267-277

Indexação

ISI Web of Knowledge - 3 Citações

Scopus - 4 Citações

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 11