1
$\begingroup$

I got stuck with a question and would like to have a little guidance for the solution.

I need to prove that the next problem is undecidable:

  • Input - A program
  • Problem - Does the number of possible inputs for which the program halts is larger than those for which the program won't halt?

I tried to build a reduction that (in case the input is even) halts for every even number, goes to an infinite loop for every odd and runs the program with the input. Or in case the input is odd does the opposite - but it only works if I am able to prove that the number of real odd numbers is equal to the real even numbers.

$\endgroup$
  • $\begingroup$ I'm a little confused about your input space and your use of "larger": are you assuming that the input has some fixed constant size? $\endgroup$ – cody Sep 19 '17 at 18:15
  • $\begingroup$ @cody That's how the question itself is phrased, I guess the meaning is that there are more legal input values that could be entered into the program and result with the program halting than those that when entered into the program would make it run forever. $\endgroup$ – Eddie Romanenco Sep 19 '17 at 18:20
  • $\begingroup$ @cody Without making any assumptions on the nature of the input values. $\endgroup$ – Eddie Romanenco Sep 19 '17 at 18:24
  • $\begingroup$ @cody I believe that I need to construct another program that can use this one to solve the halting problem, but I can't find any good idea to use. $\endgroup$ – Eddie Romanenco Sep 19 '17 at 18:27
2
$\begingroup$

I won't give you the solution - I think you're on the right track. However I will give a possible way of making this question precise:

Prove that this problem is undecidable:

  • Input: A (code for a) Turing Machine $M$
  • Output: $\texttt{Accept}$ if the number of inputs for which $M$ halts is a finite number $\leq n$
  • $\texttt{Reject}$ otherwise.

Since there are an infinite number of inputs, if $M$ halts for a finite number of them, then it doesn't halt for an infinite number of them.

Of course, it's possible for a machine to halt on an infinite number of inputs, and not halt on an infinite number of inputs (say, halt on even numbers and not on odd numbers). In this case, a hypothetical machine for this problem would $\mathtt{Reject}$.

You might notice some similarity to the halting problem at this point.

$\endgroup$

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.