Solution to the Halting problem

The diagram to the left is not a "rigorous" proof, but illustrates the solution. The same applies to the almost one sheet summary. For the proof, download the whole paper.

Further remarks: the diagram to the left is taken from an earlier version of the paper, written about 5 years ago. In essence the Halting problem is soluble because if the problem is finite for a machine of

Thus, the paradigm shift that is required involves recognising that human reason has the capacity for synthetic reasoning. Hence, the emphasis on synthetic logic on this website.

The author affirms that this website contains many other examples of synthetic reasoning, both mathematical and non-mathematical. One of these is the Dirichlet principle, but there are many others. In fact, even the analytic reasoning (of first-order logic) is incomplete without additional synthetic elements.

The importance of mathematics and logic in the debate arises from the fact that computers are described by those discourses, so the claim of strong AI - that a machine can become conscious - can only be refuted within those discourses. This author is not a computer scientist, though he has a deep mathematical background, but he did dedicate large parts of his life to equipping himself with all the tools necessary so as to evaluate this problem from a vantage that is techical but whose provenance hails from

The references here for example to "first-order logic" may preclude some non-technicians from the discussion, which must to be regretted. It is an unfortuante consequence of nature of the discourse, which has been dominated by the technical claims of computer science, mathematicians and philosophers, and that discourse is altogether written in a language outside that of the majority of the informed public. Something also must be done to remedy this situation, and bring the claims of computing science more within the scope of the evaluation of the public in general.

Further remarks: the diagram to the left is taken from an earlier version of the paper, written about 5 years ago. In essence the Halting problem is soluble because if the problem is finite for a machine of

*n*states, adding one more state does not make the problem infinite. But the revised paper argues the induction step on a case-by-case basis and is, therefore, "rigorous". It is not the habit of this author to claim more than he is allowed; he states that (a) until this time the claim has not been refuted, and expresses (b) his confidence that his rigoruous proof is just that - rigorous. The situation is extraordinary, because the assumption that (1) it is madness to attempt a solution to the Halting Problem became ingrained into scientific culture, hence, acceptance that there is a solution requires a massive "paradigm shift"; (2) because it has been assumed that mathematical induction is a species of algorithm. Although the paper does not assume that mathematical induction is not algorithmic, one may affirm independently that it is a synthetic principle of reasoning, as was mentioned by Poincare in the early C20th. It is synthetic because the premises refer in meaning only to finite information, but the conclusion refers to a potentially infinite collection - all natural numbers,*ad infinitum*. The term "*ad infinitum*" is not contained in the premises; therefore, induction is both necessary and synthetic.Thus, the paradigm shift that is required involves recognising that human reason has the capacity for synthetic reasoning. Hence, the emphasis on synthetic logic on this website.

*There is a new science of synthetic logic*.The author affirms that this website contains many other examples of synthetic reasoning, both mathematical and non-mathematical. One of these is the Dirichlet principle, but there are many others. In fact, even the analytic reasoning (of first-order logic) is incomplete without additional synthetic elements.

The importance of mathematics and logic in the debate arises from the fact that computers are described by those discourses, so the claim of strong AI - that a machine can become conscious - can only be refuted within those discourses. This author is not a computer scientist, though he has a deep mathematical background, but he did dedicate large parts of his life to equipping himself with all the tools necessary so as to evaluate this problem from a vantage that is techical but whose provenance hails from

*outside*that of the pre-existing academic consensus. He is cited in his own name in papers on first-order logic as co-author or as consultant. The author makes no denigration of the efficacy of first-order logic, but he does dispute whether first-order logic is all the logic that there is.The references here for example to "first-order logic" may preclude some non-technicians from the discussion, which must to be regretted. It is an unfortuante consequence of nature of the discourse, which has been dominated by the technical claims of computer science, mathematicians and philosophers, and that discourse is altogether written in a language outside that of the majority of the informed public. Something also must be done to remedy this situation, and bring the claims of computing science more within the scope of the evaluation of the public in general.

The halting problem is the problem of determining whether a Turing machine will halt for a given input. One of the results of modern computing theory is that the halting problem cannot be solved. However, this argument, a proof by contradiction, like any other argument has premises. Two of the hidden premises are (a) that there is no distinction between the potential and actual infinite, and (b) that proof by mathematical induction is a form of algorithm. The important point is to realise that there is a distinction between proving that we

*know*something and having an algorithm that computes a result. The impossibility proof, then, is a proof that any machine that computed an algorithm would need an actually infinite number of parts, and as this is impossible, a computer cannot be built to solve the problem. But this is only an impossibility proof for computers, not for the human mind. It turns out that a proof that the halting problem for any Turing machine can be solved is a relatively simple induction on the number of states of a Turing machine.