Written by Min-Koo Seo.

Concept of undecidable is one of the most important ideas because undecidability limits boundary of computation. However, we do not have any algorithms which can find out whether a certain problem is undecidable or not.

Typical undecidable problem is halting problem – a concern about halting property of a certain machine. Although halting problem is typical, it is hard to transform certain problem to halting problem, so PC-solution is used.

PC-solution is the solution of Post Correspondence Problem. Suppose there are two variables which contains n strings as follows:

A = w1,w2,…,wn
B = v1,v2,…vn

Finding PC-solution is to find out i and j of string index such that

wi wi+1 … wj = vi vi+1 … vj.

Showing whether this problem is undecidable is not easy, so MPC-solution – Modified Post Correspondece Problem – is used to prove the undecidability of PC-solution.

Virtue of PC-solution lies in the fact that it is convenient to transform a certain problem to PC-solution problem. However, chaning a certain problem is PC-solution problem is not decidable.

Suppose there exists a certain Turing Machine, i.e., mechanical way, which transform a certain problem to PC-solution problem. If such a Turing Machine is extant, undecidable becomes decidable, so conflict occurs.

My personal assumption behind the scene is that a solution of undecidable problem should not halt. If this is the case, deciding undecidability becomes halting problem. Now, suppose the existence of transforming algorithm which transmutes a certain problem to PC-solution problem. If such a algorithm exists, we can conclude that any machine – we do not know wheter this machine halt or not – can be transformed to PC-solution problem – we do know whether this machine halt or not -, so we can make a halting problem solution.

The allegation of equality assumption between halting problem and undecidability is very dangerous here, but I do not know whether this assumption is true or not. In fact, Mr. Shin insisted equivalence between halting and undecidability and to some extent, I agree with his idea.

In sum, transforming a certain machine to PC-solution must be unmechanical. So, we never, ever enumerate all problems which can not be solved by mathematics.