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?
Conclusion
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“:
- Atlas, The Next Generation (Boston Dynamic, Subsidiary of Google)
- Four-Legged Robot (Boston Dynamics, Subsidiary of Google)
- Unsichere Computer heilten sich selbst (this article is in german)
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
- Russell’s paradox / Barber paradox
- The Infinite Creator’s / artificer’s power and the limited technical power/science
- Das Nichts in der Mathematik (Telepilis article, only in German language)
[Translation of the heading: “The nothing in mathematics”] - The Infinite Creator’s power and the limited technical power / science