Tag Archives: Entschärfung des Halteproblems

Disarming the contradiction of the halting problem

Disarming the contradiction of the halting problem

[Last Update: 28th November 2018]

My daughter Dhivyah recently asked me (July / August 2016) if the current development of the artificial intelligence is similar to the human intelligence. This has motivated me to write about a problem in computability theory the so-called halting problem.

Many computer scientists knows the holding problem from the theoretical computer science lecture. It says that there is a universal program that decides for all possible programs in the world whether the program will terminate from running or continue to run forever. Because the universal program have to decide for all programs, it also have to decide about itself if it holds or not. This leads to a contradiction.

Clarification of the contradiction

If the universal program has to decide about itself that it will not halt then the universal program has to terminate. This is a contradiction.

Mathematical formulation of the halting problem

∀x∈X ∃y∈X ∶ x → halt = yes / no
(X = Set of all possible programs); (y = universal program)

[The mathematical expression (two lines) reads as follow:]
For all element x from the set X there exist a y from the set X so that should be checked if x halts or not. Capital letter “X” is the set of all possible programs, small letter “y” is the universal program which have to verify or falsify. The small letter “x” is one of the program from the set “X“.

How can we eliminate this contradiction or disarm it?

Solution / disarming

By simply forbidding that the Universal program does not have to decide about itself.

Addendum: 28th November 2018

The analogy of my approach or solution is similar to that of the Russell’s antinomy or barber paradox. One has tried to eliminate the paradox contained in the naive set theory through axiomatization. One of the most well-known axiomatization in modern mathematics was the Zermelo-Fraenkel Set Theory with axiom of choice (ZFC).

Mathematical formulation of disarming

∀x∈X’ ∃y∉X’ ∶ x → halt = yes / no
(Equivalent formulation: ∀x∈X’ ∃y∈X ∶ x → halt = yes/ no)
(X’ = Set of all possible programs without y); (y = universal program; y∉X’ and y∈X, X’ ⊂ X)

[The same as above in “Mathematical formulation of the halting problem” with two exceptions: stands for “not element of” and stands for “strict subset of“;  X’ is strict subset of X]

How powerful are the two sets X and X’ ? X’ is the new set, except that it does not contain the universal program y.

The answer is analogous to the decision of countability of the set of natural numbers. The set of natural numbers is infinite but still countable! How large is the new set of natural numbers when you take one element out of the set? Still infinite?


Now try to transfer the knowledge obtained here to the subject of artificial intelligence, then you know how powerful the artificial intelligence can be or is unofficially.

Here are some “official” computer science topics. The focus is on the term “official“:

Side note

Imagine there would be no wars in this world. Most of the wars/civil wars are on militarily important strategy points. What a coincidence 😉 ?

Not everything that one can formulate in mathematics is a projection of the reality or is physically possible. In physics there is an upper limit, see my article “The Infinite Creator’s power and the limited technical power/science”.

Moore’s law

What often wrongly interpreted (also by many professors) is the well-known “law” of Moore. Moore was the co-founder of Intel. The word “law” is totally misleading. It is not a law, only pure calculus – economic calculation!

It is also the case that many scientific achievements haven’t been presented officially to the world. You can connect this with my sentence from “Side note: Imagine there would be no wars in this world.” This push the whole thing into a new dimension of information. Please note also that there are more than one truth. This new dimension is one of many! One of the thing is also that if you present all the scientific achievements at once, you can’t reach the maximum profit. I am referring for the first time on harmless achievements. This is one of the reason why not all countries in this world had the same chance to reach wealth – without wars/civil wars, conflicts, knowledge hiding, corruption, terror, organised crime etc.!

You can make more profit if you artificially stifle the countries of the world and slowly awake one after the other. This is the only way to control the money and power cycle.

Similar and additional posts