Suppose we have P, a string denoting a C program which takes in a natural number as input and outputs at most one natural number. Prove that it is impossible (unsolvable) to determine that P has infinite range.
In other words, show that it is impossible to determine whether $\mid\{y\in N | \exists x \in N.(P\ outputs\ y\ given\ input\ x)\}\mid$ is infinite.
My approach to this problem is by contradiction & reduction. Let's call this problem Infinite Range (IR). I first assume that it is solvable, and let A be such algorithm that solves IR. Then I want to create a algorithm B that will use A and will solve the Halting Problem, and prove this claim. Then this program uses A and solves the Halting problem, but since we know that the halting problem is unsolvable, this is a contradiction and by reduction we see that since Halting Problem is unsolvable, so is IR.
My problem lies in creating such program B to lead to the contradiction! I was thinking of creating a program D that takes in the program P as mentioned and covert it into program Q: run P in a loop that tries to find a number x such that P(x) = y, from y = 0 ... infinity. It will be ran in another loop that increments x until P(x) = y. And then if it fails to halt, as in it fails to find an x for y, or outputs no number, returns false. We insert this program into A, and then send the NOT of the answer A returns. IE: P halts, so Q sends false. A returns false, so B return true.
Then this solves the halting problem.
However my program D seems awfully flawed and shaky and I feel rather insecure with it.
Thanks in advance!