How to prove that "Total" is not recursive (decidable)

343 views Asked by At
Halt = { f,x | f(x)↓ } is re (semi-decidable) but undecidable

Total = { f | ∀x f(x)↓ } is non-re (not even semi-decidable) 

I need some help in proving that the Total problem is not recursive (decidable).

I know the diagonalization proof for the Halting problem, I just need the same kind of proof for the Total problem. I'm posting the Halting Problem Proof for reference:

Halting Problem Proof

Assume we can decide the halting problem. Then there exists some total function Halt such that

            1 if [x] (y) is defined 
Halt(x,y) = 
            0 if [x] (y) is not defined 

Here, we have numbered all programs and [x] refers to the x-th program in this ordering. We can view Halt as a mapping from ℵ into ℵ by treating its input as a single number representing the pairing of two numbers via the one-one onto function

pair(x,y) = <x,y> = 2^x (2y + 1) – 1 
with inverses 
      <z>1 = exp(z+1,1) 

<z>2 = ((( z + 1 ) // 2^<z>1) – 1 ) // 2 

Now if Halt exist, then so does Disagree, where

             0             if Halt(x,x) = 0, i.e, if Φx (x) is not defined 
Disagree(x) = 
             µy (y == y+1) if Halt(x,x) = 1, i.e, if Φx (x) is defined 

Since Disagree is a program from ℵ into ℵ , Disagree can be reasoned about by Halt. Let d be such that Disagree = Φd, then

Disagree(d) is defined ⇔ Halt(d,d) = 0 ⇔ Φd (d) is undefined ⇔ Disagree(d) is undefined

But this means that Disagree contradicts its own existence. Since every step we took was constructive, except for the original assumption, we must presume that the original assumption was in error. Thus, the Halting Problem is not solvable.

0

There are 0 answers