On Proving a Program Shortest
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.
Volume 27 | Issue 8