The x86utm operating system shows how the halting problem can be made decidable

[olcott]

x86utm was created to be a master UTM that can execute subordinate UTMs
or TMs in DebugStep() mode. Here are some of its key operating system
functions:

u32* Allocate(u32 size);
void SaveState(Registers* state);
void LoadState(Registers* state);
u32 DebugStep(Registers* master_state, Registers* slave_state);
void PushBack(u32* S, u32 M); // similar to c++

The following code is based on the Linz H and Ĥ Turing Machine
templates: http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf


void H_Hat(u32 M)
{
if (Aborted_Because_Non_Halting_Behavior_Detected(M, M))
MOV_EAX_0 // Execution of M(N) has been aborted
else
{
MOV_EAX_1 // M(N) has halted
HERE: goto HERE;
}
HALT
}


void H(u32 M, u32 N)
{
if (Aborted_Because_Non_Halting_Behavior_Detected(M, N))
MOV_EAX_0 // Execution of M(N) has been aborted
else
MOV_EAX_1 // M(N) has halted
HALT
}


int main()
{
u32 M = (u32)H_Hat;
H(M, M);
HALT;
}

The simplest possible way to define a halt decider is to have a UTM
execute its program under test (PUT) until it detects non-halting
behavior of its (PUT) or its (PUT) terminates on its own.

When the UTM halt decider decides that its (PUT) would not otherwise
halt it stops executing its (PUT) and reports that non halting behavior
has been detected. If it does not detect non-halting behavior then it
reports that its input program has terminated.

This is exactly the same thing as the conventional NON_HALTING / HALTING
return values of a conventional halt decider except that this definition
of a halt decider cannot be fooled by any cheap trick.

Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) == true
means that the input has infinite execution.

Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) == false
means that the input DOES NOT HAVE infinite execution.

There are no programs left over that can be shown to be undecidable.

ALL INPUT IS DIVIDED INTO EXACTLY ONE OF THESE TWO SETS
(a) The input Program/TM has infinite execution.
(b) The input Program/TM DOES NOT HAVE infinite execution.








--
Copyright 2020 Pete Olcott

[Mike Terry]

What happens if it detects no "non-halting behaviour" (loops or infinite
recursion, or whatever) but its PUT does not terminate either?

>
> When the UTM halt decider decides that its (PUT) would not otherwise
> halt it stops executing its (PUT) and reports that non halting behavior
> has been detected. If it does not detect non-halting behavior then it
> reports that its input program has terminated.
>
> This is exactly the same thing as the conventional NON_HALTING / HALTING
> return values of a conventional halt decider except that this definition
> of a halt decider cannot be fooled by any cheap trick.

..and yet YOUR code is "fooled" into saying it has detected non-halting
behaviour for a calculation you agree actually halts.

All covered in your previous thread. No point in repeating arguments here.

Mike.

[olcott]

First of all this is more aptly stated as fails to detect non-halting
behavior. Yes any halt decide that is not infallibly all knowing will
certainly miss some cases.

Remember that the scope is not to solve the halting problem with a halt
decider that is omniscient (all knowing).

The scope is to show the conventional proofs do not prove that the
halting problem is undecidable.

>> When the UTM halt decider decides that its (PUT) would not otherwise
>> halt it stops executing its (PUT) and reports that non halting behavior
>> has been detected. If it does not detect non-halting behavior then it
>> reports that its input program has terminated.
>>
>> This is exactly the same thing as the conventional NON_HALTING / HALTING
>> return values of a conventional halt decider except that this definition
>> of a halt decider cannot be fooled by any cheap trick.
>
> ..and yet YOUR code is "fooled" into saying it has detected non-halting
> behaviour for a calculation you agree actually halts.

H_Hat(H_Hat) never ever halts unless and until it is aborted at some
level of inner to outer invocation.

Ignoring what I say does not count as any form or rebuttal what-so-ever.

> All covered in your previous thread.  No point in repeating arguments here.
>
> Mike.
>
>>
>> Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) == true
>> means that the input has infinite execution.
>>
>> Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) == false
>> means that the input DOES NOT HAVE infinite execution.
>>
>> There are no programs left over that can be shown to be undecidable.
>>
>> ALL INPUT IS DIVIDED INTO EXACTLY ONE OF THESE TWO SETS
>> (a) The input Program/TM has infinite execution.
>> (b) The input Program/TM DOES NOT HAVE infinite execution.
>>
>

[Elijah Stone]

> What happens if it detects no "non-halting behaviour" (loops or infinite
> recursion, or whatever) but its PUT does not terminate either?

On real hardware with a finite amount of memory, there are a finite number
of total states. So at some point either

1) An explicit halt will occur

2) A state will be repeated

The halting problem is decidable on a machine with finite memory within
1+2^n cycles (where n is the number of bits of memory), because the number
of states inducible by the program will necessarily be exhausted by 2^n
cycles.

(Granted, on modern hardware, n is so large as to render 2^n effectively infinite.)

-E

[olcott]

On 10/25/2020 8:29 AM, Alan Mackenzie wrote:
> In comp.theory olcott <No...@nowhere.com> wrote:
>
> [ .... ]

>
>> The simplest possible way to define a halt decider is to have a UTM
>> execute its program under test (PUT) until it detects non-halting
>> behavior of its (PUT) or its (PUT) terminates on its own.
>

> This doesn't work for PUTs which neither terminate nor exhibit
> "non-halting behavior", whatever that might mean.

My fully elaborated halt decider will detect many kinds of infinite
loops and many kinds of infinite recursion, thus two kinds of
non-halting behavior.

>> When the UTM halt decider decides that its (PUT) would not otherwise
>> halt it stops executing its (PUT) and reports that non halting behavior
>> has been detected. If it does not detect non-halting behavior then it
>> reports that its input program has terminated.
>
>> This is exactly the same thing as the conventional NON_HALTING / HALTING
>> return values of a conventional halt decider except that this definition
>> of a halt decider cannot be fooled by any cheap trick.
>

> There is no essential difference between a random halt decider (which
> cannot exist) and your A_B_N_H_B_D (which _might_ exist, but won't work).
> Halt deciders do not exist and cannot exist.

Your dogma is contradicted by my code. I wish people would do more than
form what superficially appears to be a rebuttal to the very gullible.

> If you really believe otherwise, then why don't you stop dicking around
> on Usenet, and finish writing your software. Then you will (or won't)
> have something to show. Please let us know what the current anticipated
> release date is. And then leave all these newsgroups in peace until the
> anticipated release becomes an actual release.

Since you already disagreed with my current proof without pointing out
any error you would likely simply disagree with fully operational code.

Any disagreement that does not point out any actual error or what is
mistakenly believed to be an error is mere vacuous rhetoric.

>
> [ .... ]

[olcott]

It looks like a 8 GB machine that runs at 2 Ghz takes a minimum of 34
seconds to repeat a prior state. This is only if the code was
intentionally designed to as quickly as possible get into every one of
its possible states.

[Mike Terry]

More specifically, your scope is to exhibit an H, H^ pair, such that
H(H^,H^) makes the correct decision for whether H^ (actually) halts.
(Not whether H(H^,H^) /would/ halt if something else did or didn't
happen, whatever that means. Actually, I've had an insight into what
you might mean by that, but I'll probably post that in a new thread...)

So, lets stick to your specific (yet to be fully delivered) H, H_Hat
pair, and I'll ask the same question:

What happens if H fails to detect non-halting behavior for its
corresponding H^(H^) calculation, and also that calculation does not
terminate?

I suggest the answer is that H itself will never terminate, and so fail
in its role of halt decider in this crucial case. (But maybe you
believe this scenario is impossible.)

>>> When the UTM halt decider decides that its (PUT) would not otherwise
>>> halt it stops executing its (PUT) and reports that non halting behavior
>>> has been detected. If it does not detect non-halting behavior then it
>>> reports that its input program has terminated.
>>>
>>> This is exactly the same thing as the conventional NON_HALTING / HALTING
>>> return values of a conventional halt decider except that this definition
>>> of a halt decider cannot be fooled by any cheap trick.
>>
>> ..and yet YOUR code is "fooled" into saying it has detected
>> non-halting behaviour for a calculation you agree actually halts.
>
> H_Hat(H_Hat) never ever halts unless and until it is aborted at some
> level of inner to outer invocation.

"aborted at some level of inner to outer invocation"? How do you come
up with such phrases? (More importantly, what does it mean exactly?)

What I think you mean is that H_Hat(H_Hat) halts precisely when its call
to Aborted_Because_Non_Halting_Behavior_Detected() returns YES, and this
in turn happens precisely when tha call has decided it's found
"non-halting behaviour" in the program it was emulating (and so decided
to cease emulating and return).

[Paavo Helde]

25.10.2020 16:40 olcott kirjutas:
>
> It looks like a 8 GB machine that runs at 2 Ghz takes a minimum of 34
> seconds to repeat a prior state. This is only if the code was
> intentionally designed to as quickly as possible get into every one of
> its possible states.

Whoa, an error of ca 10^2,000,000,000 times! This must be a new record,
so far I have only seen newspaper articles getting numbers 1 billion
times wrong, which is only meager 10^9.

[Mr Flibble]

On 25/10/2020 14:21, olcott wrote:
> On 10/25/2020 8:29 AM, Alan Mackenzie wrote:
>> In comp.theory olcott <No...@nowhere.com> wrote:
>>
>> [ .... ]
>>
>>> The simplest possible way to define a halt decider is to have a UTM
>>> execute its program under test (PUT) until it detects non-halting
>>> behavior of its (PUT) or its (PUT) terminates on its own.
>>
>> This doesn't work for PUTs which neither terminate nor exhibit
>> "non-halting behavior", whatever that might mean.
>
> My fully elaborated halt decider will detect many kinds of infinite loops and many kinds of infinite recursion, thus two kinds of non-halting behavior.

"Many kinds"? "Many" isn't good enough, mate. Unless it can detect ALL kinds of non-halting behaviour for ALL arbitrary UTMs then you haven't refuted Turing's proof, dear.

/Flibble

--
¬

[olcott]

H is (and I will repeat for the fifth time) not all knowing.

> I suggest the answer is that H itself will never terminate, and so fail
> in its role of halt decider in this crucial case.

Your assertion is merely that it is possible for programs that are not
all knowing to have bugs. You did not notice that by making this
assertion that you simply dodged the whole point.

The task at hand is not to speculate that a implementation of a halt
decider that is not all knowing may get some answers incorrectly only
because it is not all knowing.

The task at hand is to provide a a specific input to this function that
can be shown to be impossible to decide correctly:
Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)

When I am correct and people realize that I am correct and still want to
form a rebuttal they use all kinds of underhanded deceptive tactics to
try to win the argument.

With persuasive enough rhetoric they sneak in ad hominem attacks
disguised as personal insults they succeed in convincing the very
gullible that I am probably incorrect.

I am not saying that you are using these dishonest tactics. I am merely
trying to get you to directly focus on the key point at hand.

The task at hand is to provide a a specific input to this function that
can be shown to be impossible to decide correctly:
Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)

> (But maybe you
> believe this scenario is impossible.)
>
>>>> When the UTM halt decider decides that its (PUT) would not otherwise
>>>> halt it stops executing its (PUT) and reports that non halting behavior
>>>> has been detected. If it does not detect non-halting behavior then it
>>>> reports that its input program has terminated.
>>>>
>>>> This is exactly the same thing as the conventional NON_HALTING /
>>>> HALTING
>>>> return values of a conventional halt decider except that this
>>>> definition
>>>> of a halt decider cannot be fooled by any cheap trick.
>>>
>>> ..and yet YOUR code is "fooled" into saying it has detected
>>> non-halting behaviour for a calculation you agree actually halts.
>>
>> H_Hat(H_Hat) never ever halts unless and until it is aborted at some
>> level of inner to outer invocation.
>
> "aborted at some level of inner to outer invocation"?  How do you come
> up with such phrases?  (More importantly, what does it mean exactly?)

Maybe this is incomprehensible without actually seeing the working code.
I can understand it only because I focused on this key detail for
hundreds of hours and have a fully operational operating system that
implements the details of this.

> What I think you mean is that H_Hat(H_Hat) halts precisely when its call
> to Aborted_Because_Non_Halting_Behavior_Detected() returns YES, and this
> in turn happens precisely when tha call has decided it's found
> "non-halting behaviour" in the program it was emulating (and so decided
> to cease emulating and return).

Yes. H_Hat() is naturally infinitely recursive.
https://groups.google.com/g/comp.theory/c/NcFS02hKs1U/m/PlBF-1LRBAAJ

This same thing applies to all of the conventional self-referential
halting problem proof counter-examples.

>>
>> Ignoring what I say does not count as any form or rebuttal what-so-ever.
>>
>>> All covered in your previous thread.  No point in repeating arguments
>>> here.
>>>
>>> Mike.
>>>
>>>>
>>>> Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) == true
>>>> means that the input has infinite execution.
>>>>
>>>> Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) == false
>>>> means that the input DOES NOT HAVE infinite execution.
>>>>
>>>> There are no programs left over that can be shown to be undecidable.
>>>>
>>>> ALL INPUT IS DIVIDED INTO EXACTLY ONE OF THESE TWO SETS
>>>> (a) The input Program/TM has infinite execution.
>>>> (b) The input Program/TM DOES NOT HAVE infinite execution.
>>>>
>>>
>>
>>

[olcott]

8 GB is 68,719,476,736 bits
2 Ghz is 2,147,483,648 operations per second

68,719,476,736 bits / 2,147,483,648 OPS = 32 seconds.

[olcott]

On 10/25/2020 9:55 AM, Alan Mackenzie wrote:
> In comp.theory olcott <No...@nowhere.com> wrote:
>> On 10/25/2020 8:29 AM, Alan Mackenzie wrote:
>>> In comp.theory olcott <No...@nowhere.com> wrote:
>
>>> [ .... ]
>
>>>> The simplest possible way to define a halt decider is to have a UTM
>>>> execute its program under test (PUT) until it detects non-halting
>>>> behavior of its (PUT) or its (PUT) terminates on its own.
>
>>> This doesn't work for PUTs which neither terminate nor exhibit
>>> "non-halting behavior", whatever that might mean.
>
>> My fully elaborated halt decider will detect many kinds of infinite
>> loops and many kinds of infinite recursion, thus two kinds of
>> non-halting behavior.
>

> So you admit your halt decider will only detect some forms of
> "non-halting behaviour" and will fail with an arbitrary input program.
> This is consistent with the theorem saying a halting decider isn't
> possible.

>

The task at hand is not to speculate that a implementation of a halt
decider that is not all knowing may get some answers incorrectly only
because it is not all knowing.

The task at hand is to provide a specific input to this function that

can be shown to be impossible to decide correctly:
Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)

>>>> When the UTM halt decider decides that its (PUT) would not otherwise
>>>> halt it stops executing its (PUT) and reports that non halting behavior
>>>> has been detected. If it does not detect non-halting behavior then it
>>>> reports that its input program has terminated.
>
>>>> This is exactly the same thing as the conventional NON_HALTING / HALTING
>>>> return values of a conventional halt decider except that this definition
>>>> of a halt decider cannot be fooled by any cheap trick.
>
>>> There is no essential difference between a random halt decider (which
>>> cannot exist) and your A_B_N_H_B_D (which _might_ exist, but won't work).
>>> Halt deciders do not exist and cannot exist.
>
>> Your dogma is contradicted by my code. I wish people would do more than
>> form what superficially appears to be a rebuttal to the very gullible.
>

> It isn't dogma. It's a proven mathematical theorem. There's nothing
> superficial about it. And, as yet, I've seen no evidence you have any
> code whatsoever. But, for the record, I believe you have something
> resembling what you claim in the opening post of this thread.

The task at hand is to provide a specific input to this function that

can be shown to be impossible to decide correctly:
Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)

>>> If you really believe otherwise, then why don't you stop dicking around
>>> on Usenet, and finish writing your software. Then you will (or won't)
>>> have something to show. Please let us know what the current anticipated
>>> release date is. And then leave all these newsgroups in peace until the
>>> anticipated release becomes an actual release.
>
>> Since you already disagreed with my current proof without pointing out
>> any error you would likely simply disagree with fully operational code.
>

> I have pointed out the error, namely that it contravenes a theorem. And
> what you have is not a "proof". Abusing the word "proof" is a strong
> sign of a crank. What more is necessary? Others have pointed out
> detailed flaws, but you won't accept these.

The task at hand is to provide a specific input to this function that

can be shown to be impossible to decide correctly:
Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)

> And no, I wouldn't disagree with fully operational code. But I know such
> is not possible. If you want to prove me wrong, produce this code.

If that was true then you could meet this challenge:

The task at hand is to provide a specific input to this function that

can be shown to be impossible to decide correctly:
Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)

>> Any disagreement that does not point out any actual error or what is
>> mistakenly believed to be an error is mere vacuous rhetoric.
>

> No. Enough people have pointed out errors for it to be unnecessary for
> me to waste time on it. And the burden of proof is on your side, not
> ours.

The task at hand is to provide a specific input to this function that

can be shown to be impossible to decide correctly:
Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)

> You didn't answer the question: when's your software going to be ready?

Quite soon. I got totally burned out working all-the-time for months and
months. I may reduce the time spent on it to as little as 40 hours per
week. I am still aiming for the 2020-12-13 7:00 PM deadline of my two
year anniversary of refuting the conclusion the conventional

self-referential halting problem proof counter-examples.

>

[olcott]

The task at hand is not to speculate that a implementation of a halt
decider that is not all knowing may get some answers incorrectly only
because it is not all knowing.

This would be required ONLY if my claim is that I have solved the
halting problem.

What I have already done is refute all of the conventional

self-referential halting problem proof counter-examples.

Any correct rebuttal of this must meet this burden of proof:

Provide a specific input to this function that can be shown to be

impossible to decide correctly:
Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)

[olcott]

On 10/25/2020 12:02 PM, Richard Damon wrote:

> On 10/25/20 12:12 PM, olcott wrote:
>
>>
>> The task at hand is not to speculate that a implementation of a halt
>> decider that is not all knowing may get some answers incorrectly only
>> because it is not all knowing.
>>
>> This would be required ONLY if my claim is that I have solved the
>> halting problem.
>>
>> What I have already done is refute all of the conventional
>> self-referential halting problem proof counter-examples.
>> Any correct rebuttal of this must meet this burden of proof:
>>
>> Provide a specific input to this function that can be shown to be
>> impossible to decide correctly:
>> Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)
>>
>>

> If 'Aborted' has no limitations on it, than this halt decider is
> worthless, as it could just up and decide that it needs to abort ALL
> machines, and if the only test was did it abort it, it would be right.

You just really are not paying any attention at all are you?

The simplest possible way to define a halt decider is to have the halt
decider directly execute its input exactly one execution step / state
transition at a time.

If we define the halt decider in this simplest possible way then it must
stop executing its input as soon as it determines that its input would
not otherwise ever halt.

> If 'Aborted' is to mean only machines that require infinite resources to
> run then either it is wrong on H_Hat, or it isn't itself a valid
> decider, as a decider must be a finite calculation.
>
> If we can quantify what cases it is allowed to abort even though we
> aren't sure that the resultant machine than it becomes just a partial
> halt decider, which might be interesting if it can handle the really
> interesting cases, but I don't think it can, is it seems that it
> fundamentally can only detect looping that comes from a finite amount of
> state.
>
> While you don't need to actually come up with the decider, if you can't
> come up with a definition of it that shows that it could be a useful
> thing for real problems, it isn't really a useful result.
>
> Showing that a proof that disproves a specific conjecture doesn't
> disprove a DIFFERENT conjecture, doesn't really effect the status of
> first conjecture.
>
> The Halt Decider in Linz theorem has very useful properties, and if such
> a thing could exist, it would have a great impact on the theory of
> Mathematics, perhaps even if it could just be proved to exist without
> actually having it.
>
> Proving the inability to create such a decider also establishes certain
> limits to what can be proved in Mathematics.
>
> If you could actually establish that your 'Need to Abort Detector' could
> actually provide useful information close to what that classical Halt
> Detector would have been able to provide, it might be able to be
> something important, but from everything I see from your descriptions,
> it doesn't, but just handles the cases with well know solutions.

[Elijah Stone]

On Sun, 25 Oct 2020, olcott wrote:
> It looks like a 8 GB machine that runs at 2 Ghz takes a minimum of 34
> seconds to repeat a prior state. This is only if the code was
> intentionally designed to as quickly as possible get into every one of
> its possible states.

. . . what?

It takes a minimum of 0.5ns--a single instruction--'jmp $' or similar.

The maximum is:

8gb = (8*1024^3) bits
= 2^33

Total states = 2^(2^33)

At 2GHz, we can exhaust 2e9 states per second, but let's be generous and
make it 2^31, as the math is simpler that way. That makes it:

2^(2^33)
---------
2^31


= 2^(2^33 - 31)
= 2^8589934561 seconds.

Which is rather mind-bogglingly large.

[olcott]

On 10/25/2020 3:41 PM, Richard Damon wrote:

> On 10/25/20 4:15 PM, olcott wrote:
>>
>> You just really are not paying any attention at all are you?
>>
>> The simplest possible way to define a halt decider is to have the halt
>> decider directly execute its input exactly one execution step / state
>> transition at a time.
>>
>> If we define the halt decider in this simplest possible way then it must
>> stop executing its input as soon as it determines that its input would
>> not otherwise ever halt.
>

> If may be the simplest, but it also is the way that adds no useful
> information in most interesting problems.
>
> Yes, it detects non-halting in the case of the machine maintaining a
> bounded size in its non-halting state, but the interesting machines tend
> to have at least one value counting up through the natural numbers, and
> thus NEVER get into the repeated state case.
>
> This says that this basic method can always return halted, if the
> machine does halt.
>
> Return Non-Halting if the machine get stuck in a finite-bounded loop
>
> But won't return anything if the machine get into an unbounded loop, as
> it never repeats the same state, and thus it doesn't meet the
> requirements of a decider (which must always return an answer in finite
> time)
>
> Any attempt to 'fix' or improve on the latter case, will tend to hurt
> performance in one of the former, and it requires a machine with much
> larger capability then the original problem.
>
> This is a well know property, and generally it is said that this method
> is unsuitable as a halting decider because of it.
>

This does (as has always been my stated goal) refute all of the
conventional self-referential halting problem proofs. None of these
proofa show that halting is undecidable they only show that one
definition of a halt decider does not work.

bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)

Every syntaxtically correct machine description can be divided into
(a) HAS_INFINITE_EXECUTION
(b) DOES_NOT_HAVE_INFINITE_EXECUTION

An infinite machine that never returns to the same machine state was not
the basis for any of these conventional self-referential halting problem
proofs.

I have as I have claimed correctly refuted the conventional
self-referential halting problem proofs.

[olcott]

On 10/25/2020 3:42 PM, Alan Mackenzie wrote:
> In comp.theory olcott <No...@nowhere.com> wrote:

>> On 10/25/2020 12:02 PM, Richard Damon wrote:
>

> [ .... ]

>
>>> If 'Aborted' has no limitations on it, than this halt decider is
>>> worthless, as it could just up and decide that it needs to abort ALL
>>> machines, and if the only test was did it abort it, it would be right.
>
>> You just really are not paying any attention at all are you?
>
>> The simplest possible way to define a halt decider is to have the halt
>> decider directly execute its input exactly one execution step / state
>> transition at a time.
>
>> If we define the halt decider in this simplest possible way then it must
>> stop executing its input as soon as it determines that its input would
>> not otherwise ever halt.
>

> I think you're the one not paying attention. Such a determination of an
> alleged halt decider is not possible. That is a mathematical theorem.
> If you want to advance this argument, you should call the thing a
> "partial halt decider".
>
This does (as has always been my stated goal) refute all of the
conventional self-referential halting problem proofs. None of these
proofs show that halting is undecidable they only show that one

definition of a halt decider does not work.

bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)

Every syntactically correct machine description can be divided into
(a) HAS_INFINITE_EXECUTION
(b) DOES_NOT_HAVE_INFINITE_EXECUTION

I have as I have claimed correctly refuted the conventional
self-referential halting problem proofs.

[olcott]

On 10/25/2020 4:13 PM, Richard Damon wrote:

> On 10/25/20 4:51 PM, olcott wrote:
>>
>> This does (as has always been my stated goal) refute all of the
>> conventional self-referential halting problem proofs. None of these
>> proofa show that halting is undecidable they only show that one
>> definition of a halt decider does not work.
>>
>> bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)
>>
>> Every syntaxtically correct machine description can be divided into
>> (a) HAS_INFINITE_EXECUTION
>> (b) DOES_NOT_HAVE_INFINITE_EXECUTION
>>
>> An infinite machine that never returns to the same machine state was not
>> the basis for any of these conventional self-referential halting problem
>> proofs.
>>
>> I have as I have claimed correctly refuted the conventional
>> self-referential halting problem proofs.
>

> Except you don't refute the proof, you (attempt to) refute a straw man
> similar problem.

This is decidable:

void H_Hat(u32 M)
{
if (Aborted_Because_Non_Halting_Behavior_Detected(M, M))
MOV_EAX_0 // Execution of M(N) has been aborted
else
{
MOV_EAX_1 // M(N) has halted
HERE: goto HERE;
}
HALT
}


void H(u32 M, u32 N)
{
if (Aborted_Because_Non_Halting_Behavior_Detected(M, M))
MOV_EAX_0 // Execution of M(N) has been aborted
else
MOV_EAX_1 // M(N) has halted

HALT
}


int main()
{
u32 M = (u32)H_Hat;

H(M, M); // MOV_EAX_0
HALT

[Melzzzzz]

On 2020-10-25, olcott <No...@NoWhere.com> wrote:
> On 10/25/2020 4:13 PM, Richard Damon wrote:
>> On 10/25/20 4:51 PM, olcott wrote:
>>>
>>> This does (as has always been my stated goal) refute all of the
>>> conventional self-referential halting problem proofs. None of these
>>> proofa show that halting is undecidable they only show that one
>>> definition of a halt decider does not work.
>>>
>>> bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)
>>>
>>> Every syntaxtically correct machine description can be divided into
>>> (a) HAS_INFINITE_EXECUTION
>>> (b) DOES_NOT_HAVE_INFINITE_EXECUTION
>>>
>>> An infinite machine that never returns to the same machine state was not
>>> the basis for any of these conventional self-referential halting problem
>>> proofs.
>>>
>>> I have as I have claimed correctly refuted the conventional
>>> self-referential halting problem proofs.
>>
>> Except you don't refute the proof, you (attempt to) refute a straw man
>> similar problem.
>
> This is decidable:
>
>
> void H_Hat(u32 M)
> {
> if (Aborted_Because_Non_Halting_Behavior_Detected(M, M))

Where is implementation of this function?

--
current job title: senior software engineer
skills: c++,c,rust,go,nim,haskell...

press any key to continue or any other to quit...
U ničemu ja ne uživam kao u svom statusu INVALIDA -- Zli Zec
Svi smo svedoci - oko 3 godine intenzivne propagande je dovoljno da jedan narod poludi -- Zli Zec
Na divljem zapadu i nije bilo tako puno nasilja, upravo zato jer su svi
bili naoruzani. -- Mladen Gogala

[olcott]

On 10/25/2020 4:33 PM, Richard Damon wrote:

> I think you don't understand how proofs work.
>
> If a conjecture says it will work of ALL things, and you come up with 1
> exception, than the conjecture is disproved.
>
> Linz's arguement doesn't apply any restrictions on the Halt Decider
> other than what the definition is of a Halt Decider, thus when he shows
> that the Halt Decider, that is ANY Halt Decider (built as a Turing
> Machine) can't decide on his machine, he has shown that NO Halt Decider
> can be made that meets the requirements of a Halt Decider.

When my decider decides his counter-example case his proof is refuted:

bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)

> When I run the machine H(H_Hat, H_Hat) then it gives me an answer by its
> terminal state (if it doesn't, it doesn't meet the requirements of a
> Halt Decider).

We can ask an incorrect question:
Is the following sentence: "This sentence is not true." true or false?

Or we can rephrase the question so that it has a correct answer:
Is the following sentence: "This sentence is not true." true?

We can ask the halt deciding question in a way that allows the input
program to do the opposite of whatever the halt decider decides:
"Does this input program halt on its input (yes or no)?"

Or we can ask the halt deciding question in such a way where it is
impossible for the input program to do the opposite of what the halt
decider decides:

When the input program is executed on its input did this execution have
to be aborted to prevent infinite execution?

Some undecidable problems are only undecidable because we did not phrase
the question so that it has a correct answer.

Any question that has no correct answer is an incorrect question.

The logical law of polar questions copyright 2015 PL Olcott
https://groups.google.com/g/sci.lang/c/AO5Vlupeelo/m/nxJy7N2vULwJ


> If it ends up in the state that says the input Halted,
> then when I run H_Hat(H_Hat), it must halt or H failed. If it ends up in
> the state that says that the input did not halt (or had Infinite
> execution) then when I run H_Hat(H_Hat) it must not halt.
>
> But, as long as the code for H is consistent in its answer (and if it
> isn't then it has also violated the rules for a Turning Machine) then if
> H said H_Hat(H_Hat) will halt, it will execute forever, and if it said
> that it wouldn't halt (or execute infinitely) then it will Halt in
> finite time, thus H was wrong.
>
> Your failed attempt to rede4fine things and say that the answer means
> that H_Hat(H_Hat) actually would have had infinite execution if not
> aborted is wrong, because THAT H_Hat never had infinite execution time,
> and if it did, then that means that H(H_Hat, H_Hat) also had to have had
> infinite execution time, in violation of the ground rules of a decided.
>
> Yes, if the trace function didn't have a trap to stop the infinite loop,
> then H would not have returned, but that then would have been a flaw in
> the Halt Decider, the fact that the decider logic did abort the trace,
> says that H_Hat (the outer) did NOT have infinite execution time.

[olcott]

On 10/25/2020 4:55 PM, Melzzzzz wrote:
> On 2020-10-25, olcott <No...@NoWhere.com> wrote:
>> On 10/25/2020 4:13 PM, Richard Damon wrote:
>>> On 10/25/20 4:51 PM, olcott wrote:
>>>>
>>>> This does (as has always been my stated goal) refute all of the
>>>> conventional self-referential halting problem proofs. None of these
>>>> proofa show that halting is undecidable they only show that one
>>>> definition of a halt decider does not work.
>>>>
>>>> bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)
>>>>
>>>> Every syntaxtically correct machine description can be divided into
>>>> (a) HAS_INFINITE_EXECUTION
>>>> (b) DOES_NOT_HAVE_INFINITE_EXECUTION
>>>>
>>>> An infinite machine that never returns to the same machine state was not
>>>> the basis for any of these conventional self-referential halting problem
>>>> proofs.
>>>>
>>>> I have as I have claimed correctly refuted the conventional
>>>> self-referential halting problem proofs.
>>>
>>> Except you don't refute the proof, you (attempt to) refute a straw man
>>> similar problem.
>>
>> This is decidable:
>>
>>
>> void H_Hat(u32 M)
>> {
>> if (Aborted_Because_Non_Halting_Behavior_Detected(M, M))
> Where is implementation of this function?
>

Only the DebugTrace() part of it is fully implemented.
Since I have been working on this nearly all the time for about nine
months as soon as I got the x86utm operating system fully complete I
scaled back my software development to 40 hours per week.

http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf

I explain exactly how the halt decider works so that H() correctly
decides halting of H_Hat():

On 10/25/2020 1:42 PM, olcott wrote:
>Only the outermost Aborted_Because_Non_Halting_Behavior_Detected(M, M)
>has a long enough execution trace to "see" that H_Hat() called
>Aborted_Because_Non_Halting_Behavior_Detected(M, M) twice from the same
>machine address without any conditional code in H_Hat() to terminate
>this infinite recursion. // The 2018-12-13 @ 7:00 PM solution

The above is the key halt deciding decision for this code:

void H_Hat(u32 M)
{
if (DebugTrace(M, M))

MOV_EAX_0 // Execution of M(N) has been aborted
else
{
MOV_EAX_1 // M(N) has halted
HERE: goto HERE;
}
HALT
}

int main()
{
u32 M = (u32)H_Hat;

H_Hat(M); // MOV_EAX_0

[Paavo Helde]

Just a small mistake: 68719476736 bits does not mean 68719476736 states,
it means 2^68719476736 states.

[Melzzzzz]

Problem is that program would not print output it will just abort...
You can do that simpply by running timer and if does not stops on
timeout it aborts. But you don't get result...

[olcott]

> You can do that simply by running timer and if does not stops on

> timeout it aborts. But you don't get result...
>

This thread starts with a simple overview of exactly how the redefined
the halt decider so that it cannot be fooled by the conventional halting
problem trick.

On 10/25/2020 8:33 PM, olcott wrote:
Making the Halting Problem Decidable
[ Includes deciding the Peter Linz proof counter-example ]

It goes on to explain all of the details of exactly how halting is
decided for the the Peter Linz H_Hat() counter example.

I added I/O to my x86utem operating system a couple of days ago.
This seems to be what you are asking for:

Output("Infinite recursion detected at machine address", Address);
OutputString("H_Hat() has been aborted");

[olcott]

I knew that I must have screwed up somewhere.
Good job at correcting my mistake.

[olcott]

On 10/25/2020 10:57 PM, Mike Terry wrote:
> On 25/10/2020 15:30, olcott wrote:
> [...snip...]

>>
>> The task at hand is to provide a a specific input to this function that
>> can be shown to be impossible to decide correctly:
>> Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)
>

> Don't you think that since it's YOU making the claim here (to be
> refuting something), if the behaviour of this function is key to your
> argument, it's YOU who should be proving your case, rather than asking
> /us/ to respond to challenges?  That's typical Nam Ngyuyen tactics!

The would be exactly the same thing as rejecting the Church-Turing
thesis until after someone has proved it.

> Anyway, let's look at your challenge...
>
> We need to be clear exactly what the challenge is right?  Personally I'm
> not inclined to accept any challenge I don't understand, and for which I
> wouldn't know if a proposed solution (if one exists) would be correct or
> not.
>
> So for starters you need to define:
>
> 1)  The program spec for
> Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)
>
> 2)  Exactly what you mean by "impossible to decide correctly".


void H_Hat(u32 M)
{
if (!Halts(M, M))
MOV_EAX_0 // Does not Halt
else
{
MOV_EAX_1 // Halts

HERE: goto HERE;
}
HALT
}


void H(u32 M, u32 N)
{

if (!Halts(M, M))
MOV_EAX_0 // Does not Halt
else
MOV_EAX_1 // Halts

HALT
}

int main()
{
u32 M = (u32)H_Hat;
H(M, M);
HALT
}

To the question:
Does H_Hat halt on it input H_Hat?
Both Yes and No are the wrong final state to transition to.

> Also more generally,
>
> 3)  Is Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) a
> specific implementation (in C perhaps?) and do you actually have that
> souce code?

I will have it so that it correctly decides the Peter Linz H_Hat()
shortly. Since I have worked on this about 80 hours per weeks for six
months I have reduced my coding time to less than 40 hours per week for
this home stretch.

> 4)  Why not use a shorter name, because this is UseNet, and there are
> quite restrictive guidelines for line lengths.  I'm all for suggestive
> function names, but we need to be practical!  What about ABNHBD()?

No, Not all. Not in the least little bit.
The name must be utterly self-descriptive to eliminate any confusion

> -----------------------
>
> For (2) the only interpretation that currently makes sense to me is
>
> "provide an input (P,I) for which
> Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) gives a
> response that doesn't meet it's spec."

Yes and I show an overview of the architecture of the halting algorithm
as it would be applied to a UTM halt decider deciding the halting of its
subordinate UTM below:

The redefined halt decider UTM executes its subordinate UTM one state
transition at a time until it detects non-halting behavior or its
subordinate UTM has terminated normally.

If the halt decider UTM detects non-halting behavior of its subordinate
UTM it simply stops executing the subordinate and transitions to its own
final state of ABORTED_NON_TERMINATING_BEHAVIOR.

If the subordinate UTM terminates normally the halt decider UTM
transitions to its own final state of SUBORDINATE_HAS_TERMINATED.

The redefined halt decider is not subject to the conventional halting
problem trick. Its input cannot possibly do the opposite of whatever it
decides because the input has already terminated before the halt decider
makes its decision.

[olcott]

On 10/24/2020 3:13 PM, olcott wrote:
> x86utm was created to be a master UTM that can execute subordinate UTMs
> or TMs in DebugStep() mode. Here are some of its key operating system
> functions:
>
> u32* Allocate(u32 size);
> void SaveState(Registers* state);
> void LoadState(Registers* state);
> u32  DebugStep(Registers* master_state, Registers* slave_state);
> void PushBack(u32* S, u32 M); // similar to c++
>
> The following code is based on the Linz H and Ĥ Turing Machine
> templates: http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
>
>

> void H_Hat(u32 M)
> {
>   if (Aborted_Because_Non_Halting_Behavior_Detected(M, M))

>     MOV_EAX_0  // Execution of M(N) has been aborted
>   else
>   {
>     MOV_EAX_1  // M(N) has halted

>     HERE: goto HERE;
>   }
>   HALT
> }
>
>
> void H(u32 M, u32 N)
> {

>   if (Aborted_Because_Non_Halting_Behavior_Detected(M, N))

>     MOV_EAX_0  // Execution of M(N) has been aborted
>   else
>     MOV_EAX_1  // M(N) has halted

>   HALT
> }
>
>
> int main()
> {
>   u32 M = (u32)H_Hat;
>   H(M, M);

>   HALT;

> }
>
> The simplest possible way to define a halt decider is to have a UTM
> execute its program under test (PUT) until it detects non-halting
> behavior of its (PUT) or its (PUT) terminates on its own.
>

> When the UTM halt decider decides that its (PUT) would not otherwise
> halt it stops executing its (PUT) and reports that non halting behavior
> has been detected. If it does not detect non-halting behavior then it
> reports that its input program has terminated.
>
> This is exactly the same thing as the conventional NON_HALTING / HALTING
> return values of a conventional halt decider except that this definition
> of a halt decider cannot be fooled by any cheap trick.
>

> Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) == true
> means that the input has infinite execution.
>
> Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) == false
> means that the input DOES NOT HAVE infinite execution.
>
> There are no programs left over that can be shown to be undecidable.
>
> ALL INPUT IS DIVIDED INTO EXACTLY ONE OF THESE TWO SETS
> (a) The input Program/TM has infinite execution.
> (b) The input Program/TM DOES NOT HAVE infinite execution.
>

void H_Hat(u32 M)
{
if (!Halts(M, M))
MOV_EAX_0 // Does not Halt
else
{
MOV_EAX_1 // Halts
HERE: goto HERE;
}
HALT
}


void H(u32 M, u32 N)
{
if (!Halts(M, M))
MOV_EAX_0 // Does not Halt
else
MOV_EAX_1 // Halts
HALT
}

int main()
{
u32 M = (u32)H_Hat;
H(M, M);
HALT
}

To the question:
Does H_Hat halt on it input H_Hat?
Both Yes and No are the wrong final state to transition to.

void H_Hat(u32 M)
if (Aborted_Because_Non_Halting_Behavior_Detected(M, M))

MOV_EAX_1 // Execution of M(N) has been aborted
else
{
MOV_EAX_0 // M(N) has halted

HERE: goto HERE;
}
HALT
}


void H(u32 M, u32 N)
{

if (Aborted_Because_Non_Halting_Behavior_Detected(M, M))
MOV_EAX_1 // Execution of M(N) has been aborted
else
MOV_EAX_0 // M(N) has halted

HALT
}


int main()
{
u32 M = (u32)H_Hat;
H(M, M);
HALT
}

[Mike Terry]

On 26/10/2020 17:36, olcott wrote:
> On 10/25/2020 10:57 PM, Mike Terry wrote:
>> On 25/10/2020 15:30, olcott wrote:
>> [...snip...]
>>>
>>> The task at hand is to provide a a specific input to this function that
>>> can be shown to be impossible to decide correctly:
>>> Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)
>>
>> Don't you think that since it's YOU making the claim here (to be
>> refuting something), if the behaviour of this function is key to your
>> argument, it's YOU who should be proving your case, rather than asking
>> /us/ to respond to challenges? That's typical Nam Ngyuyen tactics!
>
> The would be exactly the same thing as rejecting the Church-Turing
> thesis until after someone has proved it.
>
>> Anyway, let's look at your challenge...
>>
>> We need to be clear exactly what the challenge is right? Personally
>> I'm not inclined to accept any challenge I don't understand, and for
>> which I wouldn't know if a proposed solution (if one exists) would be
>> correct or not.
>>
>> So for starters you need to define:
>>
>> 1) The program spec for
>> Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)

??

>>
>> 2) Exactly what you mean by "impossible to decide correctly".
>
>
> void H_Hat(u32 M)
> {
> if (!Halts(M, M))
> MOV_EAX_0 // Does not Halt
> else
> {
> MOV_EAX_1 // Halts
> HERE: goto HERE;
> }
> HALT
> }
>
>
> void H(u32 M, u32 N)
> {
> if (!Halts(M, M))
> MOV_EAX_0 // Does not Halt
> else
> MOV_EAX_1 // Halts
> HALT
> }
>
> int main()
> {
> u32 M = (u32)H_Hat;
> H(M, M);
> HALT
> }
>
> To the question:
> Does H_Hat halt on it input H_Hat?
> Both Yes and No are the wrong final state to transition to.
>

None of that explains what you mean by "impossible to decide correctly"
in the context of your challenge, or even make sense in the context of
the HP...

For GIVEN (/FIXED/) programs H and H_Hat, the calculation H_Hat(H_Hat)
either halts or never halts, right? Exactly one of those possibilities
is correct. So there IS a perfectly correct answer to the question
"Does H_Hat(H_Hat) halt?".

A halt decider "decides correctly" if it halts in the corresponding halt
decider state (Yes [HALTS or NONHALTS[halts] or q_n [doesn't halt]).

So in fact, one of the Yes and No IS the right final state to transition
to! The fact is simply H is one of those putative halt deciders that
transitions to the WRONG state.


Let's make this clearer. For YOUR ACTUAL (soon to be delivered) H and
H_Hat, which of these is the case?

a) H_Hat(H_Hat) halts
b) H_Hat(H_Hat) never halts

>> Also more generally,
>>
>> 3) Is Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) a
>> specific implementation (in C perhaps?) and do you actually have that
>> souce code?
>
> I will have it so that it correctly decides the Peter Linz H_Hat()
> shortly. Since I have worked on this about 80 hours per weeks for six
> months I have reduced my coding time to less than 40 hours per week for
> this home stretch.
>

OK, so you must at least know the answer to my (a) (b) question above,
right?

>> 4) Why not use a shorter name, because this is UseNet, and there are
>> quite restrictive guidelines for line lengths. I'm all for suggestive
>> function names, but we need to be practical! What about ABNHBD()?
>
> No, Not all. Not in the least little bit.

Repeating this clumsy phrase makes you look goofy.

> The name must be utterly self-descriptive to eliminate any confusion

Well, I'm not going to keep on typing all that, so I'll use ABNHBD, and
you'll know what I mean.

The right way to eliminate confusion is for you to give the
specification for the routine, which you've not done yet. The long name
fails as a spec!

>
>> -----------------------
>>
>> For (2) the only interpretation that currently makes sense to me is
>>
>> "provide an input (P,I) for which
>> Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) gives a
>> response that doesn't meet it's spec."
>
> Yes

You're saying this is the correct answer to my question (2)?

Then you should have said this in response to the question, whereas what
you actually answered was a long description of two programs, with an
incorrect statement about "wrong states".

So... now you need to give that spec!

> and I show an overview of the architecture of the halting algorithm
> as it would be applied to a UTM halt decider deciding the halting of its
> subordinate UTM below:

[... snip ...]

I never asked about this, and you've said all this elsewhere.

Regards,
Mike.

[olcott]

So in other words it is far too difficult for you to understand that:
(a) H.MOV_EAX_0 // in Linz it is a transition to a final state of ((qn))
(b) H.MOV_EAX_1 // in Linz it is a transition to a final state of ((qy))
are both the wrong answer.

If you can't acknowledge this you may have to be written off as not
actually interested in achieving a mutual understanding.

[olcott]

On 10/26/2020 7:43 PM, Mike Terry wrote:

> The wrong answer to what, exactly?  If you mean, the answer to "does
> H_Hat(H_Hat) halt?", then one of them is the correct answer, BUT H HAS
> ALREADY BEEN WRITTEN, and it's too late to change the code, and the
> actual code halts with the wrong state.

The above way of defining a halt decider provides only a single possible
way for the halt decider to provide its halting decision:
(a) H transitions to its final state of ((qy)) indicating YES its input
halts.

(b) H transitions to its final state of ((qn)) indicating NO its input
does not halt.

Because both of these return values can be contradicted by the behavior
of H_Hat() neither one of them is correct.

Do you understand and agree with this?

[Mike Terry]

Any decider has two states, qy and qn that indicate its decision. For a
halting decider, they have the meanings you describe.

>
> Because both of these return values can be contradicted by the behavior
> of H_Hat() neither one of them is correct.
>

For a given H, the logic is already fixed in H as to which of these
states it will transition to, for any particular input. It is too late
to start talking about rewriting H a different way. There is only one
of the states that H can transition to for a given input, and that is
the one its code determines. In the case of H_Hat, that code leads to
the wrong state.

> Do you understand and agree with this?

I understand what I have written. Maybe that is the same as what you mean.

Mike.

[olcott]

Intuitively, a decider should be a Turing machine that given an input,
halts and either accepts or rejects, relaying its answer in one of many
equivalent ways, such as halting at an ACCEPT or REJECT state, or
leaving its answer on the output tape. Yuval Filmus
https://cs.stackexchange.com/questions/84433/what-is-decider

Yuval Filmus top 0.04% overall Assistant Professor in the Department of
Computer Science at the Technion.

The redefined halt decider UTM executes its subordinate UTM one state
transition at a time until it detects non-halting behavior or its
subordinate UTM has terminated normally.

If the halt decider UTM detects non-halting behavior of its subordinate
UTM it simply stops executing the subordinate and transitions to its own
final state of ABORTED_NON_TERMINATING_BEHAVIOR.

If the subordinate UTM terminates normally the halt decider UTM
transitions to its own final state of SUBORDINATE_HAS_TERMINATED.

Thus dividing ALL of its input into one of two mutually exclusive
categories proving that meets the above definition of a decider.

The second category is exactly the same thing as HALTING so it is a halt
decider.

>>
>> Because both of these return values can be contradicted by the behavior
>> of H_Hat() neither one of them is correct.
>>
> For a given H, the logic is already fixed in H as to which of these
> states it will transition to, for any particular input.  It is too late
> to start talking about rewriting H a different way.  There is only one
> of the states that H can transition to for a given input, and that is
> the one its code determines.  In the case of H_Hat, that code leads to
> the wrong state.
>
>> Do you understand and agree with this?
>
> I understand what I have written.  Maybe that is the same as what you mean.
>
> Mike.

I have never detected a single moment where you were insincere or
disingenuous so that is very good. If we both really very sincerely want
to achieve mutual understanding then I am sure that we will definitely
get there, these things don't have the kind of subjectivity that could
be permanently unresolvable.

[olcott]

On 10/26/2020 11:03 PM, Mike Terry wrote:

> Yes, there are alternative definitions that amount to the same thing.
> For a Halt Decider, the key thing is that it decides all (valid) input
> pairs, and that the two halting states divide the inputs into halting
> and non-halting.

>
>>
>> The redefined halt decider UTM executes its subordinate UTM one state
>> transition at a time until it detects non-halting behavior or its
>> subordinate UTM has terminated normally.
>>
>> If the halt decider UTM detects non-halting behavior of its subordinate
>> UTM it simply stops executing the subordinate and transitions to its own
>> final state of ABORTED_NON_TERMINATING_BEHAVIOR.
>>
>> If the subordinate UTM terminates normally the halt decider UTM
>> transitions to its own final state of SUBORDINATE_HAS_TERMINATED.
>>
>> Thus dividing ALL of its input into one of two mutually exclusive
>> categories proving that meets the above definition of a decider.
>>
>> The second category is exactly the same thing as HALTING so it is a halt
>> decider.
>

> Well, this sounds like some progress!
>
> If your soon-to-be-delivered H will always terminate (make a decision),
> and if it will decide SUBORDINATE_HAS_TERMINATED if and only if its
> input is HALTING, then it would indeed be a halt decider.  In fact for
> your purposes these conditions only need hold for the one input pair of
> interest: (H_Hat, H_Hat).
>
> Just to be clear, HALTING is the category of pairs (P, I) such that P
> when run with input I halts.  (I don't see what else you could mean...)
>
> Mike.

Because it will not be all knowing there will initially be only one case
that it decides ABORTED_NON_TERMINATING_BEHAVIOR and that is
(H_Hat, H_Hat). Every other case it will simply assume halts.

The key thing is that there are no cases that can be shown to be
undecidable for a partial halt decider of this design.

[olcott]

It seems that it is a partial WOULD_NOT_HALT decider. It is not even
looking at halting. It is only looking at WOULD_NOT_HALTing.

[olcott]

On 10/27/2020 9:57 AM, Mike Terry wrote:

> OK, I know we are only interested in the input pair (H_Hat, H_Hat).
>
> You say it is only detecting WOULD_NOT_HALTing.  What does that mean?

Do you think that it might mean that someone smashed their vanilla ice
cream cone on the floor? How about it meaning that I went for a long
drive in the country on a sunny day?

> Specifically the problem is your inclusion of the word "WOULD".  Any
> calculation P(I) [for pgm P, with input data I] is either halting or
> non-halting.

ABORTED_BECAUSE_NON_HALTING_BEHAVIOR_DETECTED

> Is the following true?
>
> -  ABNHBD(H_Hat, H_Hat) will only return ABORTED if H_Hat(H_Hat) is
> non-halting.

Not exactly and precisely.
bool Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat)
returns true whenever its input has to be aborted or the halt decider
would get stuck in infinite recursion.

> ["is non-halting" means the same as "is in category HALTING" where
> HALTING is the usual HP term for the category of pairs (P,I) where P
> halts when it runs with input I, i.e. nothing to do with emulators or
> "aborting" anything!]

Not exactly and precisely because the way that the categories are
conventionally divided into HALTING and LOOPING allows an input program
to do the opposite of whatever the halt decider decides.

These categories eliminate that problem:
(a) ABORTED_BECAUSE_NON_HALTING_BEHAVIOR_DETECTED
(b) INPUT_HAS_ALREADY_HALTED

>
> Turning this around, this equivalent statement may be easier:
>
> -  If calculation H_Hat(H_Hat) halts, ABNHBD(H_Hat, H_Hat) will not
> return ABORTED.

No, not at all, not in the least little bit.

bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)

is the architectural design of a halt decider that always correctly
divides all of its inputs into:
(a) ABORTED_BECAUSE_NON_HALTING_BEHAVIOR_DETECTED
(b) INPUT_HAS_ALREADY_HALTED

> On the face of it, this sounds plausible because if a calculation P(I)
> halts, then how could ABNHBD() encounter any "non-halting behaviour",
> but you have muddied the water by adding the unclear WOULD into the
> picture.  I believe this is exactly the area where you have become
> confused!
>
>
> Mike.