Skip to content

Instantly share code, notes, and snippets.

@apaz-cli

apaz-cli/Kaboom.c

Created August 5, 2022 19:02
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save apaz-cli/c0763ccdb8d1771956615677999977b1 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save apaz-cli/c0763ccdb8d1771956615677999977b1 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. apaz-cli created this gist Aug 5, 2022.
    35 changes: 35 additions & 0 deletions Kaboom.c
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,35 @@
    /*
    * The Halting Problem:
    * Does there exist an algorithm which can determine if any complete program
    * halts? Complete means that all information about the program must be known
    * beforehand.
    *
    *
    * The definition in computability theory for "Algorithm" is:
    * "A finite list of instructions which when carried out must
    * always terminate."
    *
    * Not all code has to be an algorithm. Plenty of code (ex: web servers)
    * doesn't fit this description because it doesn't terminate.
    *
    * Suppose for contradiction that a solution to the halting problem exists.
    * That is to say, for any input it must return a correct "yes" or "no"
    * answer (not "I don't know"), and it must do so in a finite amount of time.
    */


    /*
    * Input:
    * A C program for which all information is known beforehand.
    *
    * Returns:
    * true if the program halts,
    * false otherwise (runs forever).
    */
    bool haltingProblemSolution(char* program);

    int main() {
    char* thisProgram = openFile("Kaboom.c");
    while (haltingProblemSolution(thisProgram))
    puts("Do I terminate?");
    }