Re: Flibble’s Leap: Why Behavioral Divergence Implies a Type Distinction in the Halting Problem

On 5/12/2025 11:32 AM, Ben Bacarisse wrote:

Richard Heathfield <rjh@cpax.org.uk> writes:
 

On 11/05/2025 17:29, olcott wrote:

On 5/11/2025 10:34 AM, Mr Flibble wrote:

On Sun, 11 May 2025 16:25:14 +0100, Richard Heathfield wrote:
>

For a question to be semantically incorrect, it takes more than just
you
and your allies to be unhappy with it.

>
For a question to be semantically correct, it takes more than just you
and
your allies to be happy with it.
>
Your turn, mate.
>
/Flibble

For a polar yes/no question to be proven incorrect
only requires that both yes and no are the wrong answer.

>
Fair enough.
>
Definition: YNA - a type of answer that has exactly one of exactly two
possible values, either 'yes' xor 'no' - not both, not neither, and not
banana or half-past four.
>
The two questions I presented upthread, which I'll now label QA and QB, are
both of type YNA. They are as follows:
>
QA: "P is a syntactically correct program in some well-defined
Turing-complete language. Does P stop when it is applied to this data
X?"

 Sometimes PO accepts this a yes/no question with a correct answer in
every case and sometimes he does not.  On those days when he does accept
it, he asserts (quite unambiguously -- I can post a direct quote or a
message ID) that no is sometimes the correct answer even when P(X)
halts.
 

The Tarski undefinability theorem totally fails when
it is understood that every form of the Liar Paradox
is simply not a truth bearer, thus the Liar Paradox
must be rejected as not an element of any formal
system of mathematical logic.

QB: ``Is it possible to write a program that answers QA for arbitrary P and
arbitrary X?"
>
For any P and any X, QA has a correct YNA answer. What that answer is
depends on P and X, but QA(P,X) can correctly answer with one valid YNA
response or the other.

 But on some days, PO does /not/ accept that there is a correct yes/no
answer to QA in every case.  On those days, he thinks there is a
"pathological input" for which there is no correct answer.
 

I have dropped my other view that that the halting
problem counter-example input is malformed because
its recursive simulation prevents the "do the opposite"
of whatever its corresponding termination analyzer reports
is unreachable code.

This was a very common problem with students.  They so buy into the
assumption "let H be a TM that decides halting" that they think that H'
and H^ (to use Linz's notation) also exist and so there really is a
concrete string of symbols (the encoding of H^ which I write as [H^])
such that H^([H^]) halts if it doesn't and doesn't halt if it does.
 Of course, there are no pathological inputs like this because H does not
exist.  For every TM, M, the machines M' and M^ do indeed exist, [M^]
really is some finite string of symbols and M^([M^]) either halts or it
does not halt.  But because none of the infinite variety of Ms
implements the halting function, there is no paradox or pathological
input anywhere to be seen.
 Aside...  Forgive me for repeatedly replying to you.  It's because I
know you from comp.lang.c and because you are, I think, new to this
thread which has been going on for over 20 years.  I think everyone else
here knows the history, but you might not know what PO has said in the
past and, anyway, I think it helps to remind everyone that PO has given
the game away more than once.
 All the recent junk using x86 simulations was once very much clearer.
He posted a function:
 u32 Halts(u32 P, u32 I)
{
  static u32* execution_trace;
  slave_state->EIP = P;                    // Function to invoke
  while (!Aborted)
  {
    u32 EIP = slave_state->EIP;            // Instruction to be executed
    DebugStep(master_state, slave_state);  // Execute this instruction
    PushBack(local_execution_trace_list, EIP);
    Aborted = Needs_To_Be_Aborted(execution_trace, (u32)Halts);
  }
  return 0;  // Does not halt
END_OF_CODE: // Input has normally terminated
  return 1;
}
 and explained that 0 (does not halt) is the correct return for the
classic "confounding input" like so:
    "When we comment out the line of Halts() that tests for its need to
   abort then H_Hat() remains in infinite recursion, proving that its
   abort decision was correct."
 All really clear: Halts is correct because it reports on what some other
program would do -- the H_Hat constructed from the modified Halts
function without the like that stops the simulation!
 That was way too clear, so we got all more recent guff and, as far as I
know, he no loner ties to justify this ruse quite so explicitly.  His
argument is now that the simulation is correct right up until the point
when it isn't (as Mike Terry demonstrated quite explicitly).
 

Try to show how the "do the opposite" code
is reachable from DD correctly simulated by HHH.
int DD()
{
   int Halt_Status = HHH(DD);
   if (Halt_Status)
     HERE: goto HERE;
   return Halt_Status;
}
--
Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer