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!

  • 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

1

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)     if(F(Z))         return 0     else         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.