Browse Prior Art Database

A THEORY OF PROGRAM SIZE FORMALLY IDENTICAL TO INFORMATION THEORY

IP.com Disclosure Number: IPCOM000148471D
Original Publication Date: 1974-Apr-11
Included in the Prior Art Database: 2007-Mar-30

Publishing Venue

Software Patent Institute

Related People

Chaitin, Gregory J.: AUTHOR [+2]

Abstract

RC 4805 A THEORY OF PROGRAM SIZE FORMALLY IDENTICAL (ij21361) TO INFORMATION THEORY 4 1 1 7 4 Mathematics Gregory J. Chaitin IBM T. J. Watson Research Center

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 12% of the total text.

Page 1 of 28

RC 4805 A THEORY OF PROGRAM SIZE FORMALLY IDENTICAL (ij21361) TO INFORMATION THEORY 4 / 1 1 / 7 4
Mathematics Gregory J. Chaitin *

IBM T. J. Watson Research Center


Yorktown Heights, New York 10598
ABSTRACT
A new definition of the program-size complexity is made.

H(A,B/C,D) is defined to be the size in bits of the shortest self-delimiting program for calculating the strings A and B is one is given a minimal-size self-delimiting program for calculating the strings C and D. This differs from previous definitions: (1) progr,ams are required to be self-delimiting,
i.e., no program is a prefix of another, and (2) instead of being given C and D directly, one is given a program for cal-
culating them that is ~ninimal in size. Unlike previous definitions, this one has precisely the formal properties of the entropy concept of information theory. For example, H(A/B) = H(A,B) - H(B) + O(1). Also, i f a program of length
k is assigned measure 2-k, then H(A) 4 -log2 (the proba- bility that the standard universal computer w i l l calculate
A) + 0(1) .

* This work was done while the author was a visitor at the Research Center. The author's address is Rivadavia 3580, Buenos Aires , Argentina.

[This page contains 1 picture or other non-text object]

Page 2 of 28

LIMITED DISTRIBUTION NOTICE

This report has been submitted for publication eleewhere and has been issued as a Research Report for early dissemination
of its contents. As a courtesy to the intended publisher, it should not be widely distributed until after the date of outside publication.

Copies may be requested from:
IBM Thomas J. Watson Research Center Post Office Box 218
Yorktown Heights, New York 10598

[This page contains 1 picture or other non-text object]

Page 3 of 28

SECTION 1. INTRODUCTION

    There is a persuasive analogy between the entropy concept of infor- mation theory and the size of programs. This was realized by the first workers in the field of program-size compLexity, R. J. Solomonoff [I],

A. N. Kolmogorov [2], and G. J. Chaitin [3], and it accounts for the large measure of success of subsequent work in this area. However, it is often the case that results are cumbersome and have unpleasant error terms. These ideas cannot be a tool for general use until they are clothed in a powerful formalism like that of information theory.

    This opinion is apparently not shared by all workers in the field (see A. N. Kolmogorov [ 4 ] ) , but it has led others to formulate alter- native definitions of program-size complexity, for example, D. W. Love- land1 s uniform complexity [5] and C. P. Sclnorr 's process complexity 161. In this paper we present a new concept of program-size complexity. What train of thought led us to it?

    Think of a computer as decoder equipment at the receiving end of a noiseless binary communications channel. Think of its programs as code words, and of the res...