Below, you can find another hint for the Generalized Challenge.
You should only get here after reading, digesting, and applying the .
There are many semantic properties of programs for which it would be useful to have an algorithm that determines whether a given program has the property.
One particularly interesting function of this kind is the so-called halting function H. The function result H(s) is a boolean value (true or false) expressing whether string s, when executed as a program without input, will halt.
The halting function is a mathematically well-defined function. But, unfortunately, there is no program (in JavaScript or any other programming language) that implements it correctly.
You can understand that by considering the following function f, assuming we have a JavaScript implementation H() of the halting function H. This function f applies H to s and then behaves to contradict H(s):
To understand how this refutes that the halting function can be implemented, apply our program G (see ) to this f() (including H()). We will show a concrete example below, but for now imagine the resulting output of applying G to this f(). That output is a program P such that it behaves as f() applied to P itself.
How can that program P behave? P halts, by its structure, if and only if the loop terminates. The loop terminates if and only if H(s) returns false. But that means that the alleged halting function H() determined that its argument, which is P, will not halt. Clearly, the result H(P) is not correct, because P behaves in the opposite way.
Here is an attempt at defining H (it will turn out to be wrong), so as to have something concrete to try out. Function f() is adapted a bit to make it more verbose and to provide an escape when it enters the never ending loop. The auxliary function Hinv() is the inverse of H().
When our program G from the is applied to this function f (; in case this program and input is too big for the server to handle, you can and copy-paste the definitions of H and f into the input box separately), we obtain as output a program that applies f to the program itself. This is then a program for which the alleged function H fails to return a correct result.
You should and see for yourself. You can also change the definition of function H, for instance, by removing the negation ! (do not forget to remove it also in the Blueprint), and try again. Note: There is a safety mechanisms that lets you escape from the infinite loop.
Conclusion: There exists no implemention (in JavaScript) of the halting function H that determines for any JavaScript program without input whether it will halt.
Note: For programs with input, there is a simpler counterexample, which does not involve the self-reproduction mechanism. In that case, a halting function H takes two arguments, a program and an input for that program, and it should determine whether that program will halt when (it would be) executed with the given input. (Of course, H is not just going to execute the program.)
Assuming we have a JavaScript definition of an alleged halting function H(s, i), consider the following program C:
You should .
Can you generalize this construction to refute the existence of algorithms that check other semantic properties?
This completes your journey. You can now consult the summary of all hints.
I hope you enjoyed it and learned some interesting computer science on the way.