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!

  • $\begingroup$ Didn't read the whole thing, but seems like you first need to prove the Turing Completeness of C. $\endgroup$ – Aryabhata Mar 14 '11 at 23:09
  • 2
    $\begingroup$ You should not ask assignment questions on forums and copy answer from other people. I will talk to the T.A.s to read all solutions carefully. This is an academic offence. Please come to my office hours or ask before and after Monday Wednesday classes for any questions. $\endgroup$ – user8337 Mar 16 '11 at 13:33
  • 4
    $\begingroup$ @Ellen: I've converted your post to a comment as it is not, strictly speaking, an answer to the question asked. Once you accrue 50 or more points on the website, you'll be able to leave comments yourself. $\endgroup$ – Willie Wong Mar 17 '11 at 9:25

Maybe I missed something, but I don't see how that program B would solve the halting problem for "every" possible program, it would work on those type of programs you construct from program like P, but for every arbitrary program I don't see how B would behave.
But you can prove in a similar way to the halting problem, if you suppose that a program F solves IR (return true if the input program has infinite range, or false otherwise), you can construct this program:

program Z(integer n)
        return 0
        return n

Which is a program that takes a natural number and produces at most one natural number. The thing is that Z could either have an infinite range or not, if Z has an infinite range, F(Z) would evaluate true, so Z would produce just 0, which is a contradiction, if Z doesn't have an infinite range F(Z) would evaluate false, which means that Z(n) = n, so that Z would produce all natural numbers, another contradiction.
So a program like F can't exist.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.