Question

Show that the following problem is solvable. Given two programs with their input and the knowledge that exactly one of them halts, determine which halts.

Short answer

The program which halts will depend upon the output of the given input.

Step-by-step solution

Step 1:

We have,

Two programs with their input and also the knowledge that exactly one of them halts.

Let,

$A_1=$Program one

$A_2=$Program two

$A_1\left(I_1\right)=$Input of program one

$A_2\left(I_2\right)=$Input of program two

Step 2:

We write a program $A_3$with the inputs $A_1\left(I_1\right)$and$A_2\left(I_2\right)$ that will halt if any of the given input halts.

The program will print 0 if$A_1$ halts.

The program will print 1 if$A_2$ halts.

Therefore if any one of the input halts, the program$A_3$ will also halt. The printed output will show the program will has halted.