Halting problem functions: (Pascal version)

the following obviously always halt or never halt:

   function always(n : integer) : integer ;
   begin
        always := n ;
   end;

   function never(n : integer) : integer ;
   begin 
        repeat until false ;
        never := n ;
   end ;

these sometimes halt (for even n) and sometimes loop (for odd n):

   function sometimes (n : integer) : integer ;
   begin 
        if odd(n)
           then sometimes := never(n)
           else sometimes := always(n) ;
   end ;

   function sometimes2 (n : integer) : integer ;
   begin
        count := 0
        if odd(n)
           then repeat Inc(count); n := 3 * n;  until n=1
           else repeat Inc(count); n := n div 2 ; until n=1 ;
        sometimes2 := count ;
   end ;

these take n steps to halt for 2n , but take longer when other numbers are encountered

• looper can loop, eg. for looper(5)
• who_knows returns
• 3 1 7 2 5 8 16 13 19 6 ...
• but maybe can loop - who knows?

   function looper ( n : integer) : integer ;
   { Try  5  - 14 - 7 - 20 - 10 - 5 - infinite loop}
   var count : integer ;
   begin
        count := 0 ;
        repeat
           Inc(count) ;
           if odd(n)
              then n := 3 * n - 1
              else n := n div 2 ;
        until n=1 ;
        looper := count ;
   end ;

   function who_knows(n : integer) : integer ;
   { wild oscillations, but no-one knows if can loop indefinitely }
   var count : integer ;
   begin 
        count := 0 ;
        repeat
            Inc(count) ;
            if odd(n)
               then n := 3 * n + 1
               else n := n div 2 ;
        until n=1 ;
        who_knows := count ;
   end ;

now for the proof

• define two functions (here we use string arguments - coding)

   function halts( funcstr, inpstr : string) : boolean ;
   { assume this function exists }
   begin
        if func(inpstr) loops
           then halts := false
           else halts := true ;
   end ;

   function loops ( funcstr: string) : boolean ;
   { loops if func(funcstr) halts}
   begin
        if halts(funcstr, funcstr) 
           then loops := never(0)
           else loops := false ; 
   end ;

what about loops(loopstr) ?

• if loops then must be halts(loopstr,loopstr)
• i.e. loops(loopstr) doesn’t loop !
• if doesn’t loop then loops := false
• i.e. not halts(loopstr,loopstr) ie loops(loopstr) loops !
• by reductio ad absurdum - there can be no such function
• QED