XPost: comp.theory, sci.logic, sci.math   
   From: 643-408-1753@kylheku.com   
      
   On 2025-11-19, Tristan Wibberley  wrote:   
   > On 17/11/2025 22:58, Kaz Kylheku wrote:   
   >> - continuing to use impure functions (e.g. mutating global   
   >>   execution trace buffer; distinguishing "Root == 1" H   
   >>   functions from "Root == 0").   
   >   
   > Woah there fella! The halting problem is about state machines, not pure   
   > functions.   
      
   Recursive functions and Turing machines are equivalent. The halting   
   problem is about recursive functions too.   
      
   In any case, topics in the halting problem cannot be properly explored   
   using impure procedures --- not in such a way that we assume that those   
   procedures directly correspond to recursive functions.   
      
   We can't have a procedure H whch has two behaviors based on whether it   
   is the first invocation or subsequent, and talk about that procedure as   
   a single recursive function H.   
      
   We may be able to model that function H as another function H' that   
   takes additional arguments representing all the external state that H   
   depends on. It becomes H(P, Root) instead of H(P). Then it is obvious   
   that H(D, True) and H(D, False) are different deciders.  We have to   
   explicitly pick which one of those two the diagonal case D invokes.   
      
   --   
   TXR Programming Language: http://nongnu.org/txr   
   Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal   
   Mastodon: @Kazinator@mstdn.ca   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)