Question

Prove that it is possible to write a program P which:

Takes as input M, a java program

Runs forever, and prints out strings to the console

For every x, if M(x) halts, then P(M) eventually prints out x

For every x, if M(x) does NOT halt, then P(M) never prints out x

EXPERT ANSWER

Following is the Algorithm of the given Problem :

Starting out, Let S = {}

for i = 1 to infinity:

Let N_i =