Halting problem – What if the halting algorithm gave more than one output?


Sorry I don’t know how silly a question this might be, but i’ve been reading up on the halting problem lately, and understand the halting problem cannot possibly output a value that is “correct” when fed a machine that does the opposite of itself. This therefore proves the halting problem cannot be solved by contradiction.

What if you were to give the halting algorithm 3 possible outputs, something like:

  • Yes
  • No
  • Non-deterministic (for paradox’s like this one)

You could argue then that for a non-deterministic output it would then do something entirely different, but this would be okay because it is still non-deterministic behavior. For a simple algorithm input, such as a while True: pass it would be incorrect to output non-determinism, since it will always be No.

I was wondering if this would change its solve-ability, or would it still be un-solvable?

Thanks for any responses