Re: Halting Problem Final Conclusion [2021 update to my 2004 statement]

[olcott]

On 9/5/2004 11:21 AM, Peter Olcott wrote:
> The Liar Paradox can be shown to be nothing more than
> a incorrectly formed statement because of its pathological
> self-reference. The Halting Problem can only exist because
> of this same sort of pathological self-reference.
>
> The primary benefit of solving the Halting Problem was to
> detect programs that failed to halt, thus were incorrect.
> Pathological self-reference can also be viewed as a form
> of error. If the Halting Problem is redefined (which does not
> refute anyone), then this redefined problem can be easily
> solved.
>
> Now we have three possible correct results:
> (a) Halts
> (b) Does Not Halt
> (c) Pathological Self Reference to Halt
>
> Compared to my prior claims, this one seem trivial and
> obvious. Possibly this claim adds a slight nuance to the
> problem that has not been widely discussed before.
> If we construe pathological self-reference as another
> error condition, then this does remove the impossibility
> of creating a useful tool.

I first came up with this update 2018-12-13 @ 7:00 PM at the Westroads
mall Omaha NE.

void H_Hat(u32 P)
{
u32 Input_Halts = Halts(P, P);
if (Input_Halts)
HERE: goto HERE;
return;
}

It turns out that inputs having pathological self-reference can be
decided to be non-halting. The invocation of a halt decider that is
based on simulating the execution of its input can be decided to be
infinitely recursive in the above case.

Within the x86 based execution trace of the above user code:
H_Hat() calls the same function from the same machine address with the
same inputs a second time with no other control flow instructions
inbetween.

The above program meets the criteria of a program with infinite
execution: Any program that would not halt unless its simulation was
stopped is a program with the property of infinite execution.


--
Copyright 2004 and 2021 Pete Olcott

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

[gamo]

El 2/1/21 a las 19:12, olcott escribió:

> Now we have three possible correct results:
> (a) Halts
> (b) Does Not Halt
> (c) Pathological Self Reference to Halt

Hello. You happen to have some insight in this problem.
In which type do you clasify te option to halt
*if* an arbitrary precision and/or repeated solution counter
reach a thresold???

Thank you. Best.


--
http://gamo.sdf-eu.org/
"What happens in EuroVegas it remains in EuroVegas"

[gamo]

El 3/1/21 a las 21:17, gamo escribió:

> El 2/1/21 a las 19:12, olcott escribió:
>> Now we have three possible correct results:
>> (a) Halts
>> (b) Does Not Halt
>> (c) Pathological Self Reference to Halt
>
> Hello. You happen to have some insight in this problem.
> In which type do you clasify te option to halt
> *if* an arbitrary precision and/or repeated solution counter
> reach a thresold???
>
> Thank you. Best.
>
>

s/te/the/;
s/tresold/treshold/;

Sorry!

[olcott]

On 1/4/2021 8:52 AM, Andy Walker wrote:
> On 04/01/2021 12:10, Richard Damon wrote:
>> So if detecting the recursion can't be done, then part of PO's trick is
>> the passing of pointer to functions as an address rather than actually
>> passing an input 'tape'. This allows him to trivially solve the
>> recursion detection.
>
>     No, that isn't, in itself, a "trick".  After all, we don't
> expect a compiler to make extra copies of the function code whenever
> a function is called.  A TM has access to the same methods that a
> real computer has for enabling function calls and recursion -- stash
> away return addresses, stack parameters, put return values onto the
> stack, blah-de-blah. ...
>

Thanks for adding some real software engineering to this dialogue.

>> This says that the REAL problem with his proof is that his 'UTM' doesn't
>> fully support the operation of 'make a copy of the input', and thus is
>> shown to not be a Turing Complete environment.
>
>     ... The real problems are (a) recursion is not the only way
> a program can fail to halt;

I don't have to solve the halting problem to refute the conventional
proofs. My system already detects some cases of infinte loops.

> and (b) PO's recursion detection works
> only in very trivial cases.  Oh, and of course

No sense making the system more elaborate than required to refute the
conventional proofs. This would only confuse people making it more
difficult for them to see that I refuted the conventional proofs.

> (c) the fact that his
> "H_hat" doesn't [yet] correspond to his "H" in the correct way;

Bullshit. My Halts() corresponds to my H_Hat() in the simplest "do the
opposite of whatever the halt decider decides" template that all the
conventional halting problem proofs are based on.

> he
> seems to want to construct an "H" that defeats "H_hat" rather than
> seeing that "H_hat" defeats a /given/ "H".  These have been explored
> far too much in these threads, and I don't propose to add to that.
>

There is no longer any "given" H that can be defeated. The standard
template that all the conventional halting problem, undecidability
proofs are based has been defeated.

All three halt deciding modes now are fully operational:
(a) Global
(b) Local
(c) Disabled

--
Copyright 2021 Pete Olcott

[Vir Campestris]

On 05/01/2021 02:49, olcott wrote:
> I don't have to solve the halting problem to refute the conventional
> proofs. My system already detects some cases of infinte loops.

We've got infinite loops in our production code.

There are threads whose job is to monitor the status of something for
the life of the system.

Andy

[olcott]

On 1/6/2021 11:05 AM, Malcolm McLean wrote:
> On Wednesday, 6 January 2021 at 05:00:49 UTC, olcott wrote:
>> On 1/5/2021 5:52 PM, Kaz Kylheku wrote:
>>> On 2021-01-05, olcott <No...@NoWhere.com> wrote:
>>>> On 1/5/2021 4:24 PM, Kaz Kylheku wrote:
>>>>> ["Followup-To:" header set to comp.theory.]
>>>>> On 2021-01-05, olcott <No...@NoWhere.com> wrote:
>>>>>> On 1/5/2021 3:15 PM, Kaz Kylheku wrote:
>>>>>>> ["Followup-To:" header set to comp.theory.]
>>>>>>> On 2021-01-05, olcott <No...@NoWhere.com> wrote:
>>>>>>>> On 1/5/2021 1:15 PM, Kaz Kylheku wrote:
>>>>>>>>> On 2021-01-05, olcott <No...@NoWhere.com> wrote:
>>>>>>>>>> The key reason why I need three halt deciding modes is so that people
>>>>>>>>>> can see the nuanced details of what is really going on with this case:
>>>>>>>>>
>>>>>>>>> Your results are invalid if you don't follow these requirements,
>>>>>>>>> (and possibly even if you do):
>>>>>>>>>
>>>>>>>>
>>>>>>>> The above statement is moronically stupid when understood within this
>>>>>>>> context:
>>>>>>>
>>>>>>> Note that I included the part in parentheses due to my lingering
>>>>>>> suspicion that you don't understand logical if/then conditionals.
>>>>>>>
>>>>>>> I'm emphasizing that the requirements I stated are necessary, not
>>>>>>> sufficient.
>>>>>>>
>>>>>>>> Without (the mandatory prerequisite of) carefully studying the full
>>>>>>>> execution trace of this code:
>>>>>>>>
>>>>>>>> int main()
>>>>>>>> {
>>>>>>>> H_Hat((u32)H_Hat);
>>>>>>>> HALT
>>>>>>>> }
>>>>>>>>
>>>>>>>> in all three halt decider modes: {disabled, local, global}
>>>>>>>>
>>>>>>>> while carefully looking for any error and finding none:
>>>>>>>> The above statement is moronically stupid
>>>>>>>
>>>>>>> But the statement along with the requirements it refers to is not in
>>>>>>> confict with what you're saying here.
>>>>>>>
>>>>>>> The first requirement just says: you can't interpret the traces
>>>>>>> under one mode (e.g. local) as pertaining to the halting of
>>>>>>> H_Hat(H_Hat) in any other mode (e.g. disabled).
>>>>>>>
>>>>>>> Study all the traces you want; just don't mix modes.
>>>>>>>
>>>>>>
>>>>>> When the execution trace of this code:
>>>>>> (full source code provided)
>>>>>>
>>>>>> int main()
>>>>>> {
>>>>>> H_Hat((u32)H_Hat);
>>>>>> }
>>>>>>
>>>>>> Is carefully examined looking for coding or logic errors then the
>>>>>> non-existence of coding or logic errors proves that the halt decider
>>>>>> does decide the above code correctly as infinitely recursive in global
>>>>>> mode and the input to H_Hat() as infinitely recursive in local mode.
>>>>>
>>>>> H_Hat isn't infinitely recursive in local mode, because Halts isn't.
>>>>> So the decision is wrong.
>>>> You might be bright enough to understand what pathological
>>>> self-reference is, how it screws up reasoning, and how it can be overcome.
>>>
>>> The self-reference in the halting proofs isn't pathological. It is midly
>>> ironic, at best. And in fact, I will argue that it isn't self-reference.
>> // P is the machine address of H_Hat()

>> void H_Hat(u32 P)
>> {
>> u32 Input_Halts = Halts(P, P);
>> if (Input_Halts)
>> HERE: goto HERE;
>> return;
>> }
>>

>> Here is a multiple choice question for you please don't pull the same
>> dishonest dodge crap that Ben does:
>>
>> Is the value that Halts() can correctly return to H_Hat()
>> (a) true
>> (b) false
>> (c) neither true nor false
>>
>> Although you can provide commentary after your multiple choice
>> selection, failing to choose one of the three options above will cause
>> me to conclude that you are deceitful and no longer worth my time.
>>
> OK, so there's a good insight here. Halts() is reducible to either return true,
> return false, or do neither. We don't need any other ocde, [code] because we are
> only interested in one outcome.
>

No this is a huge mistake. When we consider which of the two values that
Halts() can return to H_Hat() the correct answer is neither because the
invocation of Halts() by H_Hat() would be infinitely recursive if
Halts() did not abort this invocation.

There is never ever any case where any function can ever correctly
return a value to its infinitely recursive invocation, not even if we
sprinkle magic fairy dust.

Although a decider must always eventually indicate a decision it is not
required to return a result to every caller. That so many people in this
forum seemed to think otherwise seems quite nuts. They might as well
have said that all infinite loops only iterate ten times.

The term decider doesn't really have a standard meaning.
In fact, it is lamentable that Sipser chose the terms
decider and recognizer, since they seem to confuse students.

Yuval Filmus
Assistant Professor in the Henry and Marilyn Taub Department
of Computer Science at the Technion – Israel Institute of
Technology.

https://cs.stackexchange.com/questions/84433/what-is-decider

> So it's clear that we can neither return "true" nor "false", because H_Hat will
> invert it an make it incorrect.

Pathological Self-Reference(Olcott 2004)
is defined as the case where a
(a) declarative sentence,
(b) polar question,
(c) logical proposition
cannot be resolved to yes/no true/false because of self-reference.

When we ask the polar question:
What Boolean value can Halts() correctly return to H_Hat()
we see that this question has Pathological Self-Reference(Olcott 2004).

> So we must do neither. Either return an intermediate
> value if the programming language allows it (most don't, but you could experiment
> with a tri-valued logic language),

> or abort the program, pas up a result to a
> higher level (Most languages allow for this sort of thing, but Turing machines
> don't )

You reject the Church-Turing thesis?

> or enter an infinite loop (Turing machines allow for this).

[olcott]

On 1/7/2021 5:57 AM, Ben Bacarisse wrote:
> Kaz Kylheku <563-36...@kylheku.com> writes:
>
>> On 2021-01-06, olcott <No...@NoWhere.com> wrote:
>>> The question is hard-wired into the conventional undecidability proof
>>> trick of
>>
>> No, it isn't. Not any more than the "have you stopped beating your wife"
>> question is hard-wired into the psychology of marriage.
>>
>> It's just nonsense that you're insisting on.
>>
>> Nobody in their right mind asks whether a function that doesn't exist
>> returns true or false, or whether a nonexistent camel is dromedary or
>> bactrian, or whether someone not known to beat their wife (or not even
>> married) has stopped beating their wife.
>>
>> Pretending that the phrase "nonexistent function" refers to a real
>> object, which has to have real properties (like returning true or
>> false) is just word semantic nonsense.
>
> The trouble PO has is that "the function" clearly exists. He's written
> it, and he can see that neither return value can be right.
>
> Don't get me wrong -- I do understand what you are saying. "The
> function" that does not exist is a correct halt decider (that's the CS
> point of view) but PO is thinking like an engineer. He has actual code.
> For him "the function" is that real, actual code and, at some level, it
> just appeared to have "a bug" in that it gives the wrong answer in some
> cases. But he can now see that this bug can't be fixed. To an
> engineer, an unfixable bug means there is something wrong with the
> specification.
>
> This is why I hate the argument that Linz presents, even if he does so
> only for historical interest. To engineers (and most software people
> have been taught to think like engineers) the "assume H is a halt
> decider" style of proof makes it simply too easy to think that there's a
> function with an, apparently, unfixable bug. A class of engineers will
> spend a lot of time trying to fix the bug and, failing that, try to find
> out what's wrong with the specification.
>
> The other proof in Linz is also problematic for a class of engineers
> because it is so abstract. Like a lot of mathematical proofs it's hard
> to see how it explains the "why". It's just a bald fact -- a halt
> decider would contradict theorem 11.5 (or whatever). That's why I
> preferred the diagonal argument: every TM computes a function (sometimes
> a partial one) but every TM has the property that the function it
> computes is not the halting function. Nothing nonexistent is ever
> imagined, we simply learn something universal about TMs.

>

void H_Hat(u32 P)
{
u32 Input_Halts = Halts(P, P);
if (Input_Halts)
HERE: goto HERE;
return;
}

The diagonal argument only shows that neither true nor false is a
correct value that Halts() can return to H_Hat().

This shallow analysis utterly ignores the possibility that H_Hat() can
be correctly decided by aborting the simulation of H_Hat before Halts()
returns any value to H_Hat() on the basis that the H_Hat() invocation of
Halts() would otherwise be infinitely recursive if Halts() did not stop
simulating it.

On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
> A computation that would not halt if its simulation were not
> halted is indeed a non-halting computation.


int main()
{
u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
}

What is decider?

The term decider doesn't really have a standard meaning.
In fact, it is lamentable that Sipser chose the terms decider
and recognizer, since they seem to confuse students.

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.

answered Nov 25 '17 at 8:35 Yuval Filmus top 0.03% overall

Assistant Professor in the Henry and Marilyn
Taub Department of Computer Science at the
Technion – Israel Institute of Technology.
https://cs.stackexchange.com/questions/84433/what-is-decider

The above proves that your stupid idea that a decider must return a
value to its every invocation is just as dishonest as many of the
things that you say. A decider must eventually halt in an accept
or reject state, yet is never required to return any value to it
otherwise infinite invocation.

[olcott]

On 1/9/2021 11:30 AM, Ben Bacarisse wrote:
> Kaz Kylheku <563-36...@kylheku.com> writes:
>

>> ["Followup-To:" header set to comp.theory.]

>> On 2021-01-09, olcott <No...@NoWhere.com> wrote:
>>> On 1/8/2021 10:39 PM, Kaz Kylheku wrote:
>>>> On 2021-01-09, olcott <No...@NoWhere.com> wrote:
> <cut>
>>>>> The local halt deciding mode does not return a value to its otherwise
>>>>> infinite invocation yet does return a value to main().
>>>>
>>>> Not been shown. You've only give execution traces of this that do not
>>>> reveal the return values of Halts, in programs that do not call
>>>> H_Hat(H_Hat) from main to see whether it halts or not.
>>>>
>>>
>>> void H_Hat(u32 P)
>>
>> Yes, that's exactly the inadequate program I'm talking about, with the
>> inadequate trace.

>>
>>> {
>>> u32 Input_Halts = Halts(P, P);
>>

>> Does this Halts return? What is the value, if it does? That would be
>> good to know.
>
> When H_Hat is called as H_Hat(H_Hat), the call to Halts in H_Hat does
> not return, making H_Hat(H_Hat) a non-terminating computation.

When this same computation is executed in a simulator the Halt decider
determines that the exectution trace of H_Hat() meets this specification:

Infinite Recursion detection AXIOM
(a) Within an execution trace
(b) The same function is called
(c) From the same machine address
(d) With the same data // Richard Damon credit
(e) A second time
(f) Without any control flow instructions inbetween

Thus meeting this mutually agreed to definition of non halting behavior:

On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
> A computation that would not halt if its simulation were not
> halted is indeed a non-halting computation.

On Saturday, November 28, 2020 at 2:00:28 PM UTC-8, olcott wrote:
> Every computation that would not halt if its simulation
> were not halted is by logical necessity a non-halting computation.

The halt decider then stops this otherwise infinite recursion and
decides not halting.

> PO then
> arranges for Halts(H_Hat, H_Hat,) when called from outside H_Hat
> (specifically from main), to return false.
>
> It's what this recent quote (copied from above) means:
>
>>>>> The local halt deciding mode does not return a value to its otherwise
>>>>> infinite invocation yet does return a value to main().
>
> I know you were asking for a test/trace that makes this ruse clear, but
> I don't think it's really needed.

[olcott]

On 1/9/2021 2:07 PM, Kaz Kylheku wrote:
> On 2021-01-09, olcott <No...@NoWhere.com> wrote:

>> On 1/9/2021 12:24 PM, Kaz Kylheku wrote:
>>> On 2021-01-09, olcott <No...@NoWhere.com> wrote:
>>>> On 1/9/2021 11:30 AM, Ben Bacarisse wrote:
>>>>> Kaz Kylheku <563-36...@kylheku.com> writes:
>>>>>
>>>>>> ["Followup-To:" header set to comp.theory.]
>>>>>> On 2021-01-09, olcott <No...@NoWhere.com> wrote:
>>>>>>> On 1/8/2021 10:39 PM, Kaz Kylheku wrote:
>>>>>>>> On 2021-01-09, olcott <No...@NoWhere.com> wrote:
>>>>> <cut>
>>>>>>>>> The local halt deciding mode does not return a value to its otherwise
>>>>>>>>> infinite invocation yet does return a value to main().
>>>>>>>>
>>>>>>>> Not been shown. You've only give execution traces of this that do not
>>>>>>>> reveal the return values of Halts, in programs that do not call
>>>>>>>> H_Hat(H_Hat) from main to see whether it halts or not.
>>>>>>>>
>>>>>>>
>>>>>>> void H_Hat(u32 P)
>>>>>>
>>>>>> Yes, that's exactly the inadequate program I'm talking about, with the
>>>>>> inadequate trace.
>>>>>>
>>>>>>> {
>>>>>>> u32 Input_Halts = Halts(P, P);
>>>>>>
>>>>>> Does this Halts return? What is the value, if it does? That would be
>>>>>> good to know.
>>>>>
>>>>> When H_Hat is called as H_Hat(H_Hat), the call to Halts in H_Hat does
>>>>> not return, making H_Hat(H_Hat) a non-terminating computation.
>>>>
>>>> When this same computation is executed in a simulator the Halt decider
>>>> determines that the exectution trace of H_Hat() meets this specification:
>>>

>>> None of your programs give evidence for this statement. H_Hat(H_Hat)
>>> is a non-terminating computation only in the free-running "disabled"
>>> mode of your simulator (the detection of runaway recursion is disabled).
>>> In the other modes, it is a terminating computation.
>>
>> If you are actually paying attention to what I am saying and not simply
>
> I don't care about what you're saying; I'm pointing to what your *code*
> *isn't* saying.

Infinite Recursion detection AXIOM
(a) Within an execution trace
(b) The same function is called
(c) From the same machine address
(d) With the same data // Richard Damon credit
(e) A second time
(f) Without any control flow instructions inbetween

The execution trace of H_Hat() proves that H_Hat() meets the above
specification therefore proving that H_Hat can be correctly decided as
not halting on this basis without needing to look at the source code.

I will try to clean this up a little. Each of my recent execution traces
had some key detail missing.

Having to look at 320 of pages of source code is not going to make this
any clearer.

Simply understanding that correct halt deciding criteria for H_Hat()
exists [Infinite Recursion detection AXIOM] and seeing that the
execution trace of H_Hat() meets this criteria is all that is really
needed for complete proof that Halts() decides H_Hat() correctly.

[olcott]

On 1/9/2021 4:28 PM, Kaz Kylheku wrote:
> ["Followup-To:" header set to comp.theory.]
> On 2021-01-09, olcott <No...@NoWhere.com> wrote:

>> On 1/9/2021 3:46 PM, Mr Flibble wrote:

>>> Most algorithms of interest do have control flow instructions so I
>>> repeat: what you are banging on about is of little interest to anybody
>>> and has no bearing on the Halting Problem itself as defined.
>>>
>>> /Flibble
>>>
>>
>> By showing how the simplest form of how the:
>> "Do the opposite of whatever the halt decider decides"
>> basis of all the conventional halting problem undecidability
>> proofs is correctly decided as non-halting I have refuted
>> the basis of all of these proofs.
>
> You have not; your program indicates that H_Hat(H_Hat) fails to
> terminate, yet in fact there is every reason to believe that
> that expression terminates.
>

The conventional halting problem undecidability proofs conclude that no
universal halt decider can possibly exist on the basis that a particular
class of universal halt deciders cannot possibly exist.

It seems to be true that no universal halt decider exists that attempts
to divide all of its inputs into halting and not halting on the basis of
answering the question:

Does the input program halt on its input?

On the other hand: A universal halt decider that attempts to divide all
of its inputs into halting and not halting on the basis of answering the
question:

Does the simulation of the input have to be stopped to prevent its
otherwise infinite execution?

Does not suffer from the Pathological self-reference(Olcott 2004) and
can thus be defined.

Because this revised criteria does divide its inputs into halting and
non-halting by this criteria:

On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
> A computation that would not halt if its simulation were not
> halted is indeed a non-halting computation.

On Saturday, November 28, 2020 at 2:00:28 PM UTC-8, olcott wrote:
> Every computation that would not halt if its simulation
> were not halted is by logical necessity a non-halting computation.

it still directly applies to the actual halting problem itself.

[olcott]

On 1/11/2021 12:53 PM, Kaz Kylheku wrote:
> On 2021-01-11, olcott <No...@NoWhere.com> wrote:
>> A halt decider for a specifically defined pattern of inputs is another
>> correct way of saying that I have a partial halt decider.
>
> A function/machine has to correctly decide only one input case to be
> a partial decider.
>
> I also have a partial decider:
>
> bool Halts(u32 P, u32 I)
> {
> return true;
> }
>
> This correctly decides precisely that subset of P(I) pairs that happen
> to halt.
>
> The proof that you're trying to invalidate says, basically this:
>
> "All we can have is partial deciders; we cannot have a total one."
>
> Therefore, someone claiming "I have a partial decider" does not put a
> dent in the proof.
>
>> I have a halt decider for the simplest pattern of the conventional
>> halting problem undecidability proof:
>> "do the opposite of whatever the halt decider decides" pattern.
>
> No you don't. You admitted that your Halts(H_Hat, H_Hat) returns 0
> in a program in which that is the wrong answer because H_Hat(H_Hat)
> returns:
>
> |On 2021-01-10, olcott <No...@NoWhere.com> wrote:
> |>> The inner Halts is looking for the same terminating condition, but since
> |>> it is nested, it has no chance to get that far. The outer-most, oldest
> |>> simulation terminates everything first.
> |>>
> |>> Botom line, 0 is the wrong answer: H_Hat(H_Hat) halts.
> |>
> |> It is only the wrong answer if we are asking the question:
> |> Does the input halt on its input?
>
> I.e. you admit that your halting decider gives the wrong answer under
> the standard halting problem definition; to fix this, you are insising
> that everyone accept some alternative formulation of the problem,
Does the input halt on its input?
is a standard part of the halting problem undecidability proofs
IT IS NOT A STANDARD PART OF THE ACTUAL HALTING PROBLEM ITSELF.

The halting problem itself
IS ONLY CONCERNED WITH DIVIDING INPUTS INTO HALTING AND NON HALTING.

Does the simulation of the input have to be stopped to prevent its
otherwise infinite execution?

Does divide inputs into halting and not-halting.

[olcott]

> Yes it is. Let's look at it:

>
> "Does the input halt on its input?"

> ^^^^^^^^^ ^^^^^^^^^
>
> "the input" = P
> "its input" = I
>
> This is in fact the halting question: does P halt on I: does P(I) halt.
> For any P, and I whatsoever.
>
> You will not get anyone to accept any question which is not obviously
> equivalent to the above.

>
>> The halting problem itself
>> IS ONLY CONCERNED WITH DIVIDING INPUTS INTO HALTING AND NON HALTING.
>

> The halting problem is concerned with producing an algorithm for
> dividing inputs into halting and non-halting.
>
> An "input" is a function and and input: P(I).
>
> An algorithm for dividing the inputs looks like a function Halts(P, I).
>
> A total function has to handle any <P, I> pair.
>
> The combination P = I = H_Hat is a valid <P, I> pair.
>
> "Does H_Hat(H_Hat) halt" is just a specialization of the question "Does
> P(I) halt" by substituting H_Hat for P and I.
>
> H_Hat is a real function that we can readily construct if we are given
> Halts(P, I).
>
> You cannot remove a demonstrably constructable function rom the <P, I>
> domain.

>>
>> Does the simulation of the input have to be stopped to prevent its
>> otherwise infinite execution?
>

> That is exactly the same question, unless "its" secretly equivocates
> between different objects.

No it is not because the question:

Does the input halt on its input?

Answers yes when:
(a) The simulation of the input has to be stopped to prevent its
otherwise infinite execution.

And also answers yes when:
(b) The simulation of the input terminates without having to be stopped.

This new question divides inputs into two distinct sets and the original
question does not.

The difference between the two questions is that the original question
has pathological self-reference(Olcott 2004) and the new question does not.

[olcott]

On 1/11/2021 5:10 PM, Richard Damon wrote:

> FALSE.
>
> Can you provide any reputable source that says that the Halting Problem
> of classical mathematics/Computer Science is based on anything other
> than what the machine, whose representation is provided as the input,
> would actually do?
>

Because H_Hat() meets the "Infinite Recursion detection" criteria it can
be verified that H_Hat() would actually never halt unless its simulation
is stopped.

Anyone understanding the meaning of the following words comprehends that
they are necessarily true:

Infinite Recursion detection AXIOM
(a) Within an execution trace
(b) The same function is called
(c) From the same machine address
(d) With the same data // Richard Damon credit
(e) A second time
(f) Without any control flow instructions inbetween

You already had a chance to find an error and you did find a gap. That
gap is now closed.

[olcott]

> Yes it is. Let's look at it:
>

> "Does the input halt on its input?"

> ^^^^^^^^^ ^^^^^^^^^
>
> "the input" = P
> "its input" = I
>
> This is in fact the halting question: does P halt on I: does P(I) halt.
> For any P, and I whatsoever.
>
> You will not get anyone to accept any question which is not obviously
> equivalent to the above.
>

>> The halting problem itself
>> IS ONLY CONCERNED WITH DIVIDING INPUTS INTO HALTING AND NON HALTING.
>

> The halting problem is concerned with producing an algorithm for
> dividing inputs into halting and non-halting.
>
> An "input" is a function and and input: P(I).
>
> An algorithm for dividing the inputs looks like a function Halts(P, I).
>
> A total function has to handle any <P, I> pair.
>
> The combination P = I = H_Hat is a valid <P, I> pair.
>
> "Does H_Hat(H_Hat) halt" is just a specialization of the question "Does
> P(I) halt" by substituting H_Hat for P and I.
>
> H_Hat is a real function that we can readily construct if we are given
> Halts(P, I).
>
> You cannot remove a demonstrably constructable function rom the <P, I>
> domain.
>>

>> Does the simulation of the input have to be stopped to prevent its
>> otherwise infinite execution?
>

> That is exactly the same question,

Make sure that you pay attention to these key details
Make sure that you pay attention to these key details
Make sure that you pay attention to these key details

Ignoring these details instead of critiquing them is dishonest
Ignoring these details instead of critiquing them is dishonest
Ignoring these details instead of critiquing them is dishonest

This question has pathological self-reference:

Does the input halt on its input?

and answers yes when:
(a) The simulation of the input has to be stopped to prevent its
otherwise infinite execution.

and also answers yes when:

(b) The simulation of the input terminates without having to be stopped.

Can you see that the original question conflates these two distinct sets
together into one set?
(a) Non-halting set
(b) Halting set

[olcott]

On 1/11/2021 6:36 PM, Kaz Kylheku wrote:
> On 2021-01-11, olcott <No...@NoWhere.com> wrote:

>> Anyone understanding the meaning of the following words comprehends that
>> they are necessarily true:
>>
>> Infinite Recursion detection AXIOM
>> (a) Within an execution trace
>> (b) The same function is called
>> (c) From the same machine address
>> (d) With the same data // Richard Damon credit
>> (e) A second time
>> (f) Without any control flow instructions inbetween
>

> Your program is not correctly checking these criteria, because
> they require the complete instructions stream.
>
> At every recursion level, it runs a simulation and that simulation
> consists of a loop wrapped around DebugStep. That loop necessarily
> contains of test and branch instructions.

When a judge decides whether or not a defendant is guilty the judge is a
separate and distinct entity from the defendant.

In this same way the halt decider and the simulator are separate and
distinct entities from the program under test.

[olcott]

On 1/10/2021 9:09 AM, Ben Bacarisse wrote:
> Richard Damon <Ric...@Damon-Family.org> writes:

>
>> On 1/10/21 12:12 AM, olcott wrote:
>>>
>>>
>>> It is only the wrong answer if we are asking the question:
>>> Does the input halt on its input?
>>>

>>> If we are asking the question:

>>> Does the simulation of the input have to be stopped to prevent its
>>> otherwise infinite execution?
>>>

>>> Then it is the right answer.
>>>
>>
>> At which point you need to admit that you aren't working on the
>> classical Hating Problem, which asks the first question, but some other
>> question, and thus your answer isn't applicable to proofs like Linz
>> which ARE based on the first question.
>
> Yes, except that the question "Does the simulation of the input have to
> be stopped to prevent its otherwise infinite execution" is, itself, the
> classical halting problem.

This is one of the very rare times that you have ever agreed with me on
a material fact.

The original halting problem undecidability proof question:

Does the input halt on its input?

conflates together non-halting inputs with halting inputs

and answers yes when:
(a) The simulation of the input has to be stopped to prevent its
otherwise infinite execution.

and also answers yes when:
(b) The simulation of the input terminates without having to be stopped.

[olcott]

On 1/12/2021 11:15 AM, Kaz Kylheku wrote:
> On 2021-01-12, olcott <No...@NoWhere.com> wrote:

>> On 1/9/2021 5:22 PM, Kaz Kylheku wrote:
>>> On 2021-01-09, olcott <No...@NoWhere.com> wrote:

>>>>> AXIOM means "please accept this without proof"; that doesn't fly.
>>>>>
>>>>
>>>> Another definition of the term "axiom" is "self-evident truth" which is
>>
>>> For instance, we can add at least three different axioms to four-axiom
>>> geometry to produce different geometries.
>>
>> That is the problem with the way that natural language assigns different
>> meanings to the same word. I am not referring to that meaning.
>
> That meaning is the only one we should be using in a newsgroup like
> comp.theory, if we're discussing anything topical.
>
> It appears as (1) in that same Merriam-Webster entry you cited,
> and you should not even be using that in the first place for formal
> terms, but a dictionary of mathematics or logic.
>
> I would myself never use "axiom" other than as the formal term in logic,
> in any context whatsoever. If I intended to say "self-evident", I would
> use "self-evident".
>

I don't think that the is any other commonly understood term that means:
[can very verified as completely true entirely based on its meaning]
besides axiom.

>>> If so, this is a simulated H_Hat, not a direct call from main to H_Hat.
>>> No such direct call is performed by the program.
>>>
>>> The simulated H_Hat is a different function from a top-level H_Hat.
>>>
>>> It is different because it is wrapped in one more level of simulation.
>>>
>>> Different levels of simulation are not equivalent in this execution model.
>>>
>>> Anyway, within every simulation level, that level's simulated Halts is
>>> wrong about that level's simulated H_Hat(H_Hat).
>>
>> You continue to make this utterly baseless claim.
>
> You are utterly lying. I wrote the above several days ago. Hours after
> that, I posted a self-follow-up in which I noted that it was mistaken,
> and corrected it. Here is a snippet from the follow-up:

I am not lying, although I admit that (especially in your case)** I may
have been mistaken. I generally totally ignore at least half of the
replies so that I can focus more time on the software development aspect
of this.

** You are one of the most honest reviewers.

> On 2021-01-09, Kaz Kylheku <563-36...@kylheku.com> wrote:

> >On 2021-01-09, Kaz Kylheku <563-36...@kylheku.com> wrote:
> >> On 2021-01-09, olcott <No...@NoWhere.com> wrote:

> >>> The stack push code preceding the call from H_Hat() to Halts() above
> >>> indicates that H_Hat() is calling Halts() with two copies of its own
> >>> input parameter [ebp+08].
> >>
> >> If so, this is a simulated H_Hat, not a direct call from main to H_Hat.
> >> No such direct call is performed by the program.
> >>
> >> The simulated H_Hat is a different function from a top-level H_Hat.
> >
> > Sorry, I spoke incorrectly here. Here is the right view.
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>
> It's now three days after both these articles. You've chosen to reply to first,
> specifically quoting text which I retracted and corrected in the second, and
> insisting that I'm continuing to make that claim.
>
> You are clearly unfit for civilized discussion.
>
> What I'm wrong about is that they are different functions; the correct view is
> that the nestings are in fact the same. Each one executes the same logic on the
> same inputs, which wants to terminate the recursion in three (or whatever
> number) of levels.
>
> So in fact at each simulation level H_Hat(H_Hat) is headed for termination;
> it's just that only the direct, top-level call to H_Hat(H_Hat) actually
> terminates. The simulated ones are aborted before reaching termination, because
> the most ancestral simulation level clips the number of recursion levels
> available to the nestings.
>

Summing this up in simpler terms the Halt decider stops simulating its
input at the very first point in the execution trace where it can
correctly decide that its input would not otherwise stop executing.

> You've already admitted that a H_Hat(H_Hat) in fact terminates, though
> you refuse to actually provide an execution trace which confirms it
> (probably due to understandable embarassement or whatever).
>

I have provided the full execution trace of all of the user code if the
invocation of:

void H_Hat(u32 P)

{
u32 Input_Halts = Halts(P, P);

if (Input_Halts)
HERE: goto HERE;
return;
}

int main()
{
u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);

Output("Input_Would_Halt =", Input_Would_Halt);
}

The key aspect of this that I have been showing for the longest time is
the sequence of the execution trace that proves that H_Hat() meets the
Infinite Recursion detection criteria:

Output_Debug_Trace() [0001112e] size(124) capacity(65536)
[0000087e](01) 55 push ebp
[0000087f](02) 8bec mov ebp,esp
[00000881](01) 51 push ecx
[00000882](05) 684e080000 push 0000084e
[00000887](05) 684e080000 push 0000084e
[0000088c](05) e8ddfdffff call 0000066e ; call Halts(H_Hat,H_Hat)
[0000084e](01) 55 push ebp
[0000084f](02) 8bec mov ebp,esp
[00000851](01) 51 push ecx
[00000852](03) 8b4508 mov eax,[ebp+08]
[00000855](01) 50 push eax
[00000856](03) 8b4d08 mov ecx,[ebp+08]
[00000859](01) 51 push ecx
[0000085a](05) e80ffeffff call 0000066e ; call Halts(H_Hat,H_Hat)
[0000084e](01) 55 push ebp
[0000084f](02) 8bec mov ebp,esp
[00000851](01) 51 push ecx
[00000852](03) 8b4508 mov eax,[ebp+08]
[00000855](01) 50 push eax
[00000856](03) 8b4d08 mov ecx,[ebp+08]
[00000859](01) 51 push ecx
[0000085a](05) e80ffeffff call 0000066e ; call Halts(H_Hat,H_Hat)

Infinite Recursion detection AXIOM
(a) Within an execution trace
(b) The same function is called
(c) From the same machine address
(d) With the same data // Richard Damon credit
(e) A second time
(f) Without any control flow instructions inbetween

It can be verified entirely on the basis of its meaning that all of the
above is necessarily true. That all of the above is necessarily true is
complete proof that Halts() does decide H_Hat() correctly.

Any disagreement that all of the above is necessarily true without
pointing out any specific error in any of the above will be construed as
dishonesty. What I mean by dishonesty is the intentional divergence away
from an honest dialogue.

[olcott]

On 1/14/2021 7:34 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 1/13/2021 10:03 PM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> On 1/13/2021 6:05 PM, Ben Bacarisse wrote:
>>>>> olcott <No...@NoWhere.com> writes:
>>>>>
>>>>>> On 1/13/2021 8:47 AM, Ben Bacarisse wrote:
>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>
>>>>>>>> On 1/12/2021 8:30 PM, Richard Damon wrote:
>>>>>>>>> On 1/12/21 7:10 PM, olcott wrote:
>>>>>>>>>>>
>>>>>>>>>> The same halt decider can have different behavior on the same input:
>>>>>>>>>> Turing Machine description when halt deciding mode {enabled, disabled}
>>>>>>>>>> is an additional input.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> But the H in the halting problem doesn't have this extra input, so for
>>>>>>>>> Linz and such it can't really be there, for that purpose you need to
>>>>>>>>> wrap your decider with that extra input with a wrapper that always sets
>>>>>>>>> it the same way.
>>>>>>>>>
>>>>>>>>
>>>>>>>> Since Linz defines the halt deciding states with the ⊢* [do any damn
>>>>>>>> thing you] want operator we are free to [do any damn thing we want].
>>>>>>
>>>>>> In Linz terms it specifies an arbitrary set of moves from one
>>>>>> configuration to another, thus the specified algorithm is simply [do
>>>>>> any damn thing you want] (as long as you end up at YES or NO).
>>>>>
>>>>> Still wrong.
>>>
>>>> Any configuration is completely determined by the current state of the
>>>> control unit, the contents of the tape, and the position of the
>>>> read-write head (Linz 1990:236)
>>>>
>>>> The symbols ⊢* and ⊢+ have the usual meaning of an arbitrary number of
>>>> moves (Linz 1990:237)
>>>>
>>>> Therefore H begins at a start state (q0) and ends up at one of two
>>>> final states (qy) or (qn) and can [do any damn thing inbetween] as
>>>> long as it ends up deciding halting on its input.
>>>
>>> It can not, however, do this:
>>>
>>> | The same halt decider can have different behavior on the same input:
>>> | Turing Machine description when halt deciding mode {enabled, disabled}
>>> | is an additional input.
>>
>> The Linz H would simply be Halts() in global mode.
>
> Then you don't need any of the others. The others are there for you to
> pull of your huckster trick.

OK then.
Halts() simply returns its result to the command line and then halts.

void H_Hat(u32 P)
{
u32 Input_Halts = Halts(P, P);
if (Input_Halts)
HERE: goto HERE;
return;
}

int main()
{

Halts((u32)H_Hat, (u32)H_Hat);
}

_H_Hat()
[00000879](01) 55 push ebp
[0000087a](02) 8bec mov ebp,esp
[0000087c](01) 51 push ecx
[0000087d](03) 8b4508 mov eax,[ebp+08]
[00000880](01) 50 push eax
[00000881](03) 8b4d08 mov ecx,[ebp+08]
[00000884](01) 51 push ecx
[00000885](05) e8fffdffff call 00000689
[0000088a](03) 83c408 add esp,+08
[0000088d](03) 8945fc mov [ebp-04],eax
[00000890](04) 837dfc00 cmp dword [ebp-04],+00
[00000894](02) 7402 jz 00000898
[00000896](02) ebfe jmp 00000896
[00000898](02) 8be5 mov esp,ebp
[0000089a](01) 5d pop ebp
[0000089b](01) c3 ret

_main()
[000008a9](01) 55 push ebp
[000008aa](02) 8bec mov ebp,esp
[000008ac](05) 6879080000 push 00000879
[000008b1](05) 6879080000 push 00000879
[000008b6](05) e8cefdffff call 00000689 ; Call Halts(H_Hat,H_Hat)
[000008bb](03) 83c408 add esp,+08
[000008be](02) 33c0 xor eax,eax
[000008c0](01) 5d pop ebp
[000008c1](01) c3 ret


Output_Debug_Trace() Trace_List.size(20)
---[000008a9](01) 55 push ebp
---[000008aa](02) 8bec mov ebp,esp
---[000008ac](05) 6879080000 push 00000879
---[000008b1](05) 6879080000 push 00000879
---[000008b6](05) e8cefdffff call 00000689 ; Call
Halts(H_Hat,H_Hat)
---[00000879](01) 55 push ebp
---[0000087a](02) 8bec mov ebp,esp
---[0000087c](01) 51 push ecx
---[0000087d](03) 8b4508 mov eax,[ebp+08]
---[00000880](01) 50 push eax
---[00000881](03) 8b4d08 mov ecx,[ebp+08]
---[00000884](01) 51 push ecx
---[00000885](05) e8fffdffff call 00000689 ; Call
Halts(H_Hat,H_Hat)
---[00000879](01) 55 push ebp
---[0000087a](02) 8bec mov ebp,esp
---[0000087c](01) 51 push ecx
---[0000087d](03) 8b4508 mov eax,[ebp+08]
---[00000880](01) 50 push eax
---[00000881](03) 8b4d08 mov ecx,[ebp+08]
---[00000884](01) 51 push ecx
---[00000885](05) e8fffdffff call 00000689 --CALL [00000689]
The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:

The fact that the above execution trace matches the [Infinite Recursion
detection criteria] combined with the fact that this criteria can be
verified as [self-evidently true] (verified as totally true entirely
based on its meaning_ proves that Halts() does correctly decide H_Hat().

Infinite Recursion detection criteria (self-evident truth)

(a) Within an execution trace
(b) The same function is called
(c) From the same machine address
(d) With the same data // Richard Damon credit
(e) A second time
(f) Without any control flow instructions inbetween