Created
August 5, 2022 19:02
-
-
Save apaz-cli/c0763ccdb8d1771956615677999977b1 to your computer and use it in GitHub Desktop.
The Halting Problem
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| * 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?"); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment