Math Has a Fatal Flaw - YouTube

Is it possible to tell beforehand if a program will halt or not on a particular input?

Turing's claim (or what Veritasium claims to be his claim)

let $p(i)$ be any program with its inputs

assume $h(p, i)$ satisfy the requirement, that it tells beforehand if a program will halt or not on a particular input, such that

$$h(p, i) = \begin{cases} \text{WILL\_HALT}, & \text{if } p(i) \text{ will halt}\\ \text{WILL\_NOT\_HALT}, & \text{if } p(i) \text{ will not halt} \end{cases}$$

let $\hat{h}$ be

$$\hat{h}(p, i) = \begin{cases} \text{[infinite loop]}, & \text{if } h(p, i) = \text{WILL\_HALT}\\ 0, & \text{if } h(p, i) = \text{WILL\_NOT\_HALT} \end{cases}$$

consider $h(\hat{h}, \hat{h})$

$$h(\hat{h}, \hat{h}) = \begin{cases} \text{WILL\_HALT}, & \text{if } \hat{h}(\hat{h}) \text{ will halt}\\ \text{WILL\_NOT\_HALT}, & \text{if } \hat{h}(\hat{h}) \text{ will not halt} \end{cases}$$

or equivalently

$$h(\hat{h}, \hat{h}) = \begin{cases} \text{WILL\_HALT}, & \text{if } h(\hat{h}) = \text{WILL\_NOT\_HALT}\\ \text{WILL\_NOT\_HALT}, & \text{if } h(\hat{h}) = \text{WILL\_HALT} \end{cases}$$

The problem is, $\hat{h}(\hat{h})$ and $h(\hat{h})$ does not exist as $\hat{h}$ and $h$ takes two parameters, and there is no reason to assume $(\hat{h}) = (\hat{h}, \hat{h})$, leaving us no contradiction in the end.

The fix

To construct the paradox, we need to lower the input numbers. Instead of $\hat{h}$ we define

$$\tilde{h}(p) = \begin{cases} \text{[infinite loop]}, & \text{if } h(p, p) = \text{WILL\_HALT}\\ 0, & \text{if } h(p, p) = \text{WILL\_NOT\_HALT} \end{cases}$$

consider

$$h(\tilde{h}, \tilde{h}) = \begin{cases} \text{WILL\_HALT}, & \text{if } \tilde{h}(\tilde{h}) \text{ will halt}\\ \text{WILL\_NOT\_HALT}, & \text{if } \tilde{h}(\tilde{h}) \text{ will not halt} \end{cases}$$

or equivalently

$$h(\tilde{h}, \tilde{h}) = \begin{cases} \text{WILL\_HALT}, & \text{if } h(\tilde{h}, \tilde{h}) = \text{WILL\_NOT\_HALT}\\ \text{WILL\_NOT\_HALT}, & \text{if } h(\tilde{h}, \tilde{h}) = \text{WILL\_HALT} \end{cases}$$

Philosophy, physics, and other thoughts

Until I figure the fix out I thought Veritasium is making fake assertions and baiting, turned out he's just been careless, and a paradox does exist.

The logic behind the problem is that, if there exists a program that can tell beforehand whether any problem has a solution, it cannot tell beforehand whether itself has a solution, thus vetoes its own existence.

An analogy would be, if a predictor exists, and we do adversely to whatever it predicts, then its prediction is wrong, and we conclude the predictor does not exist.

Now in terms of predictor people's been creative that in terms of whether things happen at a given future time, it may provide a possibility instead of a definite binary happens or not. The result does not collapse until the given future time, and the behavior of observation does have an influence over the outcome since we can now alternate the predicted future (in forms of possibility). This possibility model solves all the paradox mentioned above.

Back port the possibility model into the problem, there might be a program that can tell beforehand the possibility of whether any program has a solution (with further limits on observer) which is useless though.

The conclusion, however, does not necessarily escalate to 'whether all problems has a solution' since a problem does not necessarily equal a turing machine program. It does, imho, might escalte to 'whether all problems has a definite solution', as is in coherence with quantum physics.

Though I wonder whether mathematicians are satisfied with such conclusion like 'Goldbach conjecture' has a 99.9999... possibility to be true.

On the other hand, an interesting research direction is to prove that 'Goldbach conjecture' is impossible to prove.