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":

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.

/Flibble

On 4/22/23 7:43 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":
>
> 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.
>
> /Flibble

So, see if you can show an actual use for your altered definition of
Halt Decoding.

You also need to clarify the rules of you computation system, as you
have previously commented that it can't obey the "normal" rules used in
computability theory.

Also, how does your decider determine if the branch it is following is
non-halting.

On 23/04/2023 12:53 am, Richard Damon wrote:
> On 4/22/23 7:43 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":
>>
>> 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.
>>
>> /Flibble
>
> So, see if you can show an actual use for your altered definition of
> Halt Decoding.

It will decide that P() is pathological input and it will decide that
Px() is halting.

>
> You also need to clarify the rules of you computation system, as you
> have previously commented that it can't obey the "normal" rules used in
> computability theory.

I believe you are referring to the fact that the halt decider function
and the intrinsic H(...) are a property of the machine itself, H is much
like the "move tape left" function of a Turing Machine. The only thing
"abnormal" about it is that such a function is not included in the
traditional definition of a Turing Machine.

>
> Also, how does your decider determine if the branch it is following is
> non-halting.

The way any simulating halt decider would: through the detection of
repeated state given the machine and its resources are finite in size.

/Flibble

On 4/22/2023 7:31 PM, Mr Flibble wrote:
> On 23/04/2023 12:53 am, Richard Damon wrote:
>> On 4/22/23 7:43 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":
>>>
>>> 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.
>>>
>>> /Flibble
>>
>> So, see if you can show an actual use for your altered definition of
>> Halt Decoding.
>
> It will decide that P() is pathological input and it will decide that
> Px() is halting.
>
>>
>> You also need to clarify the rules of you computation system, as you
>> have previously commented that it can't obey the "normal" rules used
>> in computability theory.
>
> I believe you are referring to the fact that the halt decider function
> and the intrinsic H(...) are a property of the machine itself, H is much
> like the "move tape left" function of a Turing Machine.  The only thing
> "abnormal" about it is that such a function is not included in the
> traditional definition of a Turing Machine.
>
>>

>> Also, how does your decider determine if the branch it is following is
>> non-halting.
>
> The way any simulating halt decider would: through the detection of
> repeated state given the machine and its resources are finite in size.
>
> /Flibble

You got the essence of that most important part correctly.

--
Copyright 2023 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer

On 4/22/23 8:31 PM, Mr Flibble wrote:
> On 23/04/2023 12:53 am, Richard Damon wrote:
>> On 4/22/23 7:43 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":
>>>
>>> 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.
>>>
>>> /Flibble
>>
>> So, see if you can show an actual use for your altered definition of
>> Halt Decoding.
>
> It will decide that P() is pathological input and it will decide that
> Px() is halting.
>

But those are just toy programs (P was just a simple program to show
classical halting to not be useful)

What USEFUL resutls can be gotten with your decider. Based on the
following answers, its hard to see one.

>>
>> You also need to clarify the rules of you computation system, as you
>> have previously commented that it can't obey the "normal" rules used
>> in computability theory.
>
> I believe you are referring to the fact that the halt decider function
> and the intrinsic H(...) are a property of the machine itself, H is much
> like the "move tape left" function of a Turing Machine.  The only thing
> "abnormal" about it is that such a function is not included in the
> traditional definition of a Turing Machine.

Your whole model of computation is at significant variance from the
classical theoretical model.

>
>>
>> Also, how does your decider determine if the branch it is following is
>> non-halting.
>
> The way any simulating halt decider would: through the detection of
> repeated state given the machine and its resources are finite in size.

So only able to detect non-halting in machines goig into repeating
loops, and not just that the computation keeps growing unbounded.

A very small set of the problems of normal interest in the theory.

>
> /Flibble

On 23/04/2023 1:39 am, Richard Damon wrote:
> On 4/22/23 8:31 PM, Mr Flibble wrote:
>> On 23/04/2023 12:53 am, Richard Damon wrote:
>>> On 4/22/23 7:43 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":
>>>>
>>>> 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.
>>>>
>>>> /Flibble
>>>
>>> So, see if you can show an actual use for your altered definition of
>>> Halt Decoding.
>>
>> It will decide that P() is pathological input and it will decide that
>> Px() is halting.
>>
>
> But those are just toy programs (P was just a simple program to show
> classical halting to not be useful)
>
> What USEFUL resutls can be gotten with your decider. Based on the
> following answers, its hard to see one.
>
>>>
>>> You also need to clarify the rules of you computation system, as you
>>> have previously commented that it can't obey the "normal" rules used
>>> in computability theory.
>>
>> I believe you are referring to the fact that the halt decider function
>> and the intrinsic H(...) are a property of the machine itself, H is
>> much like the "move tape left" function of a Turing Machine.  The only
>> thing "abnormal" about it is that such a function is not included in
>> the traditional definition of a Turing Machine.
>
> Your whole model of computation is at significant variance from the
> classical theoretical model.
>
>>
>>>
>>> Also, how does your decider determine if the branch it is following
>>> is non-halting.
>>
>> The way any simulating halt decider would: through the detection of
>> repeated state given the machine and its resources are finite in size.
>
> So only able to detect non-halting in machines goig into repeating
> loops, and not just that the computation keeps growing unbounded.

Repeated state means a duplicate hash of the machine's finite state.

>
> A very small set of the problems of normal interest in the theory.

The size of the set is relative. You are missing the point: to be
computable the machine's resources can not be unbounded. Only problems
that are computable using the technology of the present era are of
interest: one has to be a pragmatist.

/Flibble

On 4/22/23 9:55 PM, Mr Flibble wrote:
> On 23/04/2023 1:39 am, Richard Damon wrote:
>> On 4/22/23 8:31 PM, Mr Flibble wrote:
>>> On 23/04/2023 12:53 am, Richard Damon wrote:
>>>> On 4/22/23 7:43 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":
>>>>>
>>>>> 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.
>>>>>
>>>>> /Flibble
>>>>
>>>> So, see if you can show an actual use for your altered definition of
>>>> Halt Decoding.
>>>
>>> It will decide that P() is pathological input and it will decide that
>>> Px() is halting.
>>>
>>
>> But those are just toy programs (P was just a simple program to show
>> classical halting to not be useful)
>>
>> What USEFUL resutls can be gotten with your decider. Based on the
>> following answers, its hard to see one.
>>
>>>>
>>>> You also need to clarify the rules of you computation system, as you
>>>> have previously commented that it can't obey the "normal" rules used
>>>> in computability theory.
>>>
>>> I believe you are referring to the fact that the halt decider
>>> function and the intrinsic H(...) are a property of the machine
>>> itself, H is much like the "move tape left" function of a Turing
>>> Machine.  The only thing "abnormal" about it is that such a function
>>> is not included in the traditional definition of a Turing Machine.
>>
>> Your whole model of computation is at significant variance from the
>> classical theoretical model.
>>
>>>
>>>>
>>>> Also, how does your decider determine if the branch it is following
>>>> is non-halting.
>>>
>>> The way any simulating halt decider would: through the detection of
>>> repeated state given the machine and its resources are finite in size.
>>
>> So only able to detect non-halting in machines goig into repeating
>> loops, and not just that the computation keeps growing unbounded.
>
> Repeated state means a duplicate hash of the machine's finite state.

But not suitable for things like the Twin Primes problem or Collatz
Conjecture.

Most of the interesting problems don't end up in a simple infinite loop,
but a loop counting through numbers that will never reach there terminal
condition.
>
>>
>> A very small set of the problems of normal interest in the theory.
>
> The size of the set is relative.  You are missing the point: to be
> computable the machine's resources can not be unbounded.  Only problems
> that are computable using the technology of the present era are of
> interest: one has to be a pragmatist.
>
> /Flibble

For many of the problems, the "limited" memory of the modern computer is
unlikely to be the major limit. The "Very small set" was the number of
problems that can be handled, not the physical size of the problems.

Remember, the problems that Halting was designed for were things that a
person with paper and pencil were trying to solve. Detecting "simple"
loops wasn't the problem.

On 23/04/2023 3:42 am, Richard Damon wrote:
> On 4/22/23 9:55 PM, Mr Flibble wrote:
>> On 23/04/2023 1:39 am, Richard Damon wrote:
>>> On 4/22/23 8:31 PM, Mr Flibble wrote:
>>>> On 23/04/2023 12:53 am, Richard Damon wrote:
>>>>> On 4/22/23 7:43 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":
>>>>>>
>>>>>> 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.
>>>>>>
>>>>>> /Flibble
>>>>>
>>>>> So, see if you can show an actual use for your altered definition
>>>>> of Halt Decoding.
>>>>
>>>> It will decide that P() is pathological input and it will decide
>>>> that Px() is halting.
>>>>
>>>
>>> But those are just toy programs (P was just a simple program to show
>>> classical halting to not be useful)
>>>
>>> What USEFUL resutls can be gotten with your decider. Based on the
>>> following answers, its hard to see one.
>>>
>>>>>
>>>>> You also need to clarify the rules of you computation system, as
>>>>> you have previously commented that it can't obey the "normal" rules
>>>>> used in computability theory.
>>>>
>>>> I believe you are referring to the fact that the halt decider
>>>> function and the intrinsic H(...) are a property of the machine
>>>> itself, H is much like the "move tape left" function of a Turing
>>>> Machine.  The only thing "abnormal" about it is that such a function
>>>> is not included in the traditional definition of a Turing Machine.
>>>
>>> Your whole model of computation is at significant variance from the
>>> classical theoretical model.
>>>
>>>>
>>>>>
>>>>> Also, how does your decider determine if the branch it is following
>>>>> is non-halting.
>>>>
>>>> The way any simulating halt decider would: through the detection of
>>>> repeated state given the machine and its resources are finite in size.
>>>
>>> So only able to detect non-halting in machines goig into repeating
>>> loops, and not just that the computation keeps growing unbounded.
>>
>> Repeated state means a duplicate hash of the machine's finite state.
>
> But not suitable for things like the Twin Primes problem or Collatz
> Conjecture.
>
> Most of the interesting problems don't end up in a simple infinite loop,
> but a loop counting through numbers that will never reach there terminal
> condition.
>   >
>>>
>>> A very small set of the problems of normal interest in the theory.
>>
>> The size of the set is relative.  You are missing the point: to be
>> computable the machine's resources can not be unbounded.  Only
>> problems that are computable using the technology of the present era
>> are of interest: one has to be a pragmatist.
>>
>> /Flibble
>
> For many of the problems, the "limited" memory of the modern computer is
> unlikely to be the major limit. The "Very small set" was the number of
> problems that can be handled, not the physical size of the problems.
>
> Remember, the problems that Halting was designed for were things that a
> person with paper and pencil were trying to solve. Detecting "simple"
> loops wasn't the problem.

I am not sure why you are equating repeated finite state with "simple"
loops.

/Flibble

On 4/22/23 11:47 PM, Mr Flibble wrote:
> On 23/04/2023 3:42 am, Richard Damon wrote:
>> On 4/22/23 9:55 PM, Mr Flibble wrote:
>>> On 23/04/2023 1:39 am, Richard Damon wrote:
>>>> On 4/22/23 8:31 PM, Mr Flibble wrote:
>>>>> On 23/04/2023 12:53 am, Richard Damon wrote:
>>>>>> On 4/22/23 7:43 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":
>>>>>>>
>>>>>>> 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.
>>>>>>>
>>>>>>> /Flibble
>>>>>>
>>>>>> So, see if you can show an actual use for your altered definition
>>>>>> of Halt Decoding.
>>>>>
>>>>> It will decide that P() is pathological input and it will decide
>>>>> that Px() is halting.
>>>>>
>>>>
>>>> But those are just toy programs (P was just a simple program to show
>>>> classical halting to not be useful)
>>>>
>>>> What USEFUL resutls can be gotten with your decider. Based on the
>>>> following answers, its hard to see one.
>>>>
>>>>>>
>>>>>> You also need to clarify the rules of you computation system, as
>>>>>> you have previously commented that it can't obey the "normal"
>>>>>> rules used in computability theory.
>>>>>
>>>>> I believe you are referring to the fact that the halt decider
>>>>> function and the intrinsic H(...) are a property of the machine
>>>>> itself, H is much like the "move tape left" function of a Turing
>>>>> Machine.  The only thing "abnormal" about it is that such a
>>>>> function is not included in the traditional definition of a Turing
>>>>> Machine.
>>>>
>>>> Your whole model of computation is at significant variance from the
>>>> classical theoretical model.
>>>>
>>>>>
>>>>>>
>>>>>> Also, how does your decider determine if the branch it is
>>>>>> following is non-halting.
>>>>>
>>>>> The way any simulating halt decider would: through the detection of
>>>>> repeated state given the machine and its resources are finite in size.
>>>>
>>>> So only able to detect non-halting in machines goig into repeating
>>>> loops, and not just that the computation keeps growing unbounded.
>>>
>>> Repeated state means a duplicate hash of the machine's finite state.
>>
>> But not suitable for things like the Twin Primes problem or Collatz
>> Conjecture.
>>
>> Most of the interesting problems don't end up in a simple infinite
>> loop, but a loop counting through numbers that will never reach there
>> terminal condition.
>>    >
>>>>
>>>> A very small set of the problems of normal interest in the theory.
>>>
>>> The size of the set is relative.  You are missing the point: to be
>>> computable the machine's resources can not be unbounded.  Only
>>> problems that are computable using the technology of the present era
>>> are of interest: one has to be a pragmatist.
>>>
>>> /Flibble
>>
>> For many of the problems, the "limited" memory of the modern computer
>> is unlikely to be the major limit. The "Very small set" was the number
>> of problems that can be handled, not the physical size of the problems.
>>
>> Remember, the problems that Halting was designed for were things that
>> a person with paper and pencil were trying to solve. Detecting
>> "simple" loops wasn't the problem.
>
> I am not sure why you are equating repeated finite state with "simple"
> loops.
>
> /Flibble

Because your "repeated state" method won't catch even fairly simple
issues like:

for(i = 100; i != 1; i -= 2;) {
// do something but don't change i
}

because the "state" never repeats

On 23/04/2023 12:27 pm, Richard Damon wrote:
> On 4/22/23 11:47 PM, Mr Flibble wrote:
>> On 23/04/2023 3:42 am, Richard Damon wrote:
>>> On 4/22/23 9:55 PM, Mr Flibble wrote:
>>>> On 23/04/2023 1:39 am, Richard Damon wrote:
>>>>> On 4/22/23 8:31 PM, Mr Flibble wrote:
>>>>>> On 23/04/2023 12:53 am, Richard Damon wrote:
>>>>>>> On 4/22/23 7:43 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":
>>>>>>>>
>>>>>>>> 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.
>>>>>>>>
>>>>>>>> /Flibble
>>>>>>>
>>>>>>> So, see if you can show an actual use for your altered definition
>>>>>>> of Halt Decoding.
>>>>>>
>>>>>> It will decide that P() is pathological input and it will decide
>>>>>> that Px() is halting.
>>>>>>
>>>>>
>>>>> But those are just toy programs (P was just a simple program to
>>>>> show classical halting to not be useful)
>>>>>
>>>>> What USEFUL resutls can be gotten with your decider. Based on the
>>>>> following answers, its hard to see one.
>>>>>
>>>>>>>
>>>>>>> You also need to clarify the rules of you computation system, as
>>>>>>> you have previously commented that it can't obey the "normal"
>>>>>>> rules used in computability theory.
>>>>>>
>>>>>> I believe you are referring to the fact that the halt decider
>>>>>> function and the intrinsic H(...) are a property of the machine
>>>>>> itself, H is much like the "move tape left" function of a Turing
>>>>>> Machine.  The only thing "abnormal" about it is that such a
>>>>>> function is not included in the traditional definition of a Turing
>>>>>> Machine.
>>>>>
>>>>> Your whole model of computation is at significant variance from the
>>>>> classical theoretical model.
>>>>>
>>>>>>
>>>>>>>
>>>>>>> Also, how does your decider determine if the branch it is
>>>>>>> following is non-halting.
>>>>>>
>>>>>> The way any simulating halt decider would: through the detection
>>>>>> of repeated state given the machine and its resources are finite
>>>>>> in size.
>>>>>
>>>>> So only able to detect non-halting in machines goig into repeating
>>>>> loops, and not just that the computation keeps growing unbounded.
>>>>
>>>> Repeated state means a duplicate hash of the machine's finite state.
>>>
>>> But not suitable for things like the Twin Primes problem or Collatz
>>> Conjecture.
>>>
>>> Most of the interesting problems don't end up in a simple infinite
>>> loop, but a loop counting through numbers that will never reach there
>>> terminal condition.
>>>    >
>>>>>
>>>>> A very small set of the problems of normal interest in the theory.
>>>>
>>>> The size of the set is relative.  You are missing the point: to be
>>>> computable the machine's resources can not be unbounded.  Only
>>>> problems that are computable using the technology of the present era
>>>> are of interest: one has to be a pragmatist.
>>>>
>>>> /Flibble
>>>
>>> For many of the problems, the "limited" memory of the modern computer
>>> is unlikely to be the major limit. The "Very small set" was the
>>> number of problems that can be handled, not the physical size of the
>>> problems.
>>>
>>> Remember, the problems that Halting was designed for were things that
>>> a person with paper and pencil were trying to solve. Detecting
>>> "simple" loops wasn't the problem.
>>
>> I am not sure why you are equating repeated finite state with "simple"
>> loops.
>>
>> /Flibble
>
> Because your "repeated state" method won't catch even fairly simple
> issues like:
>
> for(i = 100; i != 1; i -= 2;) {
> // do something but don't change i
> }
>
> because the "state" never repeats

Of course that state repeats (and will be caught): the integer "i" is of
finite size so it will eventually wrap around to have the same bit
pattern a second time.

/Flibble

On 4/23/23 8:47 AM, Mr Flibble wrote:
> On 23/04/2023 12:27 pm, Richard Damon wrote:
>> On 4/22/23 11:47 PM, Mr Flibble wrote:
>>> On 23/04/2023 3:42 am, Richard Damon wrote:
>>>> On 4/22/23 9:55 PM, Mr Flibble wrote:
>>>>> On 23/04/2023 1:39 am, Richard Damon wrote:
>>>>>> On 4/22/23 8:31 PM, Mr Flibble wrote:
>>>>>>> On 23/04/2023 12:53 am, Richard Damon wrote:
>>>>>>>> On 4/22/23 7:43 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":
>>>>>>>>>
>>>>>>>>> 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.
>>>>>>>>>
>>>>>>>>> /Flibble
>>>>>>>>
>>>>>>>> So, see if you can show an actual use for your altered
>>>>>>>> definition of Halt Decoding.
>>>>>>>
>>>>>>> It will decide that P() is pathological input and it will decide
>>>>>>> that Px() is halting.
>>>>>>>
>>>>>>
>>>>>> But those are just toy programs (P was just a simple program to
>>>>>> show classical halting to not be useful)
>>>>>>
>>>>>> What USEFUL resutls can be gotten with your decider. Based on the
>>>>>> following answers, its hard to see one.
>>>>>>
>>>>>>>>
>>>>>>>> You also need to clarify the rules of you computation system, as
>>>>>>>> you have previously commented that it can't obey the "normal"
>>>>>>>> rules used in computability theory.
>>>>>>>
>>>>>>> I believe you are referring to the fact that the halt decider
>>>>>>> function and the intrinsic H(...) are a property of the machine
>>>>>>> itself, H is much like the "move tape left" function of a Turing
>>>>>>> Machine.  The only thing "abnormal" about it is that such a
>>>>>>> function is not included in the traditional definition of a
>>>>>>> Turing Machine.
>>>>>>
>>>>>> Your whole model of computation is at significant variance from
>>>>>> the classical theoretical model.
>>>>>>
>>>>>>>
>>>>>>>>
>>>>>>>> Also, how does your decider determine if the branch it is
>>>>>>>> following is non-halting.
>>>>>>>
>>>>>>> The way any simulating halt decider would: through the detection
>>>>>>> of repeated state given the machine and its resources are finite
>>>>>>> in size.
>>>>>>
>>>>>> So only able to detect non-halting in machines goig into repeating
>>>>>> loops, and not just that the computation keeps growing unbounded.
>>>>>
>>>>> Repeated state means a duplicate hash of the machine's finite state.
>>>>
>>>> But not suitable for things like the Twin Primes problem or Collatz
>>>> Conjecture.
>>>>
>>>> Most of the interesting problems don't end up in a simple infinite
>>>> loop, but a loop counting through numbers that will never reach
>>>> there terminal condition.
>>>>    >
>>>>>>
>>>>>> A very small set of the problems of normal interest in the theory.
>>>>>
>>>>> The size of the set is relative.  You are missing the point: to be
>>>>> computable the machine's resources can not be unbounded.  Only
>>>>> problems that are computable using the technology of the present
>>>>> era are of interest: one has to be a pragmatist.
>>>>>
>>>>> /Flibble
>>>>
>>>> For many of the problems, the "limited" memory of the modern
>>>> computer is unlikely to be the major limit. The "Very small set" was
>>>> the number of problems that can be handled, not the physical size of
>>>> the problems.
>>>>
>>>> Remember, the problems that Halting was designed for were things
>>>> that a person with paper and pencil were trying to solve. Detecting
>>>> "simple" loops wasn't the problem.
>>>
>>> I am not sure why you are equating repeated finite state with
>>> "simple" loops.
>>>
>>> /Flibble
>>
>> Because your "repeated state" method won't catch even fairly simple
>> issues like:
>>
>> for(i = 100; i != 1; i -= 2;) {
>> // do something but don't change i
>> }
>>
>> because the "state" never repeats
>
> Of course that state repeats (and will be caught): the integer "i" is of
> finite size so it will eventually wrap around to have the same bit
> pattern a second time.
>
> /Flibble

Depends on its type. It could be a big int (infinite precision integer),
so it runs until the machine exhausts its memory.

On 23/04/2023 5:44 pm, Richard Damon wrote:
> On 4/23/23 8:47 AM, Mr Flibble wrote:
>> On 23/04/2023 12:27 pm, Richard Damon wrote:
>>> On 4/22/23 11:47 PM, Mr Flibble wrote:
>>>> On 23/04/2023 3:42 am, Richard Damon wrote:
>>>>> On 4/22/23 9:55 PM, Mr Flibble wrote:
>>>>>> On 23/04/2023 1:39 am, Richard Damon wrote:
>>>>>>> On 4/22/23 8:31 PM, Mr Flibble wrote:
>>>>>>>> On 23/04/2023 12:53 am, Richard Damon wrote:
>>>>>>>>> On 4/22/23 7:43 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":
>>>>>>>>>>
>>>>>>>>>> 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.
>>>>>>>>>>
>>>>>>>>>> /Flibble
>>>>>>>>>
>>>>>>>>> So, see if you can show an actual use for your altered
>>>>>>>>> definition of Halt Decoding.
>>>>>>>>
>>>>>>>> It will decide that P() is pathological input and it will decide
>>>>>>>> that Px() is halting.
>>>>>>>>
>>>>>>>
>>>>>>> But those are just toy programs (P was just a simple program to
>>>>>>> show classical halting to not be useful)
>>>>>>>
>>>>>>> What USEFUL resutls can be gotten with your decider. Based on the
>>>>>>> following answers, its hard to see one.
>>>>>>>
>>>>>>>>>
>>>>>>>>> You also need to clarify the rules of you computation system,
>>>>>>>>> as you have previously commented that it can't obey the
>>>>>>>>> "normal" rules used in computability theory.
>>>>>>>>
>>>>>>>> I believe you are referring to the fact that the halt decider
>>>>>>>> function and the intrinsic H(...) are a property of the machine
>>>>>>>> itself, H is much like the "move tape left" function of a Turing
>>>>>>>> Machine.  The only thing "abnormal" about it is that such a
>>>>>>>> function is not included in the traditional definition of a
>>>>>>>> Turing Machine.
>>>>>>>
>>>>>>> Your whole model of computation is at significant variance from
>>>>>>> the classical theoretical model.
>>>>>>>
>>>>>>>>
>>>>>>>>>
>>>>>>>>> Also, how does your decider determine if the branch it is
>>>>>>>>> following is non-halting.
>>>>>>>>
>>>>>>>> The way any simulating halt decider would: through the detection
>>>>>>>> of repeated state given the machine and its resources are finite
>>>>>>>> in size.
>>>>>>>
>>>>>>> So only able to detect non-halting in machines goig into
>>>>>>> repeating loops, and not just that the computation keeps growing
>>>>>>> unbounded.
>>>>>>
>>>>>> Repeated state means a duplicate hash of the machine's finite state.
>>>>>
>>>>> But not suitable for things like the Twin Primes problem or Collatz
>>>>> Conjecture.
>>>>>
>>>>> Most of the interesting problems don't end up in a simple infinite
>>>>> loop, but a loop counting through numbers that will never reach
>>>>> there terminal condition.
>>>>>    >
>>>>>>>
>>>>>>> A very small set of the problems of normal interest in the theory.
>>>>>>
>>>>>> The size of the set is relative.  You are missing the point: to be
>>>>>> computable the machine's resources can not be unbounded.  Only
>>>>>> problems that are computable using the technology of the present
>>>>>> era are of interest: one has to be a pragmatist.
>>>>>>
>>>>>> /Flibble
>>>>>
>>>>> For many of the problems, the "limited" memory of the modern
>>>>> computer is unlikely to be the major limit. The "Very small set"
>>>>> was the number of problems that can be handled, not the physical
>>>>> size of the problems.
>>>>>
>>>>> Remember, the problems that Halting was designed for were things
>>>>> that a person with paper and pencil were trying to solve. Detecting
>>>>> "simple" loops wasn't the problem.
>>>>
>>>> I am not sure why you are equating repeated finite state with
>>>> "simple" loops.
>>>>
>>>> /Flibble
>>>
>>> Because your "repeated state" method won't catch even fairly simple
>>> issues like:
>>>
>>> for(i = 100; i != 1; i -= 2;) {
>>> // do something but don't change i
>>> }
>>>
>>> because the "state" never repeats
>>
>> Of course that state repeats (and will be caught): the integer "i" is
>> of finite size so it will eventually wrap around to have the same bit
>> pattern a second time.
>>
>> /Flibble
>
> Depends on its type. It could be a big int (infinite precision integer),
> so it runs until the machine exhausts its memory.
>
> If you are admitting that you can only handle "finite" machines, then
> that has been a solved problem for a long time. Even the pathological
> program can be solved under finite memory limits (it will reach memory
> exhaustion), which of course needs to be a fourth response possible out
> of your decider.

On 4/23/23 1:06 PM, Mr Flibble wrote:
> On 23/04/2023 5:44 pm, Richard Damon wrote:
>> On 4/23/23 8:47 AM, Mr Flibble wrote:
>>> On 23/04/2023 12:27 pm, Richard Damon wrote:
>>>> On 4/22/23 11:47 PM, Mr Flibble wrote:
>>>>> On 23/04/2023 3:42 am, Richard Damon wrote:
>>>>>> On 4/22/23 9:55 PM, Mr Flibble wrote:
>>>>>>> On 23/04/2023 1:39 am, Richard Damon wrote:
>>>>>>>> On 4/22/23 8:31 PM, Mr Flibble wrote:
>>>>>>>>> On 23/04/2023 12:53 am, Richard Damon wrote:
>>>>>>>>>> On 4/22/23 7:43 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":
>>>>>>>>>>>
>>>>>>>>>>> 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.
>>>>>>>>>>>
>>>>>>>>>>> /Flibble
>>>>>>>>>>
>>>>>>>>>> So, see if you can show an actual use for your altered
>>>>>>>>>> definition of Halt Decoding.
>>>>>>>>>
>>>>>>>>> It will decide that P() is pathological input and it will
>>>>>>>>> decide that Px() is halting.
>>>>>>>>>
>>>>>>>>
>>>>>>>> But those are just toy programs (P was just a simple program to
>>>>>>>> show classical halting to not be useful)
>>>>>>>>
>>>>>>>> What USEFUL resutls can be gotten with your decider. Based on
>>>>>>>> the following answers, its hard to see one.
>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> You also need to clarify the rules of you computation system,
>>>>>>>>>> as you have previously commented that it can't obey the
>>>>>>>>>> "normal" rules used in computability theory.
>>>>>>>>>
>>>>>>>>> I believe you are referring to the fact that the halt decider
>>>>>>>>> function and the intrinsic H(...) are a property of the machine
>>>>>>>>> itself, H is much like the "move tape left" function of a
>>>>>>>>> Turing Machine.  The only thing "abnormal" about it is that
>>>>>>>>> such a function is not included in the traditional definition
>>>>>>>>> of a Turing Machine.
>>>>>>>>
>>>>>>>> Your whole model of computation is at significant variance from
>>>>>>>> the classical theoretical model.
>>>>>>>>
>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> Also, how does your decider determine if the branch it is
>>>>>>>>>> following is non-halting.
>>>>>>>>>
>>>>>>>>> The way any simulating halt decider would: through the
>>>>>>>>> detection of repeated state given the machine and its resources
>>>>>>>>> are finite in size.
>>>>>>>>
>>>>>>>> So only able to detect non-halting in machines goig into
>>>>>>>> repeating loops, and not just that the computation keeps growing
>>>>>>>> unbounded.
>>>>>>>
>>>>>>> Repeated state means a duplicate hash of the machine's finite state.
>>>>>>
>>>>>> But not suitable for things like the Twin Primes problem or
>>>>>> Collatz Conjecture.
>>>>>>
>>>>>> Most of the interesting problems don't end up in a simple infinite
>>>>>> loop, but a loop counting through numbers that will never reach
>>>>>> there terminal condition.
>>>>>>    >
>>>>>>>>
>>>>>>>> A very small set of the problems of normal interest in the theory.
>>>>>>>
>>>>>>> The size of the set is relative.  You are missing the point: to
>>>>>>> be computable the machine's resources can not be unbounded.  Only
>>>>>>> problems that are computable using the technology of the present
>>>>>>> era are of interest: one has to be a pragmatist.
>>>>>>>
>>>>>>> /Flibble
>>>>>>
>>>>>> For many of the problems, the "limited" memory of the modern
>>>>>> computer is unlikely to be the major limit. The "Very small set"
>>>>>> was the number of problems that can be handled, not the physical
>>>>>> size of the problems.
>>>>>>
>>>>>> Remember, the problems that Halting was designed for were things
>>>>>> that a person with paper and pencil were trying to solve.
>>>>>> Detecting "simple" loops wasn't the problem.
>>>>>
>>>>> I am not sure why you are equating repeated finite state with
>>>>> "simple" loops.
>>>>>
>>>>> /Flibble
>>>>
>>>> Because your "repeated state" method won't catch even fairly simple
>>>> issues like:
>>>>
>>>> for(i = 100; i != 1; i -= 2;) {
>>>> // do something but don't change i
>>>> }
>>>>
>>>> because the "state" never repeats
>>>
>>> Of course that state repeats (and will be caught): the integer "i" is
>>> of finite size so it will eventually wrap around to have the same bit
>>> pattern a second time.
>>>
>>> /Flibble
>>
>> Depends on its type. It could be a big int (infinite precision
>> integer), so it runs until the machine exhausts its memory.
>>
>> If you are admitting that you can only handle "finite" machines, then
>> that has been a solved problem for a long time. Even the pathological
>> program can be solved under finite memory limits (it will reach memory
>> exhaustion), which of course needs to be a fourth response possible
>> out of your decider.
>
> Agree. As I posted earlier one has to be pragmatic given the finite
> constraints: a halt decision may not be possible on Machine A but may be
> possible on Machine B which has twice the resources of Machine A, for
> example.
>
> /Flibble

On 23/04/2023 6:16 pm, Richard Damon wrote:
> On 4/23/23 1:06 PM, Mr Flibble wrote:
>> On 23/04/2023 5:44 pm, Richard Damon wrote:
>>> On 4/23/23 8:47 AM, Mr Flibble wrote:
>>>> On 23/04/2023 12:27 pm, Richard Damon wrote:
>>>>> On 4/22/23 11:47 PM, Mr Flibble wrote:
>>>>>> On 23/04/2023 3:42 am, Richard Damon wrote:
>>>>>>> On 4/22/23 9:55 PM, Mr Flibble wrote:
>>>>>>>> On 23/04/2023 1:39 am, Richard Damon wrote:
>>>>>>>>> On 4/22/23 8:31 PM, Mr Flibble wrote:
>>>>>>>>>> On 23/04/2023 12:53 am, Richard Damon wrote:
>>>>>>>>>>> On 4/22/23 7:43 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":
>>>>>>>>>>>>
>>>>>>>>>>>> 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.
>>>>>>>>>>>>
>>>>>>>>>>>> /Flibble
>>>>>>>>>>>
>>>>>>>>>>> So, see if you can show an actual use for your altered
>>>>>>>>>>> definition of Halt Decoding.
>>>>>>>>>>
>>>>>>>>>> It will decide that P() is pathological input and it will
>>>>>>>>>> decide that Px() is halting.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> But those are just toy programs (P was just a simple program to
>>>>>>>>> show classical halting to not be useful)
>>>>>>>>>
>>>>>>>>> What USEFUL resutls can be gotten with your decider. Based on
>>>>>>>>> the following answers, its hard to see one.
>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> You also need to clarify the rules of you computation system,
>>>>>>>>>>> as you have previously commented that it can't obey the
>>>>>>>>>>> "normal" rules used in computability theory.
>>>>>>>>>>
>>>>>>>>>> I believe you are referring to the fact that the halt decider
>>>>>>>>>> function and the intrinsic H(...) are a property of the
>>>>>>>>>> machine itself, H is much like the "move tape left" function
>>>>>>>>>> of a Turing Machine.  The only thing "abnormal" about it is
>>>>>>>>>> that such a function is not included in the traditional
>>>>>>>>>> definition of a Turing Machine.
>>>>>>>>>
>>>>>>>>> Your whole model of computation is at significant variance from
>>>>>>>>> the classical theoretical model.
>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> Also, how does your decider determine if the branch it is
>>>>>>>>>>> following is non-halting.
>>>>>>>>>>
>>>>>>>>>> The way any simulating halt decider would: through the
>>>>>>>>>> detection of repeated state given the machine and its
>>>>>>>>>> resources are finite in size.
>>>>>>>>>
>>>>>>>>> So only able to detect non-halting in machines goig into
>>>>>>>>> repeating loops, and not just that the computation keeps
>>>>>>>>> growing unbounded.
>>>>>>>>
>>>>>>>> Repeated state means a duplicate hash of the machine's finite
>>>>>>>> state.
>>>>>>>
>>>>>>> But not suitable for things like the Twin Primes problem or
>>>>>>> Collatz Conjecture.
>>>>>>>
>>>>>>> Most of the interesting problems don't end up in a simple
>>>>>>> infinite loop, but a loop counting through numbers that will
>>>>>>> never reach there terminal condition.
>>>>>>>    >
>>>>>>>>>
>>>>>>>>> A very small set of the problems of normal interest in the theory.
>>>>>>>>
>>>>>>>> The size of the set is relative.  You are missing the point: to
>>>>>>>> be computable the machine's resources can not be unbounded.
>>>>>>>> Only problems that are computable using the technology of the
>>>>>>>> present era are of interest: one has to be a pragmatist.
>>>>>>>>
>>>>>>>> /Flibble
>>>>>>>
>>>>>>> For many of the problems, the "limited" memory of the modern
>>>>>>> computer is unlikely to be the major limit. The "Very small set"
>>>>>>> was the number of problems that can be handled, not the physical
>>>>>>> size of the problems.
>>>>>>>
>>>>>>> Remember, the problems that Halting was designed for were things
>>>>>>> that a person with paper and pencil were trying to solve.
>>>>>>> Detecting "simple" loops wasn't the problem.
>>>>>>
>>>>>> I am not sure why you are equating repeated finite state with
>>>>>> "simple" loops.
>>>>>>
>>>>>> /Flibble
>>>>>
>>>>> Because your "repeated state" method won't catch even fairly simple
>>>>> issues like:
>>>>>
>>>>> for(i = 100; i != 1; i -= 2;) {
>>>>> // do something but don't change i
>>>>> }
>>>>>
>>>>> because the "state" never repeats
>>>>
>>>> Of course that state repeats (and will be caught): the integer "i"
>>>> is of finite size so it will eventually wrap around to have the same
>>>> bit pattern a second time.
>>>>
>>>> /Flibble
>>>
>>> Depends on its type. It could be a big int (infinite precision
>>> integer), so it runs until the machine exhausts its memory.
>>>
>>> If you are admitting that you can only handle "finite" machines, then
>>> that has been a solved problem for a long time. Even the pathological
>>> program can be solved under finite memory limits (it will reach
>>> memory exhaustion), which of course needs to be a fourth response
>>> possible out of your decider.
>>
>> Agree. As I posted earlier one has to be pragmatic given the finite
>> constraints: a halt decision may not be possible on Machine A but may
>> be possible on Machine B which has twice the resources of Machine A,
>> for example.
>>
>> /Flibble
>
> Yep, well known answer to the Halting Problem for fixed sized machines,
> is a machine with (slightly more than) twice the memory needed for the
> program to decide, and run two copies of it, one at half speed.
>
> You compare the memories of the machines, and if the algorithm gets in a
> loop of length N, somewhere in 2N cycles of the faster machine, the two
> machines will line up and you will detect the repeated state.

On 4/23/23 4:28 PM, Mr Flibble wrote:
> On 23/04/2023 6:16 pm, Richard Damon wrote:
>> On 4/23/23 1:06 PM, Mr Flibble wrote:
>>> On 23/04/2023 5:44 pm, Richard Damon wrote:
>>>> On 4/23/23 8:47 AM, Mr Flibble wrote:
>>>>> On 23/04/2023 12:27 pm, Richard Damon wrote:
>>>>>> On 4/22/23 11:47 PM, Mr Flibble wrote:
>>>>>>> On 23/04/2023 3:42 am, Richard Damon wrote:
>>>>>>>> On 4/22/23 9:55 PM, Mr Flibble wrote:
>>>>>>>>> On 23/04/2023 1:39 am, Richard Damon wrote:
>>>>>>>>>> On 4/22/23 8:31 PM, Mr Flibble wrote:
>>>>>>>>>>> On 23/04/2023 12:53 am, Richard Damon wrote:
>>>>>>>>>>>> On 4/22/23 7:43 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":
>>>>>>>>>>>>>
>>>>>>>>>>>>> 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.
>>>>>>>>>>>>>
>>>>>>>>>>>>> /Flibble
>>>>>>>>>>>>
>>>>>>>>>>>> So, see if you can show an actual use for your altered
>>>>>>>>>>>> definition of Halt Decoding.
>>>>>>>>>>>
>>>>>>>>>>> It will decide that P() is pathological input and it will
>>>>>>>>>>> decide that Px() is halting.
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> But those are just toy programs (P was just a simple program
>>>>>>>>>> to show classical halting to not be useful)
>>>>>>>>>>
>>>>>>>>>> What USEFUL resutls can be gotten with your decider. Based on
>>>>>>>>>> the following answers, its hard to see one.
>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> You also need to clarify the rules of you computation
>>>>>>>>>>>> system, as you have previously commented that it can't obey
>>>>>>>>>>>> the "normal" rules used in computability theory.
>>>>>>>>>>>
>>>>>>>>>>> I believe you are referring to the fact that the halt decider
>>>>>>>>>>> function and the intrinsic H(...) are a property of the
>>>>>>>>>>> machine itself, H is much like the "move tape left" function
>>>>>>>>>>> of a Turing Machine.  The only thing "abnormal" about it is
>>>>>>>>>>> that such a function is not included in the traditional
>>>>>>>>>>> definition of a Turing Machine.
>>>>>>>>>>
>>>>>>>>>> Your whole model of computation is at significant variance
>>>>>>>>>> from the classical theoretical model.
>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> Also, how does your decider determine if the branch it is
>>>>>>>>>>>> following is non-halting.
>>>>>>>>>>>
>>>>>>>>>>> The way any simulating halt decider would: through the
>>>>>>>>>>> detection of repeated state given the machine and its
>>>>>>>>>>> resources are finite in size.
>>>>>>>>>>
>>>>>>>>>> So only able to detect non-halting in machines goig into
>>>>>>>>>> repeating loops, and not just that the computation keeps
>>>>>>>>>> growing unbounded.
>>>>>>>>>
>>>>>>>>> Repeated state means a duplicate hash of the machine's finite
>>>>>>>>> state.
>>>>>>>>
>>>>>>>> But not suitable for things like the Twin Primes problem or
>>>>>>>> Collatz Conjecture.
>>>>>>>>
>>>>>>>> Most of the interesting problems don't end up in a simple
>>>>>>>> infinite loop, but a loop counting through numbers that will
>>>>>>>> never reach there terminal condition.
>>>>>>>>    >
>>>>>>>>>>
>>>>>>>>>> A very small set of the problems of normal interest in the
>>>>>>>>>> theory.
>>>>>>>>>
>>>>>>>>> The size of the set is relative.  You are missing the point: to
>>>>>>>>> be computable the machine's resources can not be unbounded.
>>>>>>>>> Only problems that are computable using the technology of the
>>>>>>>>> present era are of interest: one has to be a pragmatist.
>>>>>>>>>
>>>>>>>>> /Flibble
>>>>>>>>
>>>>>>>> For many of the problems, the "limited" memory of the modern
>>>>>>>> computer is unlikely to be the major limit. The "Very small set"
>>>>>>>> was the number of problems that can be handled, not the physical
>>>>>>>> size of the problems.
>>>>>>>>
>>>>>>>> Remember, the problems that Halting was designed for were things
>>>>>>>> that a person with paper and pencil were trying to solve.
>>>>>>>> Detecting "simple" loops wasn't the problem.
>>>>>>>
>>>>>>> I am not sure why you are equating repeated finite state with
>>>>>>> "simple" loops.
>>>>>>>
>>>>>>> /Flibble
>>>>>>
>>>>>> Because your "repeated state" method won't catch even fairly
>>>>>> simple issues like:
>>>>>>
>>>>>> for(i = 100; i != 1; i -= 2;) {
>>>>>> // do something but don't change i
>>>>>> }
>>>>>>
>>>>>> because the "state" never repeats
>>>>>
>>>>> Of course that state repeats (and will be caught): the integer "i"
>>>>> is of finite size so it will eventually wrap around to have the
>>>>> same bit pattern a second time.
>>>>>
>>>>> /Flibble
>>>>
>>>> Depends on its type. It could be a big int (infinite precision
>>>> integer), so it runs until the machine exhausts its memory.
>>>>
>>>> If you are admitting that you can only handle "finite" machines,
>>>> then that has been a solved problem for a long time. Even the
>>>> pathological program can be solved under finite memory limits (it
>>>> will reach memory exhaustion), which of course needs to be a fourth
>>>> response possible out of your decider.
>>>
>>> Agree. As I posted earlier one has to be pragmatic given the finite
>>> constraints: a halt decision may not be possible on Machine A but may
>>> be possible on Machine B which has twice the resources of Machine A,
>>> for example.
>>>
>>> /Flibble
>>
>> Yep, well known answer to the Halting Problem for fixed sized
>> machines, is a machine with (slightly more than) twice the memory
>> needed for the program to decide, and run two copies of it, one at
>> half speed.
>>
>> You compare the memories of the machines, and if the algorithm gets in
>> a loop of length N, somewhere in 2N cycles of the faster machine, the
>> two machines will line up and you will detect the repeated state.
>
> Yes, that sounds like a good solution and is what I would do if I was to
> actually implement the Flibble SSHD.
>
> /Flibble
>
>

On 23/04/2023 10:23 pm, Richard Damon wrote:
> On 4/23/23 4:28 PM, Mr Flibble wrote:
>> On 23/04/2023 6:16 pm, Richard Damon wrote:
>>> On 4/23/23 1:06 PM, Mr Flibble wrote:
>>>> On 23/04/2023 5:44 pm, Richard Damon wrote:
>>>>> On 4/23/23 8:47 AM, Mr Flibble wrote:
>>>>>> On 23/04/2023 12:27 pm, Richard Damon wrote:
>>>>>>> On 4/22/23 11:47 PM, Mr Flibble wrote:
>>>>>>>> On 23/04/2023 3:42 am, Richard Damon wrote:
>>>>>>>>> On 4/22/23 9:55 PM, Mr Flibble wrote:
>>>>>>>>>> On 23/04/2023 1:39 am, Richard Damon wrote:
>>>>>>>>>>> On 4/22/23 8:31 PM, Mr Flibble wrote:
>>>>>>>>>>>> On 23/04/2023 12:53 am, Richard Damon wrote:
>>>>>>>>>>>>> On 4/22/23 7:43 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":
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> 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.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> /Flibble
>>>>>>>>>>>>>
>>>>>>>>>>>>> So, see if you can show an actual use for your altered
>>>>>>>>>>>>> definition of Halt Decoding.
>>>>>>>>>>>>
>>>>>>>>>>>> It will decide that P() is pathological input and it will
>>>>>>>>>>>> decide that Px() is halting.
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> But those are just toy programs (P was just a simple program
>>>>>>>>>>> to show classical halting to not be useful)
>>>>>>>>>>>
>>>>>>>>>>> What USEFUL resutls can be gotten with your decider. Based on
>>>>>>>>>>> the following answers, its hard to see one.
>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> You also need to clarify the rules of you computation
>>>>>>>>>>>>> system, as you have previously commented that it can't obey
>>>>>>>>>>>>> the "normal" rules used in computability theory.
>>>>>>>>>>>>
>>>>>>>>>>>> I believe you are referring to the fact that the halt
>>>>>>>>>>>> decider function and the intrinsic H(...) are a property of
>>>>>>>>>>>> the machine itself, H is much like the "move tape left"
>>>>>>>>>>>> function of a Turing Machine.  The only thing "abnormal"
>>>>>>>>>>>> about it is that such a function is not included in the
>>>>>>>>>>>> traditional definition of a Turing Machine.
>>>>>>>>>>>
>>>>>>>>>>> Your whole model of computation is at significant variance
>>>>>>>>>>> from the classical theoretical model.
>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> Also, how does your decider determine if the branch it is
>>>>>>>>>>>>> following is non-halting.
>>>>>>>>>>>>
>>>>>>>>>>>> The way any simulating halt decider would: through the
>>>>>>>>>>>> detection of repeated state given the machine and its
>>>>>>>>>>>> resources are finite in size.
>>>>>>>>>>>
>>>>>>>>>>> So only able to detect non-halting in machines goig into
>>>>>>>>>>> repeating loops, and not just that the computation keeps
>>>>>>>>>>> growing unbounded.
>>>>>>>>>>
>>>>>>>>>> Repeated state means a duplicate hash of the machine's finite
>>>>>>>>>> state.
>>>>>>>>>
>>>>>>>>> But not suitable for things like the Twin Primes problem or
>>>>>>>>> Collatz Conjecture.
>>>>>>>>>
>>>>>>>>> Most of the interesting problems don't end up in a simple
>>>>>>>>> infinite loop, but a loop counting through numbers that will
>>>>>>>>> never reach there terminal condition.
>>>>>>>>>    >
>>>>>>>>>>>
>>>>>>>>>>> A very small set of the problems of normal interest in the
>>>>>>>>>>> theory.
>>>>>>>>>>
>>>>>>>>>> The size of the set is relative.  You are missing the point:
>>>>>>>>>> to be computable the machine's resources can not be unbounded.
>>>>>>>>>> Only problems that are computable using the technology of the
>>>>>>>>>> present era are of interest: one has to be a pragmatist.
>>>>>>>>>>
>>>>>>>>>> /Flibble
>>>>>>>>>
>>>>>>>>> For many of the problems, the "limited" memory of the modern
>>>>>>>>> computer is unlikely to be the major limit. The "Very small
>>>>>>>>> set" was the number of problems that can be handled, not the
>>>>>>>>> physical size of the problems.
>>>>>>>>>
>>>>>>>>> Remember, the problems that Halting was designed for were
>>>>>>>>> things that a person with paper and pencil were trying to
>>>>>>>>> solve. Detecting "simple" loops wasn't the problem.
>>>>>>>>
>>>>>>>> I am not sure why you are equating repeated finite state with
>>>>>>>> "simple" loops.
>>>>>>>>
>>>>>>>> /Flibble
>>>>>>>
>>>>>>> Because your "repeated state" method won't catch even fairly
>>>>>>> simple issues like:
>>>>>>>
>>>>>>> for(i = 100; i != 1; i -= 2;) {
>>>>>>> // do something but don't change i
>>>>>>> }
>>>>>>>
>>>>>>> because the "state" never repeats
>>>>>>
>>>>>> Of course that state repeats (and will be caught): the integer "i"
>>>>>> is of finite size so it will eventually wrap around to have the
>>>>>> same bit pattern a second time.
>>>>>>
>>>>>> /Flibble
>>>>>
>>>>> Depends on its type. It could be a big int (infinite precision
>>>>> integer), so it runs until the machine exhausts its memory.
>>>>>
>>>>> If you are admitting that you can only handle "finite" machines,
>>>>> then that has been a solved problem for a long time. Even the
>>>>> pathological program can be solved under finite memory limits (it
>>>>> will reach memory exhaustion), which of course needs to be a fourth
>>>>> response possible out of your decider.
>>>>
>>>> Agree. As I posted earlier one has to be pragmatic given the finite
>>>> constraints: a halt decision may not be possible on Machine A but
>>>> may be possible on Machine B which has twice the resources of
>>>> Machine A, for example.
>>>>
>>>> /Flibble
>>>
>>> Yep, well known answer to the Halting Problem for fixed sized
>>> machines, is a machine with (slightly more than) twice the memory
>>> needed for the program to decide, and run two copies of it, one at
>>> half speed.
>>>
>>> You compare the memories of the machines, and if the algorithm gets
>>> in a loop of length N, somewhere in 2N cycles of the faster machine,
>>> the two machines will line up and you will detect the repeated state.
>>
>> Yes, that sounds like a good solution and is what I would do if I was
>> to actually implement the Flibble SSHD.
>>
>> /Flibble
>>
>>
>
> But that never generates your NaP exception, and never needs to, so the
> Flibble SSHD is shown to not be needed at all.
>
> The problem space being solved by it was already solved.
>
> Once you limit yourself to memory limited machines, the Halt Decider
> just needs to make sure that the "pathological" programs die of
> out-of-memory errors.

On 4/23/2023 5:26 PM, Mr Flibble wrote:
> On 23/04/2023 10:23 pm, Richard Damon wrote:
>> On 4/23/23 4:28 PM, Mr Flibble wrote:
>>> On 23/04/2023 6:16 pm, Richard Damon wrote:
>>>> On 4/23/23 1:06 PM, Mr Flibble wrote:
>>>>> On 23/04/2023 5:44 pm, Richard Damon wrote:
>>>>>> On 4/23/23 8:47 AM, Mr Flibble wrote:
>>>>>>> On 23/04/2023 12:27 pm, Richard Damon wrote:
>>>>>>>> On 4/22/23 11:47 PM, Mr Flibble wrote:
>>>>>>>>> On 23/04/2023 3:42 am, Richard Damon wrote:
>>>>>>>>>> On 4/22/23 9:55 PM, Mr Flibble wrote:
>>>>>>>>>>> On 23/04/2023 1:39 am, Richard Damon wrote:
>>>>>>>>>>>> On 4/22/23 8:31 PM, Mr Flibble wrote:
>>>>>>>>>>>>> On 23/04/2023 12:53 am, Richard Damon wrote:
>>>>>>>>>>>>>> On 4/22/23 7:43 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":
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> 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.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> /Flibble
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> So, see if you can show an actual use for your altered
>>>>>>>>>>>>>> definition of Halt Decoding.
>>>>>>>>>>>>>
>>>>>>>>>>>>> It will decide that P() is pathological input and it will
>>>>>>>>>>>>> decide that Px() is halting.
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> But those are just toy programs (P was just a simple program
>>>>>>>>>>>> to show classical halting to not be useful)
>>>>>>>>>>>>
>>>>>>>>>>>> What USEFUL resutls can be gotten with your decider. Based
>>>>>>>>>>>> on the following answers, its hard to see one.
>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> You also need to clarify the rules of you computation
>>>>>>>>>>>>>> system, as you have previously commented that it can't
>>>>>>>>>>>>>> obey the "normal" rules used in computability theory.
>>>>>>>>>>>>>
>>>>>>>>>>>>> I believe you are referring to the fact that the halt
>>>>>>>>>>>>> decider function and the intrinsic H(...) are a property of
>>>>>>>>>>>>> the machine itself, H is much like the "move tape left"
>>>>>>>>>>>>> function of a Turing Machine.  The only thing "abnormal"
>>>>>>>>>>>>> about it is that such a function is not included in the
>>>>>>>>>>>>> traditional definition of a Turing Machine.
>>>>>>>>>>>>
>>>>>>>>>>>> Your whole model of computation is at significant variance
>>>>>>>>>>>> from the classical theoretical model.
>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Also, how does your decider determine if the branch it is
>>>>>>>>>>>>>> following is non-halting.
>>>>>>>>>>>>>
>>>>>>>>>>>>> The way any simulating halt decider would: through the
>>>>>>>>>>>>> detection of repeated state given the machine and its
>>>>>>>>>>>>> resources are finite in size.
>>>>>>>>>>>>
>>>>>>>>>>>> So only able to detect non-halting in machines goig into
>>>>>>>>>>>> repeating loops, and not just that the computation keeps
>>>>>>>>>>>> growing unbounded.
>>>>>>>>>>>
>>>>>>>>>>> Repeated state means a duplicate hash of the machine's finite
>>>>>>>>>>> state.
>>>>>>>>>>
>>>>>>>>>> But not suitable for things like the Twin Primes problem or
>>>>>>>>>> Collatz Conjecture.
>>>>>>>>>>
>>>>>>>>>> Most of the interesting problems don't end up in a simple
>>>>>>>>>> infinite loop, but a loop counting through numbers that will
>>>>>>>>>> never reach there terminal condition.
>>>>>>>>>>    >
>>>>>>>>>>>>
>>>>>>>>>>>> A very small set of the problems of normal interest in the
>>>>>>>>>>>> theory.
>>>>>>>>>>>
>>>>>>>>>>> The size of the set is relative.  You are missing the point:
>>>>>>>>>>> to be computable the machine's resources can not be
>>>>>>>>>>> unbounded. Only problems that are computable using the
>>>>>>>>>>> technology of the present era are of interest: one has to be
>>>>>>>>>>> a pragmatist.
>>>>>>>>>>>
>>>>>>>>>>> /Flibble
>>>>>>>>>>
>>>>>>>>>> For many of the problems, the "limited" memory of the modern
>>>>>>>>>> computer is unlikely to be the major limit. The "Very small
>>>>>>>>>> set" was the number of problems that can be handled, not the
>>>>>>>>>> physical size of the problems.
>>>>>>>>>>
>>>>>>>>>> Remember, the problems that Halting was designed for were
>>>>>>>>>> things that a person with paper and pencil were trying to
>>>>>>>>>> solve. Detecting "simple" loops wasn't the problem.
>>>>>>>>>
>>>>>>>>> I am not sure why you are equating repeated finite state with
>>>>>>>>> "simple" loops.
>>>>>>>>>
>>>>>>>>> /Flibble
>>>>>>>>
>>>>>>>> Because your "repeated state" method won't catch even fairly
>>>>>>>> simple issues like:
>>>>>>>>
>>>>>>>> for(i = 100; i != 1; i -= 2;) {
>>>>>>>> // do something but don't change i
>>>>>>>> }
>>>>>>>>
>>>>>>>> because the "state" never repeats
>>>>>>>
>>>>>>> Of course that state repeats (and will be caught): the integer
>>>>>>> "i" is of finite size so it will eventually wrap around to have
>>>>>>> the same bit pattern a second time.
>>>>>>>
>>>>>>> /Flibble
>>>>>>
>>>>>> Depends on its type. It could be a big int (infinite precision
>>>>>> integer), so it runs until the machine exhausts its memory.
>>>>>>
>>>>>> If you are admitting that you can only handle "finite" machines,
>>>>>> then that has been a solved problem for a long time. Even the
>>>>>> pathological program can be solved under finite memory limits (it
>>>>>> will reach memory exhaustion), which of course needs to be a
>>>>>> fourth response possible out of your decider.
>>>>>
>>>>> Agree. As I posted earlier one has to be pragmatic given the finite
>>>>> constraints: a halt decision may not be possible on Machine A but
>>>>> may be possible on Machine B which has twice the resources of
>>>>> Machine A, for example.
>>>>>
>>>>> /Flibble
>>>>
>>>> Yep, well known answer to the Halting Problem for fixed sized
>>>> machines, is a machine with (slightly more than) twice the memory
>>>> needed for the program to decide, and run two copies of it, one at
>>>> half speed.
>>>>
>>>> You compare the memories of the machines, and if the algorithm gets
>>>> in a loop of length N, somewhere in 2N cycles of the faster machine,
>>>> the two machines will line up and you will detect the repeated state.
>>>
>>> Yes, that sounds like a good solution and is what I would do if I was
>>> to actually implement the Flibble SSHD.
>>>
>>> /Flibble
>>>
>>>
>>
>> But that never generates your NaP exception, and never needs to, so
>> the Flibble SSHD is shown to not be needed at all.
>>
>> The problem space being solved by it was already solved.
>>
>> Once you limit yourself to memory limited machines, the Halt Decider
>> just needs to make sure that the "pathological" programs die of
>> out-of-memory errors.
>
> No, the pathological program of [Strachey 1965] still needs to be
> explicitly detected as it won't die of an out-of-memory error: the so
> called "infinite recursion" of Olcott's decider is a mistake.
>
> /Flibble