Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: Simulating Halt Decider Copyright 2022 Mr Flibble
Date: Sun, 2 Mar 2025 11:23:12 +0200
Organization: -
Lines: 66
Message-ID: <vq1820$ne68$1@dont-email.me>
References: <0qg7sjlnvataaqrgv0207nednemnqpubqu@4ax.com> <vq0jvg$gksp$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 02 Mar 2025 10:23:14 +0100 (CET)
Injection-Info: dont-email.me; posting-host="a72b0c126c3da1d8eeb41eb14669e115";
	logging-data="768200"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18kxGFU7T2FsNAJalICwiZh"
User-Agent: Unison/2.2
Cancel-Lock: sha1:nSUAf5/Zc+i8W6iAGzSHV+gKyT8=
Bytes: 3073

On 2025-03-02 03:40:31 +0000, olcott said:

> On 3/1/2025 8:33 PM, Mr Flibble wrote:
>> Hi!
>> 
>> I have an idea for a signaling simulating halt decider that forks the
>> simulation into two branches if the input calls the halt decider as
>> per [Strachey 1965]'s "Impossible Program":
>> 
> 
> The signalling aspect that forks is your idea.
> 
> It is established all over the place for
> many years that "simulating halt decider" is my idea.
> 
>> void P(void (*x)())
>> {
>> 	if (H(x, x))
>> 		infinite_loop: goto infinite_loop;
>> 	return;
>> }
>> 
>> int main()
>> {
>> 	std::cout << "Input halts: " << H(P, P) << std::endl;
>> }
>> 
>> When the simulator detects the call to H in P it forks the simulation
>> into a non-halting branch (returning 0 to P) and a halting branch
>> (returning 1 to P) and continues the simulation of these two branches
>> in parallel.
>> 
>> If the non-halting branch is determined to halt AND the halting branch
>> is determined to not halt then pathology is detected and reported via
>> a sNaP (signaling Not a Program) signal (analogous to IEEE 754's
>> sNaN (signaling Not a Number) signal)
>> 
>> If EITHER branch is determined to be correctly decided then that will
>> be the decision of the halting decider.
>> 
>> Crucially this scheme will handle (and correctly decide) the
>> following case whereby the result of H is discarded by the input:
>> 
>> void Px(void (*x)())
>> {
>> 	(void) H(x, x);
>> 	return;
>> }
>> 
>> Obviously my idea necessitates extending the definition of a halt
>> decider:
>> 
>> 1) Decider decision is HALTS if input halts.
>> 2) Decider decision is NON-HALTING if input does not halt.
>> 3) Decider rejects pathological input as invalid by signaling sNaP.
>> 
>> Thoughts?  I am probably missing something obvious as my idea
>> appears to refute [Strachey 1965] and associated HP proofs which
>> great minds have mulled over for decades.

A program that on some voaid input does not decide HALTS or NON-HALTING
is not a halt decider and therefore does not refute Strachey's proof.

-- 
Mikko