Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott333@gmail.com>
Newsgroups: comp.theory
Subject: =?UTF-8?Q?Re=3A_Flibble=E2=80=99s_Leap=3A_Why_Behavioral_Divergence?=
 =?UTF-8?Q?_Implies_a_Type_Distinction_in_the_Halting_Problem?=
Date: Mon, 12 May 2025 11:52:48 -0500
Organization: A noiseless patient Spider
Lines: 135
Message-ID: <vvt910$14pca$21@dont-email.me>
References: <vv1UP.77894$JJT6.54808@fx16.ams4> <vvqd4u$g8a1$1@dont-email.me>
 <7N2UP.527443$wBt6.464256@fx15.ams4> <vvqfgq$gmmk$1@dont-email.me>
 <os3UP.670056$BFJ.223954@fx13.ams4> <vvqja4$gldn$10@dont-email.me>
 <vvql92$g8ck$4@dont-email.me> <87ikm5oklo.fsf@bsb.me.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Mon, 12 May 2025 18:52:49 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="15cac720ddbb61c7f6586fe023932af8";
	logging-data="1205642"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19rNcIxLHDjwfw8GWEDMiVG"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:OFTbiSxGN5lSXdxiY2ylYJyMIUA=
In-Reply-To: <87ikm5oklo.fsf@bsb.me.uk>
X-Antivirus: Norton (VPS 250512-4, 5/12/2025), Outbound message
Content-Language: en-US
X-Antivirus-Status: Clean

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