A slightly different version of the halting problemo

119 Views Asked by At

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.

1

There are 1 best solutions below

0
On

Here is a hint.

˙„ɥƃnouǝ ǝƃɹɐʃ„ ǝɹɐ ʇɐɥʇ sʇnduı ʃʃɐ ɹoɟ ʇʃɐɥ ʇɥƃıɯ ʇɐɥʇ sɯɐɹƃoɹd ʇɐ ʞoo˥