Q24: Hello-world tester

Question #24: Consider the following hypothetical program:

The program “Hello-world tester” takes two inputs, a program P and the input I for P. The program H prints “yes” if P on input I prints “hello, world”, otherwise H prints “no”. What do you think of such a program?

Options:

1. The program H can exist which can test any other program for some particular output.
2. The program H is very difficult to design.
3. The program H can’t exist since we can come up with a contradiction by replacing “no” with “hello, world” and taking a single input which both acts as program and input.
4. Both options 1 and 2 are correct

 

Solution:

This is one version of very famous halting problem, which states that we can’t detect whether any program on any input will ever halt or not. And, it’s undecidable over Turing machines! Hence, the correct answer is option 3.