A slightly different version of the halting problemo

Question

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.

The usual way is to construct another program that can use this one to solve the halting problem. If you succeed, you've proven that the original program can't exist. — biziclop
– biziclop, Commented Sep 19, 2017 at 17:15
@sascha Not for me, sadly. I tried to build one 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. — Eddie Romanenco
– Eddie Romanenco, Commented Sep 19, 2017 at 17:19
@biziclop That was my approach too, but I wasn't able to come up with a good one. — Eddie Romanenco
– Eddie Romanenco, Commented Sep 19, 2017 at 17:20
@biziclop Could you think of a general discription for a program that could help me? — Eddie Romanenco
– Eddie Romanenco, Commented Sep 19, 2017 at 17:28
@Eddie you could consider the problem of solving the halting program for programs that completely ignore their input. You might also consider writing a program that ignores the provided input, but writes out data which a second program treats as if it was input, so the combination of the two completely ignores the original input, but the second program treats the output of the first as if it was input. — mcdowella
– mcdowella, Commented Sep 20, 2017 at 3:57

btilly · Accepted Answer · 2017-09-20 07:39:36Z

Here is a hint.

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

Collectives™ on Stack Overflow

A slightly different version of the halting problemo

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related