The halting problem claims that it is impossible to having a machine that will always be able to predict if machine

will halt with a given input. However, it is proven impossible due to machine giving a output when it does not halt.

The machine does not need to give an output it could loop on forever which would still be a valid answer to the halting

machine prediction.

In this case

begin{align}

emptyset & = loop forever without output \

P(M) & = {M,M} \

H(M,i) & = {halt} when it halts and H(M,i) = emptyset when it does not halt \

N(i) & = {halt} when it get’s {not halt} and {} when it get’s input {halt} \

X(M) & = N(H(P(M))) \

end{align}

All machines can work on their own therefore all result are included.

This solves the problem as it is not possible to negate the absence of an output therefore both machine X and H will loop forever and H was right.

begin{align}

X(X) & = N(H(P(X))) \

& = N(H(X,X)) \

& = N(emptyset) \

& = emptyset

end{align}

$$

H(X,X) = X(X) = emptyset

$$

Assume the opposite $H(X,X) = {halt}$

begin{align}

X(X) & = N(H(P(X))) \

& = N(H(X,X)) \

& = N({halt}) \

& = emptyset

end{align}

This is a contradiction H predicted $X(X)$ would ${halt}$ but it did not

The answer the question then relies on what is the question is it on the output or the state of the machine. This solution also preserves the concept of infinite

recursion not giving a output even at the infinite state.

To further add on, this would mean given any input with infinite time and resource if $H(M,i) = {halt}$ it means there exist a finite solution (or a error from a real-life perspective).

If on the other hand $H(M,i) = emptyset$, then the input is not valid and has infinite recursion in it’s input (this could be the machine or the input in a real-life perspective).

The halting problem specifically looked into only the concept of machine looping forever I added real life perspective as an additional note.

The setup of X does have this problem but I assume that is a design issue:

begin{align}

X(M) & = N(H(P(M))) \

& = N(H(M,M)) \

& = N({halt}) \

& = N(emptyset) \

& = emptyset

end{align}

begin{align}

X(M) & = N(H(P(M))) \

& = N(H(M,M)) \

& = N(emptyset) \

& = emptyset

end{align}

$$

X(i) = emptyset

$$

**Solution to $NH$**

It is not the same as negating the result of $H$:

begin{align}

NH(M,i) & = N(H(M,i)) \

& = N({halt}) : N(emptyset) \

& = emptyset : emptyset

end{align}

You can reverse the output of the original halting machine but this will give you two possible solution. this is

how you get only one solution:

begin{align}

emptyset_{1} & = halt without output \

NH(NH,NH) & = {not halt}

end{align}

$NH(M,i) = {not halt}$ when it halts and $NH(M,i) = emptyset_{1}$ when it does not halt

begin{align}

NX(X) & = N(NH(P(X))) \

& = N(NH(X,X)) \

& = N({not halt}) \

& = {halt}

end{align}

$$

NH(X,X) ne NX(X)

$$

Assume the opposite $NH(X,X) = emptyset_{1}$

begin{align}

NX(X) & = N(NH(P(X))) \

& = N(NH(X,X)) \

& = N(emptyset_{1}) \

& = emptyset_{1}

end{align}

This is a contradiction $NH$ predicted it will halt and it did therefore $NH(X,X)$ can only output ${not halt} and halt$

This solution also preserves the concept of reverse infinite recursion is a solution that halts.

Similar proof as before:

begin{align}

NX(M) & = N(H(P(M))) \

& = N(NH(M,M)) \

& = N({not halt}) \

& = {halt}

end{align}

begin{align}

NX(M) & = N(H(P(M))) \

& = N(H(M,M)) \

& = N(emptyset_{1}) \

& = emptyset_{1}

end{align}

$$

NX(i) = {{halt},emptyset_{1}}

$$

$X(i)$ always loops forever $NX(i)$ will halt with or without output ${halt}$

**Conclusion**

The above shows that both $H$ and $NH$ are decidable and computers can answer any question when given infinite time and resource.