Browse Prior Art Database

PROGRAM SIZE, ORACLES, AND THE JUMP OPERATION

IP.com Disclosure Number: IPCOM000148705D
Original Publication Date: 1976-Jan-27
Included in the Prior Art Database: 2007-Mar-30

Publishing Venue

Software Patent Institute

Related People

Chaitin, Gregory J.: AUTHOR [+2]

Abstract

RC 5822 PROGRAM SIZE, ORACLES, AND THE JUMP OPERATION (f 25230)1/27/76 Gregory J. ChaitinMathematics IBM Thomas J. Watson Research center 17 pages Yorktown Heights, New York 10598 Typed by Barbara J. Juliano on MTST ABSTRACT: There are a number of questions regarding the size of programs for calculating natural numbers, sequences, sets, and functions, which are best answered by considering computations in which one is allowed to consult an oracle for the halting problem. Questions of this kind suggested by work of T. Kame and D. W. Loveland are treated. LIXlITED DISTRIBUTION NOTICE This report has been submitted for publication elsewhere 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 218Yorktown Heights, New York 10598 SECTION 1. COMPUTER PROGRAMS, ORACLES, INFORMATION MEASURES, AND CODINGS

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 15% of the total text.

Page 1 of 20

RC 5822 PROGRAM SIZE, ORACLES, AND THE JUMP OPERATION
(f 25230)
1/27/76 Gregory J. Chaitin
Mathematics

                 IBM Thomas J. Watson Research center
17 pages Yorktown Heights, New York 10598

Typed by Barbara J. Juliano on MTST
ABSTRACT: There are a number of questions regarding the '

size of programs for calculating natural numbers, sequences,
sets, and functions, which are best answered by considering
computations in which one is allowed to consult an oracle
for the halting problem. Questions of this kind suggested
by work of T. Kame and D. W. Loveland are treated.

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

Page 2 of 20

LIXlITED DISTRIBUTION NOTICE

This report has been submitted for publication elsewhere 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 20

SECTION 1. COMPUTER PROGRAMS, ORACLES, INFORMATION MEASURES, AND CODINGS

    In this paper we use as much as possible Rogers' terminology and
notation 11, pp. xv-xixl. Thus N = {0,1,2, ...I is the set of (natural) numbers; i, j, k, n, v, w, x, y, z are elements of N; A, B, X are subsets of M; f, g, h are functions from N into N; co, JI are partial functions from N into N; <x ...,

                   x > denotes the ordered k-tuple consisting of 1 ' k
the numbers xl, ...,

x the lambda notation Ax[ ...

k ;

the partial function of x whose value is ...

vx[ ...

x. ..I is used to denote the least x such that ...

x... is true.

    The size of the number x, denoted lgtx), is defined to be the number of bits in the xth binary string. The binaxy strings are: A, 0, 1, 00, 0 1 1 11 000, . Thus lg(x) is the integer part of log2(x+l). Note that there are 2n numbers x of size n, and 2n-1 numbers x of size less than n.

    We are interested in the size of programs for a certain class of computers. The zth computer in this class is defined in terns of P (2)X z

11, pp. 128-1343, which is the two-variable partial X-recursive function with Gadel number z. These computers use an oracle for deciding member- ship in the set XI and the zth computer produces the output 'P(~)'

    (xIy) z

when given the program x and the data y. Thus the output depends on the set X as well as the nmbers x and y.

    We now choose the standard universal computer U that can simulate any other computer. U is defined as follc>ws:

x. ..I is used to denote

x...; and the mu notation

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

Page 4 of 20

Thus for each computer C there is a constant c such that any program of

size n for C can be simulated by a program of size < n+c for U.

-

    Having picked the standard computer...