XPost: comp.theory, sci.logic, sci.math   
   From: 643-408-1753@kylheku.com   
      
   On 2025-11-17, olcott  wrote:   
   > On 11/17/2025 4:45 PM, Tristan Wibberley wrote:   
   >> On 17/11/2025 22:15, Alan Mackenzie wrote:   
   >>   
   >>> There is no proper academic conversation to be had over 2 + 2 = 4.  It is   
   >>> firm, unassailable knowledge, unchallengeable.  The Halting Theorem is of   
   >>> the same status, proven using the same methodology from the same   
   >>> fundamentals.   
   >>   
   >>   
   >> It's a completely different league from 2 + 2 = 4.   
   >> It's closer to x = 1/2 + x/2 but it's still conceptually /much/ harder   
   >> than that.   
   >> It's more like the problem of whether a fixed point exists or not, but   
   >> it's for the fixed point of a limit of a particular, conceptually weird,   
   >> sequence of functions.   
   >>   
   >> It really is quite peculiar.   
   >>   
   >   
   > Ultimately it is essentially the Liar Paradox in disguise.   
      
   No it isn't; not every self reference is Liar Paradox.   
      
   It is your /conjecture/ that the incomputability of halting somehow   
   contains the Liar Paradox; but it doesn't withstand rational scrutiny.   
      
   Here is why:   
      
   Self-reference occurs in the diagonal proof of the Halting Theorem.   
   It is this: the diagonal test case D refers to itself; it passes   
   itself to a decision algorithm.   
      
   - D is not a logical proposition. D might not even be calculating   
     a Boolean result.   
      
   - D is not contradicting itself in any way, saying "I am false".   
     It cannot do that because it's not a proposition; it has no truth   
     value, and doesn't assert any truth value.   
      
   - D does contradict something.   
      
   The contradiction is something like the one in "This sentence has   
   four words", though not quite.   
      
   In this analogy, the role of H(D) is the sentence itself: just like H(D)   
   makes an assertion of truth, so does the sentence.   
      
   The role of D is the word count of the sentence.   
      
   D contradicts H(D) through its behavior.   
      
   The word count of the sentence also contradicts that sentence   
   through its "behavior": its property of being five rather than four.   
      
   The important thing here is that "This sentence has four words"   
   is not the Liar Paradox.   
      
   > The Liar Paradox formalized in the Prolog Programming language   
      
   ... even if it were done correctly, wouldn't prove that halting is based   
   on the Liar Paradox.   
      
   Yes, we can model the Liar Paradox in languages and show how it   
   leads to infinite regress. E.g. Common Lisp:   
      
     [1]> #1=(not #1#)   
      
     *** - Program stack overflow. RESET   
      
   The expression #1=(not #1) is a complete, direct representation   
   of Liar as a Lisp expression. We do not need numerous lines of   
   Prolog.   
      
   #1=WHATEVER means "read WHATEVER object and associate it with   
   the integer label 1".   
      
   And then #1# means "do not read an object; instead return a reference   
   to the object previously associated with label 1".   
      
   This expression is saying exactly "The negation (not) of the expression,   
   which is myself, is true"; i.e. "This esxpression is false".   
      
   The "Program stack overflow" response in the CLISP implementation of   
   Common Lisp occurs when CLISP tries to traverse the syntax tree   
   of that expression to look for macros to expand. So we don't even   
   get to evaluation. The traversal triggers runaway recursion.   
      
      
   --   
   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)