Thursday, October 08, 2009

On other implications of Halting problem being not solvable

The Halting problem is a fundamental result in Complexity theory which says that a Turing Machine cannot be created which can solve all problems that could be decided in finite time. If such a machine could be created it could be shown to be self contradictory through diagnolization principle (assuming a problem has been solved by that machine, another problem can be created with opposite results which the machine then cannot solve). This concept was used by Godel to prove his incompleness theorem. The theorem says that you cannot create a set of principles(axioms) that can prove all mathematical statements with completeness(prove all statements true), and soundness(prove all wrong statements false). He said if such a proof system were created, it would solve the halting problem, an impossibility. The implications of this approach are very large. It puts a fundamental limits on what mankind can achieve. Take a glance.

a. A society where everyone is equally rich cannot be created: To create an equal society you will have to create a perfect set of distribution laws, and if it were created, diagonalization can show it to self contradictory. I will ignore diagnolization inferences in remaining parallelizations.

b. Mankind cannot solve all problems in Science..there will always be unsolved problems. Researchers be happy.."Everything that needs to be discovered has been discovered" will never happen.

c. A pure society created on the principles of Koran, Ram Rajya or any other religious conjecture will never achieve perfect happiness for its members: If such a society were created, an equivalent Turing Machine could be created that would solve the happiness function. And through diagnolization it could be shown that an alternate happiness function exists for the same solution which would be contradictory to results already obtained, an impossibility.

d. Poverty can never be eliminated from the face of earth: If poverty were eliminated, through diagonalization it can be shown that an alternate defnition of poverty function exists, and a contradiction would appear in society.

Can you think of others :)

0 Comments:

Post a Comment

<< Home