On Proving a Program Shortest
- PDF / 214,365 Bytes
- 10 Pages / 595 x 842 pts (A4) Page_size
- 19 Downloads / 200 Views
On Proving a Program Shortestโ Arindama Singh
We revisit a problem faced by all programmers. Can one write a program that determines whether any given program is the shortest program? How does one prove that a given program is the shortest? After answering these questions, we discuss very brie๏ฌy the Kolmogorov complexity of a string of zero and one, which leads to a barrier on any axiomatic system, known as Chaitinโs barrier. Arindama Singh works as a professor in mathematics at
Introduction
IIT Madras. His teaching and research interests include
Consider writing a program that computes the function
theory of computation, logic, and linear Algebra. He has authored three books in these
๐ : {1, . . . , 20} โ {1, . . . , 6},
areas.
given by the following table: ๐ : ๐ (๐) :
1 1
2 5
3 2
4 5
5 2
6 6
7 2
8 6
9 3
10 0
๐ : 11 12 13 14 15 16 17 18 19 20 ๐ (๐) : 3 0 4 0 4 1 4 1 5 2 We can write a program by giving this table as an input so that ๐ (๐) can be computed for a given ๐ by just reading the table appropriately. However, there is an alternative. It is easy to verify that the function ๐ can be speci๏ฌed by
Keywords Four types of programs, simu-
๐ (๐) = [(3.7 ร ๐) โ 2]
mod 7 for 1 โค ๐ โค 20.
lating programs, input bit-string, input-program, length of a pro-
It is the remainder obtained by dividing the integral part of (3.7 ร ๐) โ 2 by 7. Is there a shorter way of specifying the same function?
gram, complexity, Chaitinโs barrier.
In fact, we are interested in more general questions. โ Vol.25,
No.9, DOI: https://doi.org/10.1007/s12045-020-1043-6
RESONANCE | September 2020
1251
GENERAL ARTICLE
Strong Question: How do we prove that a given program is a shortest program among all those doing the same job? Weak Question: Can we write a program which will determine whether a given program is a shortest program among all the programs doing the same job?
1. Preparation To answer these questions, we need a little preparation as to ๏ฌxing some notions, etc. We ๏ฌx a computer and a general-purpose language for this computer, be it C, Java, Python, or Lisp. Though we give input to the computer and get some output from the computer by executing a program, we say that the program has taken an input and gave us that output. Based on this, we will deal with four types of programs: 1. Programs that take inputs and give outputs upon halting. 2. Programs that take no inputs but give outputs upon halting. 3. Programs that take inputs, do not halt and give outputs time to time. 4. Programs that do not take inputs, do not halt, and give outputs time to time.
There are programs that can take other programs as inputs and run an input-program.
1252
In fact, inputs and programs are all stored in the computer as bit-strings, that is, ๏ฌnite sequences of 0 or 1. And all our programs can take bit-strings as inputs. Thus all programs can take other programs as inputs. That is, there are programs that can take other programs as inputs and run an input-program. Such programs may be called as simulating programs. If the in
Data Loading...
