Explain the Halting Problem (source: Wiki, https://programmingwords.com/home/halting-problem)

Halting_Problem.java

// What is the halting problem in programming?
// In computability theory, the halting problem is the problem of determining, from a description of an abitrary program and an input, whether the program will finish running, or continue to run forever. (Wiki)
// Normally, you run the program, it executes, then it's done. In other words, it stops to a halt.
// But sometimes, a program runs for a very long time. Sometimes even for an infinitely amount of time.
// The problem is, there is no way to actually tell whether a program will ever be done. In fact, it is one of the most fundamental problems in computer science, so fundamental, that solving it changed both mathematics and computer science forever.
// Example of a never-halt program
while (true) {
	print("I am running.");
}
// Using Contradiction, Turing has prove that it is impossible to answer the question of whether a program will ever finished. That the halting problem is undecidable.
// Lets pretend that we have some sort of function that can determine if a program halts or not. It would look something like this
boolean halts(program) {
	// some magic here
}

// Now, consider the following function
int g(program) {
	if (halts(program)) {
		while (true) {
			print("I am running.");
		}
	} else {
		return 0;
	}
}
// If program is halt-able, g will loop forever (un-halt-able)
// If program is un-halt-able, g will return 0 (halt)

// Now, let's try to call
g(g);
// If g halts, then this program will run forever. But how can that be true if we know g is halting ??????
// If g never halts, then this program will halt. So that means g halts, which also not possible ????
// Because it does not make sense, then obviously it is undecidable.

// This has some real world consequences. This is why we don7t get a compiler error if we write an infinite loop.
// This is also why stack overflow error exists.
// If we could predict/detect them before, we could prevent them from happening.