Logical depth and other algorithmically defined properties of finite objects

Abstract

The input/output relation of a universal computer, which by Church's thesis provides a microcosm of all deductive logic and all physical processes that might be described by such logic, can be used t o define intrinsic properties of digitally represented physical objects. An object's intrinsic information content o r arbitrarin e s s m a y identified with its algorithimic entropy, The negative logarithm of The object's probability of being produced as The output of a computation with r a n d o m input. An object's intrinsic causal nontriviality o r logical depth m a y be identified with n u m b e r of steps in a typical o n e of The computation paths leading t o The object. Although n o t effectively computable o r efficiently approximable in practice, these properties are asymptotically roughly m a c h i n e independent (and thus intrinsic), owing t o The ability of a n y t w o e f i c i e n t l y universal computers t o simulate one another at the cost of a n additive increase in program size and a polynomial expansion of execution t i m e .