2
$\begingroup$

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!

  • 0
    Didn't read the whole thing, but seems like you first need to prove the Turing Completeness of C.2011-03-14
  • 2
    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.2011-03-16
  • 4
    @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.2011-03-17

1 Answers 1