• On Proving a Program Shortest

    • Fulltext


        Click here to view fulltext PDF

      Permanent link:

    • Keywords


      Four types of programs, simulating programs, input bit-string, input-program, length of a program, complexity, Chaitin’s barrier.

    • Abstract


      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 briefly the Kolmogorov complexity of a string of zero and one, which leads to a barrier on any axiomatic system, known as Chaitin’s barrier.

    • Author Affiliations


      Arindama Singh1

      1. Professor of Mathematics IIT Madras
    • Dates


© 2021-2022 Indian Academy of Sciences, Bengaluru.