X86 based simulating halt decider H correctly decides halt status of pathological input P(P)

0 views
Skip to first unread message

olcott

unread,
Jul 17, 2021, 2:36:25 PMJul 17
to
// Strachey(1965) "An impossible program"
// CPL translated to C
// https://doi.org/10.1093/comjnl/7.4.313
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}

int main()
{
Output("Input_Halts = ", P((u32)P);
}

*Conventional Halt Deciding Axiom*
When the pure simulation of the machine description ⟨P⟩ of a machine P
on its input I never halts we know that P(I) never halts. // based on
UTM(⟨P⟩,I) ≡ P(I)

*Stipulated Definition of Halting*
An input to a halt decider is defined to halt if and only if this input
stops running while simulating halt decider H remains a pure simulator
of this input.

*Pathological Input* to a halt decider is defined as any input that was
defined to do the opposite of whatever its corresponding halt decider
decides.

It seems to me that the Stipulated Definition of Halting does not add
anything but clarity to the Conventional Halt Deciding Axiom. Others may
see this differently.

None-the-less the Stipulated Definition of Halting does provide the
means to correctly decide the halting status of Pathological Inputs.

int main() { P(P); } is defined to be a non-halting computation under
the stipulated definition.

The stipulated definition of halting defines the exact same set as the
conventional definition of halting with the possible exception that
pathological inputs are decided as non-halting inputs.

Because the stipulated definition of halting is merely a paraphrase of
the Conventional Halt Deciding Axiom I propose that this stipulated
definition of halting merely provides clarity and does not change the
conventional definition of halting at all.


https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation

--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein

olcott

unread,
Jul 17, 2021, 3:40:43 PMJul 17
to
On 7/17/2021 1:36 PM, olcott wrote:
> // Strachey(1965) "An impossible program"
> // CPL translated to C
> // https://doi.org/10.1093/comjnl/7.4.313
> void P(u32 x)
> {
>   if (H(x, x))
>     HERE: goto HERE;
> }
>
> int main()
> {
>   Output("Input_Halts = ", P((u32)P);
> }
>
> *Conventional Halt Deciding Axiom*
> When the pure simulation of the machine description ⟨P⟩ of a machine P
> on its input I never halts we know that P(I) never halts. // based on
> UTM(⟨P⟩,I) ≡ P(I)
>
> *Stipulated Definition of Halting*
> An input to a halt decider is defined to halt if and only if this input
> stops running while simulating halt decider H remains a pure simulator
> of this input.
>

A stipulative definition is a type of definition in which a new or
currently existing term is given a new specific meaning for the purposes
of argument or discussion in a given context.
https://en.wikipedia.org/wiki/Stipulative_definition

If it is stipulated that cats are all animals having DNA that exactly
matches cat DNA, then when a cat barks or gives birth to genetic puppies
it remains a cat by stipulative definition.
Reply all
Reply to author
Forward
0 new messages