• On Proving a Program Shortest

    • Fulltext

       

        Click here to view fulltext PDF


      Permanent link:
      https://www.ias.ac.in/article/fulltext/reso/025/09/1251-1260

    • 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.