Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.software-eng > #1793 > unrolled thread

It is known that a correct halt decider must return false (in this case)[V2]

Started byolcott <NoOne@NoWhere.com>
First post2020-11-21 13:19 -0600
Last post2020-11-22 13:14 -0600
Articles 20 on this page of 58 — 3 participants

Back to article view | Back to comp.software-eng


Contents

  It is known that a correct halt decider must return false (in this case)[V2] olcott <NoOne@NoWhere.com> - 2020-11-21 13:19 -0600
    Re: It is known that a correct halt decider must return false (in this case)[V2] olcott <NoOne@NoWhere.com> - 2020-11-21 15:35 -0600
    Re: It is known that a correct halt decider must return false (in this case)[V2] olcott <NoOne@NoWhere.com> - 2020-11-22 08:17 -0600
      Re: It is known that a correct halt decider must return false (in this case)[V2](behind its back) olcott <NoOne@NoWhere.com> - 2020-11-22 10:16 -0600
        Re: It is known that a correct halt decider must return false (in this case)[V2](false assumptions are not a rebuttal) olcott <NoOne@NoWhere.com> - 2020-11-22 12:28 -0600
          Re: It is known that a correct halt decider must return false (in this case)[V2](false assumptions are not a rebuttal) olcott <NoOne@NoWhere.com> - 2020-11-22 12:56 -0600
            Re: It is known that a correct halt decider must return false (in this case)[V2](false assumptions are not a rebuttal) olcott <NoOne@NoWhere.com> - 2020-11-22 13:28 -0600
              Re: It is known that a correct halt decider must return false (in this case)[V2](false assumptions are not a rebuttal) olcott <NoOne@NoWhere.com> - 2020-11-22 16:25 -0600
                Re: It is known that a correct halt decider must return false (in this case)[V2](actual execution trace) olcott <NoOne@NoWhere.com> - 2020-11-22 17:35 -0600
                  Re: It is known that a correct halt decider must return false (in this case)[V2](actual execution trace) olcott <NoOne@NoWhere.com> - 2020-11-23 07:09 -0600
                    Re: It is known that a correct halt decider must return false (in this case)[V2](obvious facts) olcott <NoOne@NoWhere.com> - 2020-11-23 07:55 -0600
                    Re: It is known that a correct halt decider must return false (in this case)[V2](obvious facts) olcott <NoOne@NoWhere.com> - 2020-11-23 08:50 -0600
                      Re: It is known that a correct halt decider must return false (in this case)[V2](obvious facts) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-23 17:33 +0000
                    Re: It is known that a correct halt decider must return false (in this case)[V2](actual execution trace) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-23 17:14 +0000
                      Re: It is known that a correct halt decider must return false (in this case)[V2](actual execution trace) olcott <NoOne@NoWhere.com> - 2020-11-23 12:08 -0600
          Re: It is known that a correct halt decider must return false (in this case)[V2](false assumptions are not a rebuttal) olcott <NoOne@NoWhere.com> - 2020-11-22 13:04 -0600
            Re: It is known that a correct halt decider must return false (in this case)[V2](false assumptions are not a rebuttal) olcott <NoOne@NoWhere.com> - 2020-11-23 07:08 -0600
              Re: It is known that a correct halt decider must return false (in this case)[V2](obvious facts) olcott <NoOne@NoWhere.com> - 2020-11-23 09:49 -0600
                Re: It is known that a correct halt decider must return false (in this case)[V2](obvious facts) olcott <NoOne@NoWhere.com> - 2020-11-23 21:30 -0600
                  Re: It is known that a correct halt decider must return false (in this case)[V2](obvious facts) olcott <NoOne@NoWhere.com> - 2020-11-24 09:47 -0600
                    Re: It is known that a correct halt decider must return false (in this case)[V2](obvious facts) olcott <NoOne@NoWhere.com> - 2020-11-24 21:06 -0600
                      Re: It is known that a correct halt decider must return false (in this case)[V2](no difference) olcott <NoOne@NoWhere.com> - 2020-11-24 21:58 -0600
                        Re: It is known that a correct halt decider must return false (in this case)[V2](no difference) olcott <NoOne@NoWhere.com> - 2020-11-24 23:05 -0600
                          Re: It is known that a correct halt decider must return false (in this case)[V2](no difference) olcott <NoOne@NoWhere.com> - 2020-11-25 08:02 -0600
                            Re: It is known that a correct halt decider must return false (in this case)[V2](no difference) olcott <NoOne@NoWhere.com> - 2020-11-25 09:19 -0600
                              Re: It is known that a correct halt decider must return false (in this case)[V2](no difference) olcott <NoOne@NoWhere.com> - 2020-11-25 11:37 -0600
                                Re: It is known that a correct halt decider must return false (in this case)[V2](no difference) olcott <NoOne@NoWhere.com> - 2020-11-25 12:13 -0600
                                  Re: It is known that a correct halt decider must return false (in this case)[V2](no difference) olcott <NoOne@NoWhere.com> - 2020-11-25 13:33 -0600
                                    Re: It is known that a correct halt decider must return false (in this case)[V2](no difference) olcott <NoOne@NoWhere.com> - 2020-11-25 14:16 -0600
                                      Re: It is known that a correct halt decider must return false (in this case)[V2](no difference) olcott <NoOne@NoWhere.com> - 2020-11-25 17:18 -0600
                                Re: It is known that a correct halt decider must return false (in this case)[V2](no difference) olcott <NoOne@NoWhere.com> - 2020-11-25 18:49 -0600
                                  Re: It is known that a correct halt decider must return false (in this case)[V2](no difference) olcott <NoOne@NoWhere.com> - 2020-11-25 20:43 -0600
                                    Re: It is known that a correct halt decider must return false (in this case)[V2](no difference) olcott <NoOne@NoWhere.com> - 2020-11-25 22:30 -0600
                                      Re: It is known that a correct halt decider must return false (in this case)[V2](ridiculous) olcott <NoOne@NoWhere.com> - 2020-11-26 08:33 -0600
                                        Re: It is known that a correct halt decider must return false (in this case)[V2](ridiculous) olcott <NoOne@NoWhere.com> - 2020-11-26 09:49 -0600
                                          Re: It is known that a correct halt decider must return false (in this case)[V2](whole solution) olcott <NoOne@NoWhere.com> - 2020-11-26 11:50 -0600
                                            Re: It is known that a correct halt decider must return false (in this case)[V2](whole solution) olcott <NoOne@NoWhere.com> - 2020-11-26 12:41 -0600
                                              Re: It is known that a correct halt decider must return false (in this case)[V2](whole solution) olcott <NoOne@NoWhere.com> - 2020-11-26 13:07 -0600
                                                Re: It is known that a correct halt decider must return false (in this case)[V2](whole solution) olcott <NoOne@NoWhere.com> - 2020-11-26 15:12 -0600
                                                  Re: It is known that a correct halt decider must return false (in this case)[V2](whole solution) olcott <NoOne@NoWhere.com> - 2020-11-26 15:56 -0600
                                                    Re: It is known that a correct halt decider must return false (in this case)[V2](whole solution) olcott <NoOne@NoWhere.com> - 2020-11-26 16:20 -0600
                                                      Re: It is known that a correct halt decider must return false (in this case)[V2](whole solution) olcott <NoOne@NoWhere.com> - 2020-11-26 18:25 -0600
                                                  Re: It is known that a correct halt decider must return false (in this case)[V2](whole solution) olcott <NoOne@NoWhere.com> - 2020-11-26 16:34 -0600
                                                    Re: It is known that a correct halt decider must return false (in this case)[V2](whole solution) olcott <NoOne@NoWhere.com> - 2020-11-26 18:10 -0600
                                            Re: It is known that a correct halt decider must return false (in this case)[V2](whole solution) olcott <NoOne@NoWhere.com> - 2020-11-26 17:41 -0600
                                              Re: It is known that a correct halt decider must return false (in this case)[V2](Ben disagrees with himself) olcott <NoOne@NoWhere.com> - 2020-11-26 20:45 -0600
                                                Re: It is known that a correct halt decider must return false (in this case)[V2](Ben disagrees with himself [verified]) olcott <NoOne@NoWhere.com> - 2020-11-27 12:14 -0600
                                          Re: It is known that a correct halt decider must return false (in this case)[V2](whole solution) olcott <NoOne@NoWhere.com> - 2020-11-26 11:58 -0600
                                    Re: It is known that a correct halt decider must return false (in this case)[V2](facts v falsehood) olcott <NoOne@NoWhere.com> - 2020-11-26 08:26 -0600
                                Re: It is known that a correct halt decider must return false (in this case)[V2](no difference) olcott <NoOne@NoWhere.com> - 2020-11-25 19:10 -0600
                        Re: It is known that a correct halt decider must return false (in this case)[V2](no difference) olcott <NoOne@NoWhere.com> - 2020-11-25 10:44 -0600
                          Re: It is known that a correct halt decider must return false (in this case)[V2](no difference) olcott <NoOne@NoWhere.com> - 2020-11-25 13:24 -0600
                            Re: It is known that a correct halt decider must return false (in this case)[V2](no difference) olcott <NoOne@NoWhere.com> - 2020-11-25 14:09 -0600
                              Re: It is known that a correct halt decider must return false (in this case)[V2](no difference) Jeff Barnett <jbb@notatt.com> - 2020-11-25 14:30 -0700
                              Re: It is known that a correct halt decider must return false (in this case)[V2](no difference) olcott <NoOne@NoWhere.com> - 2020-11-25 21:03 -0600
                      Re: It is known that a correct halt decider must return false (in this case)[V2](obvious facts) olcott <NoOne@NoWhere.com> - 2020-11-25 16:07 -0600
              Re: It is known that a correct halt decider must return false (in this case)[V2](false assumptions are not a rebuttal) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-23 17:34 +0000
        Re: It is known that a correct halt decider must return false (in this case)[V2](black cats are black) olcott <NoOne@NoWhere.com> - 2020-11-22 13:14 -0600

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →


#1852 — Re: It is known that a correct halt decider must return false (in this case)[V2](obvious facts)

Fromolcott <NoOne@NoWhere.com>
Date2020-11-24 21:06 -0600
SubjectRe: It is known that a correct halt decider must return false (in this case)[V2](obvious facts)
Message-ID<mJqdnZk8VbPQVyDCnZ2dnUU7-VPNnZ2d@giganews.com>
In reply to#1838
On 11/24/2020 8:49 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> 
>> On 11/24/2020 9:22 AM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 11/23/2020 8:26 PM, Ben Bacarisse wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> The point is that H(Ĥ, Ĥ) ⊢* H.no is correct.
>>>>>>
>>>>>>        H.q0 wMw ⊢* H.yes   if M applied to w halts, and
>>>>>>        H.q0 wMw ⊢* H.no    if M applied to w does not halt.
>>>>>>        (Linz 1990:318)
>>>>>
>>>>> Good grief, you are using the notation almost correctly!  But you open
>>>>> with a falsehood.  H.q0 wĤ wĤ ⊢* H.no is /not/ correct as Linz explains.
>>>>> Basically, Ĥ is constructed so that
>>>>>
>>>>>      Ĥ.q0 wĤ ⊢* H.q0 wĤ wĤ ⊢* H.no
>>>>
>>>> Ĥ does not copy its input.
>>>
>>> Yes it does.  You cited the book that tell you it does.  If you don't
>>> accept the "hat" construction from Linz, you have nothing more to say
>>> about the proof.
>>
>> As I have told you hundreds of times I simplify the counter-example to
>> make it conform to the general counter-example that does not copy its
>> input.
> 
> You cited Linz and gave the desired behaviour of H exactly as Linz does.
> Linz says of Ĥ "This new machine takes its input wM and copies it".  I
> wrote exactly what Linz writes using the slightly different notation you
> have adopted:
> 
>    Ĥ.q0 wM ⊢* H.q0 wM wM ⊢* H.no
> 
> To keep denying that Ĥ copies its input is just silly.  Just admit it
> and move.  We can then talk about your x86 code, and why that's wrong.

To say that this code copies itself is dishonest:

void H_Hat(u32 P)
{
   u32 Aborted = DebugTrace(P, P);
   if (Aborted)
     HALT
   else
     HERE: goto HERE;
}


>>> Does this, in fact, mean you accept the proof as
>>> presented by Linz about actual Turing machines -- the one where Ĥ /does/
>>> copy its input?
>>
>> No it does not.  It is quite crazy that you say this
> 
> Take a deep breath.  What is the usual end result when you have had to
> resort to thinking I'm saying crazy things?  I am usually right, aren't
> I?

I have already shown how the Linz equivalent code above has been 
correctly decided.

>> when I have shown you the actual execution trace of a concrete example
>> of an equivalent H_Hat...
> 
> H_Hat is not Ĥ.  Ĥ is a Turing machine which can be run with a tape
> containing the encoding of Ĥ.  What matters for this post is the
> execution trace of the Turing machine Ĥ, not the execution trace of your
> x86 code.  The TM execution trace is written like this:

No that does not matter. What does matter is that my H_Hat is 
computationally equivalent to the Linz Ĥ. It has the exact same relation 
between Halts and H_Hat as H has to Ĥ. That was the only required element.

You have already agreed that computational equivalence is good enough 
and now you try to back out of this agreement (as I always expected).

>    Ĥ.q0 <M> ⊢* H.q0 <M><M>
> 
> and in the key case where the tape string is <Ĥ>, the full trace is
> 
>    Ĥ.q0 <Ĥ> ⊢* H.q0 <Ĥ><Ĥ> ⊢* H.no  iff H(<Ĥ>) is not a finite computation
> 
> which is obviously absurd.  The other possibility is that the trace is
> 
>    Ĥ.q0 <Ĥ> ⊢* H.q0 <Ĥ><Ĥ> ⊢* H.yes ⊢* ∞  iff H(<Ĥ>) is a finite computation
> 
> which is equally absurd.
> 
>>> ...  (Your x86 H_Hat does in fact copy the input.
>>
>> That is such a horrifically stupid thing to say when I provide that
>> actual source code for H_Hat that does not copy its input:
> 
> I can explain this more subtle point later on, but if you continue to
> deny that the TM Ĥ copies its input there is no point.  Let's see if we
> can't clear up that much simpler matter first.
> 



-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#1857 — Re: It is known that a correct halt decider must return false (in this case)[V2](no difference)

Fromolcott <NoOne@NoWhere.com>
Date2020-11-24 21:58 -0600
SubjectRe: It is known that a correct halt decider must return false (in this case)[V2](no difference)
Message-ID<da2dnQicD-v9SyDCnZ2dnUU7-LfNnZ2d@giganews.com>
In reply to#1852
On 11/24/2020 9:45 PM, Richard Damon wrote:
> On 11/24/20 10:06 PM, olcott wrote:
>> On 11/24/2020 8:49 PM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 11/24/2020 9:22 AM, Ben Bacarisse wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> On 11/23/2020 8:26 PM, Ben Bacarisse wrote:
>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>
>>>>>>>> The point is that H(Ĥ, Ĥ) ⊢* H.no is correct.
>>>>>>>>
>>>>>>>>         H.q0 wMw ⊢* H.yes   if M applied to w halts, and
>>>>>>>>         H.q0 wMw ⊢* H.no    if M applied to w does not halt.
>>>>>>>>         (Linz 1990:318)
>>>>>>>
>>>>>>> Good grief, you are using the notation almost correctly!  But you
>>>>>>> open
>>>>>>> with a falsehood.  H.q0 wĤ wĤ ⊢* H.no is /not/ correct as Linz
>>>>>>> explains.
>>>>>>> Basically, Ĥ is constructed so that
>>>>>>>
>>>>>>>       Ĥ.q0 wĤ ⊢* H.q0 wĤ wĤ ⊢* H.no
>>>>>>
>>>>>> Ĥ does not copy its input.
>>>>>
>>>>> Yes it does.  You cited the book that tell you it does.  If you don't
>>>>> accept the "hat" construction from Linz, you have nothing more to say
>>>>> about the proof.
>>>>
>>>> As I have told you hundreds of times I simplify the counter-example to
>>>> make it conform to the general counter-example that does not copy its
>>>> input.
>>>
>>> You cited Linz and gave the desired behaviour of H exactly as Linz does.
>>> Linz says of Ĥ "This new machine takes its input wM and copies it".  I
>>> wrote exactly what Linz writes using the slightly different notation you
>>> have adopted:
>>>
>>>     Ĥ.q0 wM ⊢* H.q0 wM wM ⊢* H.no
>>>
>>> To keep denying that Ĥ copies its input is just silly.  Just admit it
>>> and move.  We can then talk about your x86 code, and why that's wrong.
>>
>> To say that this code copies itself is dishonest:
>>
>> void H_Hat(u32 P)
>> {
>>    u32 Aborted = DebugTrace(P, P);
>>    if (Aborted)
>>      HALT
>>    else
>>      HERE: goto HERE;
>> }
>>
> 
> I see 1 P becoming 2 Ps, and a violation of the design if DebugTrace,
> via the program P it is emulating, happens to change its tape. Note that
> at this level of defintion, P does NOT yet need to be a representation
> of H_Hat, so it is possible to come up with a machine that this will
> process in a none equivalent matter to the Turing Machine Version, thus
> it is NOT the equivalent calculation.
> 
>>
>>>>> Does this, in fact, mean you accept the proof as
>>>>> presented by Linz about actual Turing machines -- the one where Ĥ
>>>>> /does/
>>>>> copy its input?
>>>>
>>>> No it does not.  It is quite crazy that you say this
>>>
>>> Take a deep breath.  What is the usual end result when you have had to
>>> resort to thinking I'm saying crazy things?  I am usually right, aren't
>>> I?
>>
>> I have already shown how the Linz equivalent code above has been
>> correctly decided.
> 
> Only in your own mind.
>>
>>>> when I have shown you the actual execution trace of a concrete example
>>>> of an equivalent H_Hat...
>>>
>>> H_Hat is not Ĥ.  Ĥ is a Turing machine which can be run with a tape
>>> containing the encoding of Ĥ.  What matters for this post is the
>>> execution trace of the Turing machine Ĥ, not the execution trace of your
>>> x86 code.  The TM execution trace is written like this:
>>
>> No that does not matter. What does matter is that my H_Hat is
>> computationally equivalent to the Linz Ĥ. It has the exact same relation
>> between Halts and H_Hat as H has to Ĥ. That was the only required element.
> 
> As pointed above, it isn't, if Program P changes its tape, the execution
> equivalence is broken.
> 
>>
>> You have already agreed that computational equivalence is good enough
>> and now you try to back out of this agreement (as I always expected).
>>
> 
> I don't think anyone has complained about this optimization. What they
> HAVE complained about is that in if we want to make a change to the top
> level code to test a 'needed' clause, you won't allow the tape to remain
> per the original definition, even if at the top level we have a
> different H_Hat or Halt Decider, but that is a DIFFERENT issue.
> 

Only Mike has the capacity to understand this key aspect and he has not 
yet provided me any feedback of my rebuttal of this.

At least he explained why this sort of change is thought to be required. 
Everyone else was incapable of providing any reasoning for their 
requirement merely dogmatic assertions entirely bereft of any reasoning.

It is an actual verifiable fact that the execution of H_Hat under a 
simulator and the execution of H_Hat under a halt decider is perfectly 
identical from H_Hat's point of view, thus not at all two different 
computations as Mike has indicated.

H_Hat does not decide to change its behavior between its simulation 
under a UTM and its simulation under a halt decider because H_Hat is 
utterly unaware of any difference.





-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#1861 — Re: It is known that a correct halt decider must return false (in this case)[V2](no difference)

Fromolcott <NoOne@NoWhere.com>
Date2020-11-24 23:05 -0600
SubjectRe: It is known that a correct halt decider must return false (in this case)[V2](no difference)
Message-ID<pfqdnW1eyOOveyDCnZ2dnUU7-X_NnZ2d@giganews.com>
In reply to#1857
On 11/24/2020 10:46 PM, Richard Damon wrote:
> On 11/24/20 10:58 PM, olcott wrote:
>> On 11/24/2020 9:45 PM, Richard Damon wrote:
>>> On 11/24/20 10:06 PM, olcott wrote:
>>>> On 11/24/2020 8:49 PM, Ben Bacarisse wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> On 11/24/2020 9:22 AM, Ben Bacarisse wrote:
>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>
>>>>>>>> On 11/23/2020 8:26 PM, Ben Bacarisse wrote:
>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>
>>>>>>>>>> The point is that H(Ĥ, Ĥ) ⊢* H.no is correct.
>>>>>>>>>>
>>>>>>>>>>          H.q0 wMw ⊢* H.yes   if M applied to w halts, and
>>>>>>>>>>          H.q0 wMw ⊢* H.no    if M applied to w does not halt.
>>>>>>>>>>          (Linz 1990:318)
>>>>>>>>>
>>>>>>>>> Good grief, you are using the notation almost correctly!  But you
>>>>>>>>> open
>>>>>>>>> with a falsehood.  H.q0 wĤ wĤ ⊢* H.no is /not/ correct as Linz
>>>>>>>>> explains.
>>>>>>>>> Basically, Ĥ is constructed so that
>>>>>>>>>
>>>>>>>>>        Ĥ.q0 wĤ ⊢* H.q0 wĤ wĤ ⊢* H.no
>>>>>>>>
>>>>>>>> Ĥ does not copy its input.
>>>>>>>
>>>>>>> Yes it does.  You cited the book that tell you it does.  If you don't
>>>>>>> accept the "hat" construction from Linz, you have nothing more to say
>>>>>>> about the proof.
>>>>>>
>>>>>> As I have told you hundreds of times I simplify the counter-example to
>>>>>> make it conform to the general counter-example that does not copy its
>>>>>> input.
>>>>>
>>>>> You cited Linz and gave the desired behaviour of H exactly as Linz
>>>>> does.
>>>>> Linz says of Ĥ "This new machine takes its input wM and copies it".  I
>>>>> wrote exactly what Linz writes using the slightly different notation
>>>>> you
>>>>> have adopted:
>>>>>
>>>>>      Ĥ.q0 wM ⊢* H.q0 wM wM ⊢* H.no
>>>>>
>>>>> To keep denying that Ĥ copies its input is just silly.  Just admit it
>>>>> and move.  We can then talk about your x86 code, and why that's wrong.
>>>>
>>>> To say that this code copies itself is dishonest:
>>>>
>>>> void H_Hat(u32 P)
>>>> {
>>>>     u32 Aborted = DebugTrace(P, P);
>>>>     if (Aborted)
>>>>       HALT
>>>>     else
>>>>       HERE: goto HERE;
>>>> }
>>>>
>>>
>>> I see 1 P becoming 2 Ps, and a violation of the design if DebugTrace,
>>> via the program P it is emulating, happens to change its tape. Note that
>>> at this level of defintion, P does NOT yet need to be a representation
>>> of H_Hat, so it is possible to come up with a machine that this will
>>> process in a none equivalent matter to the Turing Machine Version, thus
>>> it is NOT the equivalent calculation.
>>>
>>>>
>>>>>>> Does this, in fact, mean you accept the proof as
>>>>>>> presented by Linz about actual Turing machines -- the one where Ĥ
>>>>>>> /does/
>>>>>>> copy its input?
>>>>>>
>>>>>> No it does not.  It is quite crazy that you say this
>>>>>
>>>>> Take a deep breath.  What is the usual end result when you have had to
>>>>> resort to thinking I'm saying crazy things?  I am usually right, aren't
>>>>> I?
>>>>
>>>> I have already shown how the Linz equivalent code above has been
>>>> correctly decided.
>>>
>>> Only in your own mind.
>>>>
>>>>>> when I have shown you the actual execution trace of a concrete example
>>>>>> of an equivalent H_Hat...
>>>>>
>>>>> H_Hat is not Ĥ.  Ĥ is a Turing machine which can be run with a tape
>>>>> containing the encoding of Ĥ.  What matters for this post is the
>>>>> execution trace of the Turing machine Ĥ, not the execution trace of
>>>>> your
>>>>> x86 code.  The TM execution trace is written like this:
>>>>
>>>> No that does not matter. What does matter is that my H_Hat is
>>>> computationally equivalent to the Linz Ĥ. It has the exact same relation
>>>> between Halts and H_Hat as H has to Ĥ. That was the only required
>>>> element.
>>>
>>> As pointed above, it isn't, if Program P changes its tape, the execution
>>> equivalence is broken.
>>>
>>>>
>>>> You have already agreed that computational equivalence is good enough
>>>> and now you try to back out of this agreement (as I always expected).
>>>>
>>>
>>> I don't think anyone has complained about this optimization. What they
>>> HAVE complained about is that in if we want to make a change to the top
>>> level code to test a 'needed' clause, you won't allow the tape to remain
>>> per the original definition, even if at the top level we have a
>>> different H_Hat or Halt Decider, but that is a DIFFERENT issue.
>>>
>>
>> Only Mike has the capacity to understand this key aspect and he has not
>> yet provided me any feedback of my rebuttal of this.
>>
>> At least he explained why this sort of change is thought to be required.
>> Everyone else was incapable of providing any reasoning for their
>> requirement merely dogmatic assertions entirely bereft of any reasoning.
>>
>> It is an actual verifiable fact that the execution of H_Hat under a
>> simulator and the execution of H_Hat under a halt decider is perfectly
>> identical from H_Hat's point of view, thus not at all two different
>> computations as Mike has indicated.
>>
>> H_Hat does not decide to change its behavior between its simulation
>> under a UTM and its simulation under a halt decider because H_Hat is
>> utterly unaware of any difference.
>>
> 
> There is a VERY big difference between the execution trace of H_Hat
> using 'just' a UTM and H_Hat using a Halt Decider.
> 
> The H_Hat(H_Hat) running with a UTM will never get control back from the
> UTM, this is clear from the infinite recursion.
> 
> The H_Hat(H_Hat) running with a Halt Decider MUST get control back from
> the Halt Decider, as that is a required aspect of a Halt Decider. This
> means that the Halt Decider will need to add code beyond just a simple
> UTM to catch non-halting behavior in the program under test and resolve
> this sort of recursive request.
> 
> These are VERY distinct computations.

Not from the perspective of H_Hat. H_hat is unable to distinguish the 
difference thus it cannot execute its own code differently at all.

> As to why we need the ability to switch between UTM mode and Halt
> Detecting mode, let us first assume that we can add a 3rd parameter to
> Debug Step, if this parameter is 0, it will act as a UTM and not stop
> the code, if this parameter is a 1, it will enable the Halt Decider.

it is simpler to just make this a command line parameter to the x86utm 
operating system.

> We define our program under test to be the standard Linz H_Hat.
> 
> So
> 
> void H_Hat(P)
> {

This is cheating.
>      u32 aborted = Debug_Step(P, P, 1);
>      if(aborted)
>        HALT;
>      else
>        HERE: goto HERE;
> }
> 

No one can possibly justify why your cheat is needed.


-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#1864 — Re: It is known that a correct halt decider must return false (in this case)[V2](no difference)

Fromolcott <NoOne@NoWhere.com>
Date2020-11-25 08:02 -0600
SubjectRe: It is known that a correct halt decider must return false (in this case)[V2](no difference)
Message-ID<JOKdnVl38MZJ_iPCnZ2dnUU7-fvNnZ2d@giganews.com>
In reply to#1861
On 11/25/2020 6:17 AM, Richard Damon wrote:
> On 11/25/20 12:05 AM, olcott wrote:
>> On 11/24/2020 10:46 PM, Richard Damon wrote:
>>> On 11/24/20 10:58 PM, olcott wrote:
>>>> On 11/24/2020 9:45 PM, Richard Damon wrote:
>>>>> On 11/24/20 10:06 PM, olcott wrote:
>>>>>> On 11/24/2020 8:49 PM, Ben Bacarisse wrote:
>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>
>>>>>>>> On 11/24/2020 9:22 AM, Ben Bacarisse wrote:
>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>
>>>>>>>>>> On 11/23/2020 8:26 PM, Ben Bacarisse wrote:
>>>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>>>
>>>>>>>>>>>> The point is that H(Ĥ, Ĥ) ⊢* H.no is correct.
>>>>>>>>>>>>
>>>>>>>>>>>>           H.q0 wMw ⊢* H.yes   if M applied to w halts, and
>>>>>>>>>>>>           H.q0 wMw ⊢* H.no    if M applied to w does not halt.
>>>>>>>>>>>>           (Linz 1990:318)
>>>>>>>>>>>
>>>>>>>>>>> Good grief, you are using the notation almost correctly!  But you
>>>>>>>>>>> open
>>>>>>>>>>> with a falsehood.  H.q0 wĤ wĤ ⊢* H.no is /not/ correct as Linz
>>>>>>>>>>> explains.
>>>>>>>>>>> Basically, Ĥ is constructed so that
>>>>>>>>>>>
>>>>>>>>>>>         Ĥ.q0 wĤ ⊢* H.q0 wĤ wĤ ⊢* H.no
>>>>>>>>>>
>>>>>>>>>> Ĥ does not copy its input.
>>>>>>>>>
>>>>>>>>> Yes it does.  You cited the book that tell you it does.  If you
>>>>>>>>> don't
>>>>>>>>> accept the "hat" construction from Linz, you have nothing more
>>>>>>>>> to say
>>>>>>>>> about the proof.
>>>>>>>>
>>>>>>>> As I have told you hundreds of times I simplify the
>>>>>>>> counter-example to
>>>>>>>> make it conform to the general counter-example that does not copy
>>>>>>>> its
>>>>>>>> input.
>>>>>>>
>>>>>>> You cited Linz and gave the desired behaviour of H exactly as Linz
>>>>>>> does.
>>>>>>> Linz says of Ĥ "This new machine takes its input wM and copies
>>>>>>> it".  I
>>>>>>> wrote exactly what Linz writes using the slightly different notation
>>>>>>> you
>>>>>>> have adopted:
>>>>>>>
>>>>>>>       Ĥ.q0 wM ⊢* H.q0 wM wM ⊢* H.no
>>>>>>>
>>>>>>> To keep denying that Ĥ copies its input is just silly.  Just admit it
>>>>>>> and move.  We can then talk about your x86 code, and why that's
>>>>>>> wrong.
>>>>>>
>>>>>> To say that this code copies itself is dishonest:
>>>>>>
>>>>>> void H_Hat(u32 P)
>>>>>> {
>>>>>>      u32 Aborted = DebugTrace(P, P);
>>>>>>      if (Aborted)
>>>>>>        HALT
>>>>>>      else
>>>>>>        HERE: goto HERE;
>>>>>> }
>>>>>>
>>>>>
>>>>> I see 1 P becoming 2 Ps, and a violation of the design if DebugTrace,
>>>>> via the program P it is emulating, happens to change its tape. Note
>>>>> that
>>>>> at this level of defintion, P does NOT yet need to be a representation
>>>>> of H_Hat, so it is possible to come up with a machine that this will
>>>>> process in a none equivalent matter to the Turing Machine Version, thus
>>>>> it is NOT the equivalent calculation.
>>>>>
>>>>>>
>>>>>>>>> Does this, in fact, mean you accept the proof as
>>>>>>>>> presented by Linz about actual Turing machines -- the one where Ĥ
>>>>>>>>> /does/
>>>>>>>>> copy its input?
>>>>>>>>
>>>>>>>> No it does not.  It is quite crazy that you say this
>>>>>>>
>>>>>>> Take a deep breath.  What is the usual end result when you have
>>>>>>> had to
>>>>>>> resort to thinking I'm saying crazy things?  I am usually right,
>>>>>>> aren't
>>>>>>> I?
>>>>>>
>>>>>> I have already shown how the Linz equivalent code above has been
>>>>>> correctly decided.
>>>>>
>>>>> Only in your own mind.
>>>>>>
>>>>>>>> when I have shown you the actual execution trace of a concrete
>>>>>>>> example
>>>>>>>> of an equivalent H_Hat...
>>>>>>>
>>>>>>> H_Hat is not Ĥ.  Ĥ is a Turing machine which can be run with a tape
>>>>>>> containing the encoding of Ĥ.  What matters for this post is the
>>>>>>> execution trace of the Turing machine Ĥ, not the execution trace of
>>>>>>> your
>>>>>>> x86 code.  The TM execution trace is written like this:
>>>>>>
>>>>>> No that does not matter. What does matter is that my H_Hat is
>>>>>> computationally equivalent to the Linz Ĥ. It has the exact same
>>>>>> relation
>>>>>> between Halts and H_Hat as H has to Ĥ. That was the only required
>>>>>> element.
>>>>>
>>>>> As pointed above, it isn't, if Program P changes its tape, the
>>>>> execution
>>>>> equivalence is broken.
>>>>>
>>>>>>
>>>>>> You have already agreed that computational equivalence is good enough
>>>>>> and now you try to back out of this agreement (as I always expected).
>>>>>>
>>>>>
>>>>> I don't think anyone has complained about this optimization. What they
>>>>> HAVE complained about is that in if we want to make a change to the top
>>>>> level code to test a 'needed' clause, you won't allow the tape to
>>>>> remain
>>>>> per the original definition, even if at the top level we have a
>>>>> different H_Hat or Halt Decider, but that is a DIFFERENT issue.
>>>>>
>>>>
>>>> Only Mike has the capacity to understand this key aspect and he has not
>>>> yet provided me any feedback of my rebuttal of this.
>>>>
>>>> At least he explained why this sort of change is thought to be required.
>>>> Everyone else was incapable of providing any reasoning for their
>>>> requirement merely dogmatic assertions entirely bereft of any reasoning.
>>>>
>>>> It is an actual verifiable fact that the execution of H_Hat under a
>>>> simulator and the execution of H_Hat under a halt decider is perfectly
>>>> identical from H_Hat's point of view, thus not at all two different
>>>> computations as Mike has indicated.
>>>>
>>>> H_Hat does not decide to change its behavior between its simulation
>>>> under a UTM and its simulation under a halt decider because H_Hat is
>>>> utterly unaware of any difference.
>>>>
>>>
>>> There is a VERY big difference between the execution trace of H_Hat
>>> using 'just' a UTM and H_Hat using a Halt Decider.
>>>
>>> The H_Hat(H_Hat) running with a UTM will never get control back from the
>>> UTM, this is clear from the infinite recursion.
>>>
>>> The H_Hat(H_Hat) running with a Halt Decider MUST get control back from
>>> the Halt Decider, as that is a required aspect of a Halt Decider. This
>>> means that the Halt Decider will need to add code beyond just a simple
>>> UTM to catch non-halting behavior in the program under test and resolve
>>> this sort of recursive request.
>>>
>>> These are VERY distinct computations.
>>
>> Not from the perspective of H_Hat. H_hat is unable to distinguish the
>> difference thus it cannot execute its own code differently at all.
> 
> The code directly in H_Hat may not change its behavior (except that in
> one case it doesn't have behvior because it does get to it) but the
> whole machine H_Hat does, as it includes the Halting Decider.

How many times do I have to tell you something before you hear what I 
actually said and quit hearing the voices in you head tell you things 
that I did not say?

The halt decider is not any aspect of H_Hat.
The halt decider is not any aspect of H_Hat.
The halt decider is not any aspect of H_Hat.
The halt decider is not any aspect of H_Hat.
The halt decider is not any aspect of H_Hat.

> Just run the actual traces. With the UTM, the code will run forever in a
> tight recursive loop. With a working halt decider, that loop MUST get
> broken, and control returned eventually to the caller. This is a
> difference of execution.

The proving that the halt decider made the correct halting decision.
It seems like everyone is telling that my halt decider must be broken 
because it gets the right answer.

> Saying that what goes on inside Debug_Step is a false separation.
> Everything that happens within the operation of a function is part of
> the execution of the function.

When-so-ever the execution of any TMD must be aborted to prevent it from 
otherwise infinite execution THIS IS A CORRECT NON-HALTING DECISION.

>>
>>> As to why we need the ability to switch between UTM mode and Halt
>>> Detecting mode, let us first assume that we can add a 3rd parameter to
>>> Debug Step, if this parameter is 0, it will act as a UTM and not stop
>>> the code, if this parameter is a 1, it will enable the Halt Decider.
>>
>> it is simpler to just make this a command line parameter to the x86utm
>> operating system.
> 
> Except that changes the program on the tape, which is not allowed.

It does not change the program on the same. Where the Hell did you get 
that from?

> 
> See note below.
> 
> What this basically means is that you are defining that your Halt
> Decider can't be used in a real turing machine equivalent environment.

Bullshit. My halt decider is not wrong on the basis that it gets the 
correct answet it is right on the basis that it gets the correct answer.

>>
>>> We define our program under test to be the standard Linz H_Hat.
>>>
>>> So
>>>
>>> void H_Hat(P)
>>> {
>>
>> This is cheating.
>>>       u32 aborted = Debug_Step(P, P, 1);
>>>       if(aborted)
>>>         HALT;
>>>       else
>>>         HERE: goto HERE;
>>> }
>>>
>>
>> No one can possibly justify why your cheat is needed.
>>
>>
> 
> The rule we are supposedly applying for Debug_Step is that
> 
> Debug_Step(P, I, 1) == true IFF Debug_Step(P, I, 0) is a non-halting
> computation

That is bullshit UTM mode or halt decider mode as a commend line 
parameter to the operating system.

> 
> It does not make sense that we would define it by
> 
> Debug_Step(P, I, 1) == true IFF Debug_Step(A, B, 0) is a non-halting
> computation.
> 
> Since our function under test uses Debug_Step in its calculation,

IT DOES NOT DO THIS
IT DOES NOT DO THIS
IT DOES NOT DO THIS
IT DOES NOT DO THIS

You can't simply ignore my rebuttal.

> changing the behavior or Debuge_Step renders that function a new
> function, even if it has the same name.

H_Hat cannot possibly change its behavior and in fact it does not change 
its behavior up to the point where the halt decider aborts its 
execution. Any execution trace of H_Hat under a UTM is identical to 
H_Hat under a halt decider up to the point where the halt decider aborts 
its execution.

You cannot correctly say that the halt decide is wrong entirely on the 
basis that it got the correct answer.

> THIS is why I object to you misusing terms.
> 
> It is cleat that YOU need to cheat.
> 


-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#1868 — Re: It is known that a correct halt decider must return false (in this case)[V2](no difference)

Fromolcott <NoOne@NoWhere.com>
Date2020-11-25 09:19 -0600
SubjectRe: It is known that a correct halt decider must return false (in this case)[V2](no difference)
Message-ID<Y5CdnagvBPmM6yPCnZ2dnUU7-U_NnZ2d@giganews.com>
In reply to#1864
On 11/25/2020 9:01 AM, Richard Damon wrote:
> On 11/25/20 9:02 AM, olcott wrote:
>> On 11/25/2020 6:17 AM, Richard Damon wrote:
>>> On 11/25/20 12:05 AM, olcott wrote:
> 
>>> The code directly in H_Hat may not change its behavior (except that in
>>> one case it doesn't have behvior because it does get to it) but the
>>> whole machine H_Hat does, as it includes the Halting Decider.
>>
>> How many times do I have to tell you something before you hear what I
>> actually said and quit hearing the voices in you head tell you things
>> that I did not say?
>>
>> The halt decider is not any aspect of H_Hat.
>> The halt decider is not any aspect of H_Hat.
>> The halt decider is not any aspect of H_Hat.
>> The halt decider is not any aspect of H_Hat.
>> The halt decider is not any aspect of H_Hat.
> 
> But it IS. Are you saying that in the following functions:
> 
> double comp(double x) {
>     return sin(2.0*x);
> }
> 
> That the operation of the sin function is not an aspect of the function
> comp?
> 
> That it 'behavior' would stay the same if we flipped an option somewhere
> that changed the function from interpreting its argument from radians to
> degrees? or even made it compute sinh?
> 
> Of COURSE, anything that a function calls becomes an aspect of that
> functions execution.

It is not an aspect of the caller in that it has its own machine code 
that is not embedded within the caller.

In this situation we can change the function being called and there will 
be no change to the behavior of comp() because it never reaches the 
called code.

double comp(double x)
{
  HERE: goto HERE;
     return sin(2.0*x);
}

We have the same case here. Even though DebugTrace() does specify a 
return value that would cause H_Halt to halt, H_Hat never reaches this 
return value so it never halts, thus its behavior is unaffected by the 
return value from DebugTrace();

int DebugTrace(u32 N, u32 M)
{
   return ((int(*)(int))N)(M);
   return 1;
}


void H_Hat(u32 P)
{
   u32 Aborted = DebugTrace(P, P);
   if (Aborted)
     HALT
   else
     HERE: goto HERE;
}

When an otherwise UTM correctly decides that its input would never halt 
unless this otherwise UTM stopped simulating it this otherwise UTM has 
made a correct not halting decision.

-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#1876 — Re: It is known that a correct halt decider must return false (in this case)[V2](no difference)

Fromolcott <NoOne@NoWhere.com>
Date2020-11-25 11:37 -0600
SubjectRe: It is known that a correct halt decider must return false (in this case)[V2](no difference)
Message-ID<qc6dnQFgArvACyPCnZ2dnUU7-WfNnZ2d@giganews.com>
In reply to#1868
On 11/25/2020 9:55 AM, Richard Damon wrote:
> On 11/25/20 10:19 AM, olcott wrote:
>> On 11/25/2020 9:01 AM, Richard Damon wrote:
>>> On 11/25/20 9:02 AM, olcott wrote:
>>>> On 11/25/2020 6:17 AM, Richard Damon wrote:
>>>>> On 11/25/20 12:05 AM, olcott wrote:
>>>
>>>>> The code directly in H_Hat may not change its behavior (except that in
>>>>> one case it doesn't have behvior because it does get to it) but the
>>>>> whole machine H_Hat does, as it includes the Halting Decider.
>>>>
>>>> How many times do I have to tell you something before you hear what I
>>>> actually said and quit hearing the voices in you head tell you things
>>>> that I did not say?
>>>>
>>>> The halt decider is not any aspect of H_Hat.
>>>> The halt decider is not any aspect of H_Hat.
>>>> The halt decider is not any aspect of H_Hat.
>>>> The halt decider is not any aspect of H_Hat.
>>>> The halt decider is not any aspect of H_Hat.
>>>
>>> But it IS. Are you saying that in the following functions:
>>>
>>> double comp(double x) {
>>>      return sin(2.0*x);
>>> }
>>>
>>> That the operation of the sin function is not an aspect of the function
>>> comp?
>>>
>>> That it 'behavior' would stay the same if we flipped an option somewhere
>>> that changed the function from interpreting its argument from radians to
>>> degrees? or even made it compute sinh?
>>>
>>> Of COURSE, anything that a function calls becomes an aspect of that
>>> functions execution.
>>
>> It is not an aspect of the caller in that it has its own machine code
>> that is not embedded within the caller.
> 
> The code may not be present in the code of the caller. The behavior of
> the called function IS in the behavior of the context of the caller.

Not at all:

On 11/25/2020 10:16 AM, Mike Terry wrote:
 > 1)  There is the possibility that a halt decider might choose to quit
 > enumerating the calculation steps earlier than the UTM - but of course
 > the calculation itself is nothing to do with either of those
 > emulations.
 >   And any perceived "change of behaviour" as a result of the halt
 > decider aborting its emulation is not actually behaviour of H_Hat,
 > it's different emulator behaviour.  Aside from this, the behaviour
 > OF THE SAME CALCULATION under different emulators will of course
 > be the same up to the point where the emulators decide to
 > stop enumerating the steps.
 > (Duh!)
 >



-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#1878 — Re: It is known that a correct halt decider must return false (in this case)[V2](no difference)

Fromolcott <NoOne@NoWhere.com>
Date2020-11-25 12:13 -0600
SubjectRe: It is known that a correct halt decider must return false (in this case)[V2](no difference)
Message-ID<JsSdnbc3VckqAyPCnZ2dnUU7-UnNnZ2d@giganews.com>
In reply to#1876
On 11/25/2020 12:03 PM, Richard Damon wrote:
> On 11/25/20 12:37 PM, olcott wrote:
>> On 11/25/2020 9:55 AM, Richard Damon wrote:
>>>
>>> The code may not be present in the code of the caller. The behavior of
>>> the called function IS in the behavior of the context of the caller.
>>
>> Not at all:
>>
>> On 11/25/2020 10:16 AM, Mike Terry wrote:
>>> 1)  There is the possibility that a halt decider might choose to quit
>>> enumerating the calculation steps earlier than the UTM - but of course
>>> the calculation itself is nothing to do with either of those
>>> emulations.
>>>     And any perceived "change of behaviour" as a result of the halt
>>> decider aborting its emulation is not actually behaviour of H_Hat,
>>> it's different emulator behaviour.  Aside from this, the behaviour
>>> OF THE SAME CALCULATION under different emulators will of course
>>> be the same up to the point where the emulators decide to
>>> stop enumerating the steps.
>>> (Duh!)
>>>
> 
> First, If Mike was actually stating that there is no behavior change in
> H_Hat between it having a UTM or a Halt Decider as the operation it is
> use, I will disagree with it, and your argument just becomes a case of
> Appealing to Authority. It is clear that there IS a change of behavior.

I keep proving there there is no change in behavior and you keep 
ignoring my proof.

To understand my proof that there is no change in behavior you must tell 
me the return value that H_Hat() receives from its invocation of
DebugTrace().


int DebugTrace(u32 N, u32 M)
{
   return ((int(*)(int))N)(M);
   return 1;
}


void H_Hat(u32 P)
{
   u32 Aborted = DebugTrace(P, P);
   if (Aborted)
     HALT
   else
     HERE: goto HERE;
}


int main()
{
   u32 P = (u32)H_Hat;
   DebugTrace(P, P);
   HALT;
}




-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#1880 — Re: It is known that a correct halt decider must return false (in this case)[V2](no difference)

Fromolcott <NoOne@NoWhere.com>
Date2020-11-25 13:33 -0600
SubjectRe: It is known that a correct halt decider must return false (in this case)[V2](no difference)
Message-ID<gPGdnYK3v5gOLCPCnZ2dnUU7-K3NnZ2d@giganews.com>
In reply to#1878
On 11/25/2020 1:27 PM, Richard Damon wrote:
> On 11/25/20 1:13 PM, olcott wrote:
>> On 11/25/2020 12:03 PM, Richard Damon wrote:
>>> On 11/25/20 12:37 PM, olcott wrote:
>>>> On 11/25/2020 9:55 AM, Richard Damon wrote:
>>>>>
>>>>> The code may not be present in the code of the caller. The behavior of
>>>>> the called function IS in the behavior of the context of the caller.
>>>>
>>>> Not at all:
>>>>
>>>> On 11/25/2020 10:16 AM, Mike Terry wrote:
>>>>> 1)  There is the possibility that a halt decider might choose to quit
>>>>> enumerating the calculation steps earlier than the UTM - but of course
>>>>> the calculation itself is nothing to do with either of those
>>>>> emulations.
>>>>>      And any perceived "change of behaviour" as a result of the halt
>>>>> decider aborting its emulation is not actually behaviour of H_Hat,
>>>>> it's different emulator behaviour.  Aside from this, the behaviour
>>>>> OF THE SAME CALCULATION under different emulators will of course
>>>>> be the same up to the point where the emulators decide to
>>>>> stop enumerating the steps.
>>>>> (Duh!)
>>>>>
>>>
>>> First, If Mike was actually stating that there is no behavior change in
>>> H_Hat between it having a UTM or a Halt Decider as the operation it is
>>> use, I will disagree with it, and your argument just becomes a case of
>>> Appealing to Authority. It is clear that there IS a change of behavior.
>>
>> I keep proving there there is no change in behavior and you keep
>> ignoring my proof.
> 
> IF we assume that the halt detector provides no change in behavior, then
> it must be a faulty halt detector, as a halt detector is a very
> different sort of thing to a UTM.
> 
> A UTM just executes a machine, and maybe has a way to tell your the
> 'answer' the program being run gave (final state or tape). If the
> program has infinite execution, it never returns.
> 
> On the other hand, A halt decider needs to return in finite time and
> returns a simple answer of halted or not. I suppose you could make a
> somewhat specialized halt decider that if the imput machine halts, it
> tells you what state it halted in. In either case, the calling program
> will have access to the tape.
> 
> This says that there is VERY much different behavior in the calling
> program depending on the halting nature of the input.
> 
>>
>> To understand my proof that there is no change in behavior you must tell
>> me the return value that H_Hat() receives from its invocation of
>> DebugTrace().
> 
> 
> Undefined Behavior. Likely results on a real x86 processor a stack fault
> due to infinite recursion (if running on a protected OS), so NO return
> ever. If running on a non-protected mode OS, really undefined behavior.

You dodged the question. I will be more specific.

Does the code shown below** specify that H_Hat() will receive a return 
value from DebugTrace() ?

** Ignore hardware, go only by what the C code itself specifies.

>>
>>
>> int DebugTrace(u32 N, u32 M)
>> {
>>    return ((int(*)(int))N)(M);
>>    return 1;
>> }
>>
>>
>> void H_Hat(u32 P)
>> {
>>    u32 Aborted = DebugTrace(P, P);
>>    if (Aborted)
>>      HALT
>>    else
>>      HERE: goto HERE;
>> }
>>
>>
>> int main()
>> {
>>    u32 P = (u32)H_Hat;
>>    DebugTrace(P, P);
>>    HALT;
>> }
>>
>>
>>
>>
> 


-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#1883 — Re: It is known that a correct halt decider must return false (in this case)[V2](no difference)

Fromolcott <NoOne@NoWhere.com>
Date2020-11-25 14:16 -0600
SubjectRe: It is known that a correct halt decider must return false (in this case)[V2](no difference)
Message-ID<_O2dnW8q5903JiPCnZ2dnUU7-X3NnZ2d@giganews.com>
In reply to#1880
On 11/25/2020 1:46 PM, Richard Damon wrote:
> On 11/25/20 2:33 PM, olcott wrote:
>> On 11/25/2020 1:27 PM, Richard Damon wrote:
>>> On 11/25/20 1:13 PM, olcott wrote:
>>>> On 11/25/2020 12:03 PM, Richard Damon wrote:
>>>>> On 11/25/20 12:37 PM, olcott wrote:
>>>>>> On 11/25/2020 9:55 AM, Richard Damon wrote:
>>>>>>>
>>>>>>> The code may not be present in the code of the caller. The
>>>>>>> behavior of
>>>>>>> the called function IS in the behavior of the context of the caller.
>>>>>>
>>>>>> Not at all:
>>>>>>
>>>>>> On 11/25/2020 10:16 AM, Mike Terry wrote:
>>>>>>> 1)  There is the possibility that a halt decider might choose to quit
>>>>>>> enumerating the calculation steps earlier than the UTM - but of
>>>>>>> course
>>>>>>> the calculation itself is nothing to do with either of those
>>>>>>> emulations.
>>>>>>>       And any perceived "change of behaviour" as a result of the halt
>>>>>>> decider aborting its emulation is not actually behaviour of H_Hat,
>>>>>>> it's different emulator behaviour.  Aside from this, the behaviour
>>>>>>> OF THE SAME CALCULATION under different emulators will of course
>>>>>>> be the same up to the point where the emulators decide to
>>>>>>> stop enumerating the steps.
>>>>>>> (Duh!)
>>>>>>>
>>>>>
>>>>> First, If Mike was actually stating that there is no behavior change in
>>>>> H_Hat between it having a UTM or a Halt Decider as the operation it is
>>>>> use, I will disagree with it, and your argument just becomes a case of
>>>>> Appealing to Authority. It is clear that there IS a change of behavior.
>>>>
>>>> I keep proving there there is no change in behavior and you keep
>>>> ignoring my proof.
>>>
>>> IF we assume that the halt detector provides no change in behavior, then
>>> it must be a faulty halt detector, as a halt detector is a very
>>> different sort of thing to a UTM.
>>>
>>> A UTM just executes a machine, and maybe has a way to tell your the
>>> 'answer' the program being run gave (final state or tape). If the
>>> program has infinite execution, it never returns.
>>>
>>> On the other hand, A halt decider needs to return in finite time and
>>> returns a simple answer of halted or not. I suppose you could make a
>>> somewhat specialized halt decider that if the imput machine halts, it
>>> tells you what state it halted in. In either case, the calling program
>>> will have access to the tape.
>>>
>>> This says that there is VERY much different behavior in the calling
>>> program depending on the halting nature of the input.
>>>
>>>>
>>>> To understand my proof that there is no change in behavior you must tell
>>>> me the return value that H_Hat() receives from its invocation of
>>>> DebugTrace().
>>>
>>>
>>> Undefined Behavior. Likely results on a real x86 processor a stack fault
>>> due to infinite recursion (if running on a protected OS), so NO return
>>> ever. If running on a non-protected mode OS, really undefined behavior.
>>
>> You dodged the question. I will be more specific.
>>
>> Does the code shown below** specify that H_Hat() will receive a return
>> value from DebugTrace() ?
>>
>> ** Ignore hardware, go only by what the C code itself specifies.
> 
> What the C code specifies is that Demons might be coming out of your
> nose. As I mentioned, you code has undefined behavior, multiple cases of it.

The C code itself specified infinite recursion that never returns any 
value to H_Hat(). Compiler implelementors may decide different ways of 
handling this the default behavior would be to abort when the code runs 
out of stack space.

> Now, ignoring that, it SAYS that DebugTrace will return a value, the
> value it gets from calling the function provided (with parameter
> provided), but that function is not actually defined to return any
> value, 

Yet another case of your responding to what you think that I said rather 
than responding to what I actually said.

DebugTrace() is defined to return 1.
DebugTrace() is defined to return 1.
DebugTrace() is defined to return 1.
DebugTrace() is defined to return 1.

The question remains what return value does H_Hat() receive?
The question remains what return value does H_Hat() receive?
The question remains what return value does H_Hat() receive?
The question remains what return value does H_Hat() receive?
The question remains what return value does H_Hat() receive?

There are more steps after aft this, if we every get past your dodging 
the question.

> so what will be returned is undefined, and perhaps could even
> destroy the machine it is running on for a particularly hostile machine.
> 
> Now since H_Hat never actually 'returns' neither will DebugTrace, that
> isn't quite as important.
> 
>>
>>>>
>>>>
>>>> int DebugTrace(u32 N, u32 M)
>>>> {
>>>>     return ((int(*)(int))N)(M);
>>>>     return 1;
>>>> }
>>>>
>>>>
>>>> void H_Hat(u32 P)
>>>> {
>>>>     u32 Aborted = DebugTrace(P, P);
>>>>     if (Aborted)
>>>>       HALT
>>>>     else
>>>>       HERE: goto HERE;
>>>> }
>>>>
>>>>
>>>> int main()
>>>> {
>>>>     u32 P = (u32)H_Hat;
>>>>     DebugTrace(P, P);
>>>>     HALT;
>>>> }
>>>>
>>>>
>>>>
>>>>
>>>
>>
>>
> 


-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#1889 — Re: It is known that a correct halt decider must return false (in this case)[V2](no difference)

Fromolcott <NoOne@NoWhere.com>
Date2020-11-25 17:18 -0600
SubjectRe: It is known that a correct halt decider must return false (in this case)[V2](no difference)
Message-ID<uqidnZlhW4TJeyPCnZ2dnUU7-RPNnZ2d@giganews.com>
In reply to#1883
On 11/25/2020 4:32 PM, Richard Damon wrote:
> On 11/25/20 3:16 PM, olcott wrote:
>> On 11/25/2020 1:46 PM, Richard Damon wrote:
>>> On 11/25/20 2:33 PM, olcott wrote:
>>>> On 11/25/2020 1:27 PM, Richard Damon wrote:
>>>>> On 11/25/20 1:13 PM, olcott wrote:
>>>>>> To understand my proof that there is no change in behavior you must
>>>>>> tell
>>>>>> me the return value that H_Hat() receives from its invocation of
>>>>>> DebugTrace().
>>>>>
>>>>>
>>>>> Undefined Behavior. Likely results on a real x86 processor a stack
>>>>> fault
>>>>> due to infinite recursion (if running on a protected OS), so NO return
>>>>> ever. If running on a non-protected mode OS, really undefined behavior.
>>>>
>>>> You dodged the question. I will be more specific.
>>>>
>>>> Does the code shown below** specify that H_Hat() will receive a return
>>>> value from DebugTrace() ?
>>>>
>>>> ** Ignore hardware, go only by what the C code itself specifies.
>>>
>>> What the C code specifies is that Demons might be coming out of your
>>> nose. As I mentioned, you code has undefined behavior, multiple cases
>>> of it.
>>
>> The C code itself specified infinite recursion that never returns any
>> value to H_Hat(). Compiler implelementors may decide different ways of
>> handling this the default behavior would be to abort when the code runs
>> out of stack space.
> 
> The C code has preformed a violation of the requirements of the standard
> in performing the call inside DebugTrace. After this point, the C
> language provide NO, ZERO, ZILTCH requirements on what the code does. As
> is commonly said, the implementation is allowed to make Demons come out
> of your Nose. The Undefined behavior is cause by calling a function
> through a pointer to a function with a different type than the actual
> function. So even before we hit the critical undefined behavior from the
> stack overflow from the recursion, we hit critical undefined behavior
> before ever got into H_Hat.
> 
> I know you don't like me telling you how to right code, but this code
> would NEVER pass a review at my firm. Debug_Step should NOT be taking
> two u32 parameters, but given that we are passing pointer values they
> should be a function pointer of the type that Turing Machines are
> exepcted to be, and a data pointer, likely a void* or a char or uint8_t*
>>
>>> Now, ignoring that, it SAYS that DebugTrace will return a value, the
>>> value it gets from calling the function provided (with parameter
>>> provided), but that function is not actually defined to return any
>>> value,
>>
>> Yet another case of your responding to what you think that I said rather
>> than responding to what I actually said.
> 
> READ YOUR CODE.
> 
>>
>> DebugTrace() is defined to return 1.
>> DebugTrace() is defined to return 1.
>> DebugTrace() is defined to return 1.
>> DebugTrace() is defined to return 1.
> 
> IT CAN NEVER GET THERE. Look at your code, you first return the value
> the provided function returned. The return 1 is DEAD CODE.
> 

int DebugTrace(u32 P, u32 I)
{
   ((int(*)(int))P)(I);
   return 1;
}

void H_Hat(u32 P)
{
   u32 Aborted = DebugTrace(P, P);
   if (Aborted)
     HALT
   else
     HERE: goto HERE;
}

int main()
{
   u32 P = (u32)H_Hat;
   DebugTrace(P, P);
   HALT;
}

If you can finally see that H_Hat() would never receive any return value 
from DebugTrace() then you should also see that Halts() is correct when 
it aborts H_Hat() before it returns any value to H_Hat.


-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#1893 — Re: It is known that a correct halt decider must return false (in this case)[V2](no difference)

Fromolcott <NoOne@NoWhere.com>
Date2020-11-25 18:49 -0600
SubjectRe: It is known that a correct halt decider must return false (in this case)[V2](no difference)
Message-ID<zf6dnT4Z6PgIZiPCnZ2dnUU7-TvNnZ2d@giganews.com>
In reply to#1876
On 11/25/2020 6:26 PM, Mike Terry wrote:
> On 25/11/2020 23:26, Richard Damon wrote:
>> On 11/25/20 3:55 PM, Mike Terry wrote:
>>> On 25/11/2020 18:03, Richard Damon wrote:
>>>> On 11/25/20 12:37 PM, olcott wrote:
>>>>> On 11/25/2020 9:55 AM, Richard Damon wrote:
>>>>>>
>>>>>> The code may not be present in the code of the caller. The 
>>>>>> behavior of
>>>>>> the called function IS in the behavior of the context of the caller.
>>>>>
>>>>> Not at all:
>>>>>
>>>>> On 11/25/2020 10:16 AM, Mike Terry wrote:
>>>>>> 1)  There is the possibility that a halt decider might choose to quit
>>>>>> enumerating the calculation steps earlier than the UTM - but of 
>>>>>> course
>>>>>> the calculation itself is nothing to do with either of those
>>>>>> emulations.
>>>>>>    And any perceived "change of behaviour" as a result of the halt
>>>>>> decider aborting its emulation is not actually behaviour of H_Hat,
>>>>>> it's different emulator behaviour.  Aside from this, the behaviour
>>>>>> OF THE SAME CALCULATION under different emulators will of course
>>>>>> be the same up to the point where the emulators decide to
>>>>>> stop enumerating the steps.
>>>>>> (Duh!)
>>>>>>
>>>>
>>>> First, If Mike was actually stating that there is no behavior change in
>>>> H_Hat between it having a UTM or a Halt Decider as the operation it is
>>>> use, I will disagree with it, and your argument just becomes a case of
>>>> Appealing to Authority. It is clear that there IS a change of behavior.
>>>
>>> I thought my "the behaviour OF THE SAME CALCULATION under different
>>> emulators will of course be the same up to the point where the emulators
>>> decide to stop enumerating the steps." was 100% clear.  I even put OF
>>> THE SAME CALCULATION in caps. :)
>>>
>>> I'll say it differently:
>>>
>>> HMM, after getting to the end of this post I realise perhaps the key
>>> here is my technical use of the word "calculation":
>>>
>>> Def.  Given a TM P, and input data I, the *calculation* P(I) is the
>>> sequence of calculation steps (p0,p1,p2,...) as usually defined
>>> (recursively) in the theory of TMs.  (Note: nothing to do with 
>>> emulation!)
>>>
>>> Ok...
>>> Suppose we have a calculation P(I), with steps (p0,p1,p2,...),
>>> Suppose we have two emulators E1 and E2 which enumerate the steps of
>>> P(I). E1 enumerates steps as far as n1 and then stops, for whatever
>>> reason, while E2 enumerates steps as far as n2 and then stops.
>>>
>>> Then:
>>>    The steps enumerated by E1 will be (p0,p1,...p_n1)
>>>    The steps enumerated by E2 will be (p0,p1,...p_n2)
>>>    The enumerations of E1 and E2 will agree, as far as the
>>>    enumerations both go.
>>>
>>> That is because both E1 and E2 are just enumerating the same
>>> "calculation" P(I) = (p0,p1,p2,...).
>>>
>>> The sequence (p0,p1,p2,...) has a mathematical definition, which depends
>>> only on P and I, not any emulator which enumerates the steps.
>>>
>>> Do you agree with all the above?  (You may use a slightly different word
>>> for "calculation" perhaps - please adjust accordingly!)
>>
>> The key feature here is that the sequence of steps done by going into
>> the UTM are different then the sequence of steps going into the Halt
>> Decicer, because presumably at some point the halt decider is going to
>> make its decision and return that answer, while the UTM will just keep
>> on executiong.
> 
> Agreed.
> 
> But nothing I said above involved halting machines or UTMs, it was just 
> discussing "emulation" generally:  E1, E2 being two emulators.  What you 
> describe as the halt-decider giving up earlier than the UTM is just what 
> I was saying with my n1, n2 which can be different.  (Maybe P(I) is 
> non-halting, and Decider looks at 20000 steps then stops, whereas UTM 
> will never stop.)  We can say at least that the 20000 steps as examined 
> by the two emulators will be the same! Er, that's it :)
> 
>>
>> One KEY point here is that the machines should have a different external
>> structure. The UTM will have a start state, and one terminal state to
>> indicate the machine being run finished. The Halt decider has two
>> terminal states, one for the machine WILL halt (might get there before
>> it actually did if it can tell, might not even have done an emulation),
>> and a seconde to say that the machine WILL never halt if it was run.
>>
>> If the machine given to them is halting, then the ultimate results might
>> be the same.
>>
>> Now, which is RUNNING H_Hat doesn't matter, except that the halt decider
>> isn't required to actually try to run the machine, but a halt decider
>> making the vain attempt to make the decison by simple emulation would
>> step through the same steps.
> 
> Agreed.  (As expected - despite PO's suggestion you don't understand this.)
> 
>>>
>>> Now on to specifics:
>>>
>>> Do you (Richard) take the following two machines H_Hat1 and H_Hat2 to be
>>> THE SAME machine:   (to have and to hold... :))
>>>
>>>    H_Hat1:   H_Hat as above, "having a UTM as the
>>>              operation it is use [sic]"
>>>    H_Hat2:   H_Hat as above, "having a halt decider as the
>>>              operation it is use [sic]"
>>
>> H_Hat1 (or I would call H_HAT_UT) is a different machine than H_Hat2
>> (which is Linz's machine)
>>>
>>> (Sorry, I don't understand the phrase "operation it is use(ing?)"  I
>>> suspect this relates to two completely different machines, each using
>>> its own unique Halts()/ABNHBD()/whatever, but it might relate to one
>>> FIXED H_Hat whose calculation is being emulated (possibly to different
>>> depths) under two different emulators, E1=UTM and E2=haltdecider.)
>>
>> Peter is talking about changing the behavior of Debug_Step from first
>> being simply a UTM to being the halt decider. When he does this, this
>> will change the computation that H_Hat is doing.
> 
> Exactly - 100% agreement.  So these are DIFFERENT CALCULATIONS, and so 
> there's no reason to think they must have the same steps if emulated. 
> Since what I said only applied to THE SAME calculation, but run under 
> different emulators, my comments which PO quoted don't apply.
> 
>>>
>>> If your answer is "no, H_Hat1 and H_Hat2 are different", then the
>>> calculation H_Hat1(H_Hat1) and H_Hat2(H_Hat2) are DIFFERENT
>>> CALCULATIONS, so I didn't say they had the same behaviour.
>>>
>>> If your answer is "yes, we're talking about enumerating the same
>>> calculation under two different emulators", then what I said applies:
>>> the emulators are enumerating the same calculation, and so the
>>> enumerations will agree up to the point where one of the emulators gives
>>> up.
>>>
>>> For example, one enumerator may see (p0,p1,p2,p3) and then give up,
>>> whereas the second sees (p0,p1,p2,p3,p4) then gives up.  The first four
>>> steps are the same.  Regardless of this, the actual "calculation"
>>> (p0,p1,p2...) either halts or doesn't halt.
>>
>> Note that H_Hat2 actual uses the results of the decision to decide what
>> to do. So it isn't that maybe it went farther in executing the tape then
>> the other, but that after making that decision, it decides on a path of
>> execution to perform from there. Thus we have some ADDED functionality
>> on the non-halting behavior path the the halt decider has that the UTM
>> did not have.
> 
> Agreed.  Put more simply, the calculations are different, and so the 
> fact that one is non-halting doesn't mean the other is non-halting.
> 
>>>
>>> In my wording I said that the "behaviour of the *calculation*" (e.g.
>>> halting/non-halting) is not changed by either emulator "giving up" after
>>> 3 or 4 steps.  If you want to use a different interpretation for
>>> "behaviour" which says that the behaviour of calculation (p_i) is
>>> different under the two emulators, that would be a different word usage
>>> to mine.  [I say there is one calculation (p_i) which "behaves" in one
>>> way, and the two emulators just enumerate this one calculation to
>>> different depths.  Under my interpretation, the "difference" is not in
>>> the one calculation (p_i), but in the behaviour of the /emulators/ in so
>>> far as the emulators make different decisions on how far to enumerate
>>> the calculation.]
>>>
>> I think you are looking at a different level of processing than I am, I
>> see the primary calcualtion at the top level, H_Hat is trying to decide
>> what to do, so it asked the Halt Decider a question. In a real sense,
>> H_Hat doesn't care diddly how the Halt Decider works, whether it runs
>> the machine provided or does some magical hashing function to make a
>> decision, so any difference in how the program it was given ran is
>> meaningless to it, it just wants to know would it complete.  THAT
>> computation works very differently between asking a UTM that question an
>> a Halting Decider. The Halting Decider has the ability to say, this
>> computation will not complete, to which H_Hat can say great, I will just
>> halt then. Or the Halting Decider can say that this computation will
>> complete, at which point H_Hat desides to just sit there idleing its
>> engines forever and not halt.
>>
>> When H_Hat_UTM asks the UTM to run the input, the UTM has just one
>> answer it can give, it can say that the input came to a halt, and then
>> H_Hat will just idle again. A second behavior is the UTM can just run
>> forever because the input program was non-halting. This give a very
>> different result than that same operation with the Halt Decicder.
>>
> 
> OK, I agree with all that, no problem.
> 
> The text of mine that PO quoted is indeed at a different (simpler) level 
> of detail.  It did not involve H_Hat, halt deciders or UTMs except 
> perhaps as illustrative examples.
> 
> All I (originally) said was that if we have ONE FIXED (P,I) input, and 
> two correctly written emulators which examine that input, then the two 
> emulators will agree on the calculation steps up to the point one of 
> them gives up.  PO claims I'm the only person (apart from him!) who 
> understands that, but of course I know everybody would agree once 
> terminology is sorted.
> 
> In my "simple" level it is enough to simply say that H_Hat_Decider is 
> different from H_Hat_UTM, and so PO can't use my words to imply that 
> H_Hat_Decider(H_Hat_Decider) has the same behaviour as 
> H_Hat_UTM(H_Hat_UTM).
> 
> Going back to your original words:
> 
>  >>> First, If Mike was actually stating that there is no behavior 
> change in
>  >>> H_Hat between it having a UTM or a Halt Decider as the operation it is
>  >>> use, I will disagree with it, and your argument just becomes a case of
>  >>> Appealing to Authority. It is clear that there IS a change of 
> behavior.
> 
> then the resolution for this mini-thread is that I wouldn't claim those 
> two hats were the same, so I wouldn't apply remarks about how THE SAME 
> calculation behaves under different emulators - it's just not 
> applicable.  (So, no I don't say there's no behaviour change - it's just 
> PO being PO.)
> 
> Phew! Glad that's cleared up :)
> 
>>> I accept that others may use terms slightly differently, but the main
>>> thing is the facts don't change.  (PO doesn't understand complications
>>> like this, so whereas some may say he exploits this to confuse people, I
>>> would say he's just too stupid to appreciate what's actually going on.)
>>>
>>>>
>>>> I also think he is refering to a different topic. Yes, H_Hat makes no
>>>> decision to change its behavior because of the change, but its behavior
>>>> IS changed, and Mike even mentions this. That AFTER the point of the
>>>> trace when the abort occurs, the trace for the caller to the operation
>>>> is now different, so it is doing a different computation.
>>>>
>>>
>>> Aha, that sounds like a mere difference in use of the word
>>> "calculation".  I use it to mean the complete mathematically defined
>>> sequence (p_i).  You seem to use it to mean "the results of emulation
>>> activity" (not the HP concept used to define halting/non-halting).
>>> That's OK I guess, since we could say that what an emulator does is
>>> "calculate the steps", but then what word do you use for what I call the
>>> calculation?  Is there a standard terminology here?  (I try to be
>>> consistant in my own usage...)
>>>
>>>
>>> Mike.
>>>
>>
>> I think the big difference is you seem to be looking at the computation
>> being done BY the UTM/Decider, while I am looking at the computation
>> being done WITH the results of the UTM/Decider, since THAT is the
>> machine the question is being asked of when we start at H_Hat.
>>

I am sure that Richard still does not get this:

On 11/25/2020 10:16 AM, Mike Terry wrote:
 > 1)  There is the possibility that a halt decider
 > might choose to quit enumerating the calculation
 > steps earlier than the UTM

 > ...any perceived "change of behaviour" as a
 > result of the halt decider aborting its emulation
 > is not actually behaviour of H_Hat, it's different
 > emulator behaviour.



-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#1899 — Re: It is known that a correct halt decider must return false (in this case)[V2](no difference)

Fromolcott <NoOne@NoWhere.com>
Date2020-11-25 20:43 -0600
SubjectRe: It is known that a correct halt decider must return false (in this case)[V2](no difference)
Message-ID<G8qdnT8Nar6giyLCnZ2dnUU7-VXNnZ2d@giganews.com>
In reply to#1893
On 11/25/2020 7:30 PM, Richard Damon wrote:
> On 11/25/20 7:49 PM, olcott wrote:
> 
>> I am sure that Richard still does not get this:
>>
>> On 11/25/2020 10:16 AM, Mike Terry wrote:
>>> 1)  There is the possibility that a halt decider
>>> might choose to quit enumerating the calculation
>>> steps earlier than the UTM
>>
>>> ...any perceived "change of behaviour" as a
>>> result of the halt decider aborting its emulation
>>> is not actually behaviour of H_Hat, it's different
>>> emulator behaviour.
>>
>>
>>
> 
> I fully understand it, and as Mike said, it is not applicable to this
> problem.
> 
> The key is he was talking about the steps taken INSIDE the emulation,
> which yes, there is no diference base on what is outside it.
> 
> There IS a difference to what happens OUTSIDE the emulation, to the
> machine that is CALLING the UTM/Halt Decider.
> 
> Now, because of the recursion that is happening, many of the machines
> are actually in both situations.
> 
> Thus
> 
> int H_UTM(P)
> {
>     if(UTM(P, P))
>         while(1) ;
>     else
>        HALT;
> }
> 
> is a different computation from
> 
> int H_Halt(P)
> {
>    if(Halt_Detector(P,P))
>        while(1);
>    else
>        HALT;
> }
> 
> (irrespective of what P is so we are talking the recursive stuff yet)


That is an incorrect way of specifying it.
Here is the correct way.

void H_Hat(u32 P)
{
   u32 Aborted = DebugTrace(P, P);
   if (Aborted)
     HALT
   else
     HERE: goto HERE;
}

int main()
{
   u32 P = (u32)H_Hat;
   DebugTrace(P, P);
   HALT;
}


void H_Hat(u32 P)
{
   u32 Aborted = Halts(P, P);
   if (Aborted)
     HALT
   else
     HERE: goto HERE;
}

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


 >> On 11/25/2020 10:16 AM, Mike Terry wrote:
 >>> ...any perceived "change of behaviour" as a
 >>> result of the halt decider aborting its emulation
 >>> is not actually behaviour of H_Hat, it's different
 >>> emulator behaviour.

Thus when Halts() decides to abort H_Hat it is the same H_Hat as the 
H_Hat that DebugTrace(P, P) is merely emulating.

-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#1901 — Re: It is known that a correct halt decider must return false (in this case)[V2](no difference)

Fromolcott <NoOne@NoWhere.com>
Date2020-11-25 22:30 -0600
SubjectRe: It is known that a correct halt decider must return false (in this case)[V2](no difference)
Message-ID<7YednRDmR8LlsiLCnZ2dnUU7-VHNnZ2d@giganews.com>
In reply to#1899
On 11/25/2020 10:12 PM, Mike Terry wrote:
> On 26/11/2020 02:43, olcott wrote:
>> On 11/25/2020 7:30 PM, Richard Damon wrote:
>>> On 11/25/20 7:49 PM, olcott wrote:
>>>
>>>> I am sure that Richard still does not get this:
>>>>
>>>> On 11/25/2020 10:16 AM, Mike Terry wrote:
>>>>> 1)  There is the possibility that a halt decider
>>>>> might choose to quit enumerating the calculation
>>>>> steps earlier than the UTM
>>>>
>>>>> ...any perceived "change of behaviour" as a
>>>>> result of the halt decider aborting its emulation
>>>>> is not actually behaviour of H_Hat, it's different
>>>>> emulator behaviour.
>>>>
>>>>
>>>>
>>>
>>> I fully understand it, and as Mike said, it is not applicable to this
>>> problem.
>>>
>>> The key is he was talking about the steps taken INSIDE the emulation,
>>> which yes, there is no diference base on what is outside it.
>>>
>>> There IS a difference to what happens OUTSIDE the emulation, to the
>>> machine that is CALLING the UTM/Halt Decider.
>>>
>>> Now, because of the recursion that is happening, many of the machines
>>> are actually in both situations.
>>>
>>> Thus
>>>
>>> int H_UTM(P)
>>> {
>>>     if(UTM(P, P))
>>>         while(1) ;
>>>     else
>>>        HALT;
>>> }
>>>
>>> is a different computation from
>>>
>>> int H_Halt(P)
>>> {
>>>    if(Halt_Detector(P,P))
>>>        while(1);
>>>    else
>>>        HALT;
>>> }
>>>
>>> (irrespective of what P is so we are talking the recursive stuff yet)
>>
>>
>> That is an incorrect way of specifying it.
>> Here is the correct way.
> 
> Richard does not specify the input data P for the calculation, so I 
> would have said H_UTM(H_UTM) is a different computation from 
> H_Halt(H_Halt).  (Or that H_UTM is a different machine from H_Halt, or 
> maybe supplied the main() setup/call to make the input clear.  We all 
> understand what was meant though...)
> 
>>
>> void H_Hat(u32 P)
>> {
>>   u32 Aborted = DebugTrace(P, P);
>>   if (Aborted)
>>     HALT
>>   else
>>     HERE: goto HERE;
>> }
>>
>> int main()
>> {
>>   u32 P = (u32)H_Hat;
>>   DebugTrace(P, P);
>>   HALT;
>> }
>>
>>
>> void H_Hat(u32 P)
>> {
>>   u32 Aborted = Halts(P, P);
>>   if (Aborted)
>>     HALT
>>   else
>>     HERE: goto HERE;
>> }
>>
>> int main()
>> {
>>   u32 P = (u32)H_Hat;
>>   Halts(P, P);
>>   HALT;
>> }
>>
> That's just asking for confusion, using H_Hat for two quite different 
> machines.
> 
> But... the two machines you show above DO have different calculations as 
> Richard was saying.  (I'm not sure if that's what you were trying to say.)
> 
> 
>>
>>>> On 11/25/2020 10:16 AM, Mike Terry wrote:
>>>>> ...any perceived "change of behaviour" as a
>>>>> result of the halt decider aborting its emulation
>>>>> is not actually behaviour of H_Hat, it's different
>>>>> emulator behaviour.
>>
>> Thus when Halts() decides to abort H_Hat it is the same H_Hat as the
>> H_Hat that DebugTrace(P, P) is merely emulating.
>>
> That's ridiculous - the emulations are not even looking at the same 
> machine, let alone the same calculation.  I don't think you understand 
> what I said at all.  (No wonder you sounded so uncharacteristically 
> happy when I said it!  Mystery explained...  :) )
> 
> I think I even put in a caveat that covered this exact scenario, because 
> I suspected you would want to misinterpret what I said in this way.  8-/
> 
> 
> Mike.
> [Wow, 20 chars!  Maybe a new record...]
> 

01 void H_Hat(u32 P)
02 {
03   u32 Aborted = DebugTrace(P, P);
04   if (Aborted)
05     HALT
06   else
07     HERE: goto HERE;
08 }

The H_Hat() that calls DebugTrace() is computationally identical to the 
H_Hat() that calls Halts() because neither one of them ever gets past 
line 03.

You are the only one that I know smart enough to see this. Ben would 
never say it if he did see it. Richard does not understand these things 
well enough to see this.



-- 


Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#1904 — Re: It is known that a correct halt decider must return false (in this case)[V2](ridiculous)

Fromolcott <NoOne@NoWhere.com>
Date2020-11-26 08:33 -0600
SubjectRe: It is known that a correct halt decider must return false (in this case)[V2](ridiculous)
Message-ID<IKmdnZkItY0jISLCnZ2dnUU7-RvNnZ2d@giganews.com>
In reply to#1901
On 11/26/2020 8:22 AM, Richard Damon wrote:
> On 11/25/20 11:30 PM, olcott wrote:
>>>
>>
>> 01 void H_Hat(u32 P)
>> 02 {
>> 03   u32 Aborted = DebugTrace(P, P);
>> 04   if (Aborted)
>> 05     HALT
>> 06   else
>> 07     HERE: goto HERE;
>> 08 }
>>
>> The H_Hat() that calls DebugTrace() is computationally identical to the
>> H_Hat() that calls Halts() because neither one of them ever gets past
>> line 03.
>>
>> You are the only one that I know smart enough to see this. Ben would
>> never say it if he did see it. Richard does not understand these things
>> well enough to see this.
>>
> 
> The only possible reason to NOT get past line 3 when calling Halts, (if
> Halts is supposed to be a proper halt detector), is because Halts is
> broken and doesn't meet its requirements.

I am probably going to stop responding to you because you do not have 
enough basic knowledge of things like infinite recursion to ever 
actually understand what I am saying.

It is ridiculous to assume that a function designed to detect Halting 
would be required rewrite the code that it is testing to remove the 
infinite recursion of this code.

> YOu may complain that that isn't what Halts is supposed to be in this
> example, but that is EXACTLY why I said you shouldn't use this naming style.
> 
> YOu have already been found 'Guilty' of trying to sneak in the comments
> about one version of a function to when it was being used as a different
> functions.
> 
> The use of obviously misleading names is a good sign that you are
> intentionally trying to pull a scam here.
> 


-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#1905 — Re: It is known that a correct halt decider must return false (in this case)[V2](ridiculous)

Fromolcott <NoOne@NoWhere.com>
Date2020-11-26 09:49 -0600
SubjectRe: It is known that a correct halt decider must return false (in this case)[V2](ridiculous)
Message-ID<lbWdnUyeSpQZUyLCnZ2dnUU7-RHNnZ2d@giganews.com>
In reply to#1904
On 11/26/2020 9:43 AM, Richard Damon wrote:
> On 11/26/20 9:33 AM, olcott wrote:
>> On 11/26/2020 8:22 AM, Richard Damon wrote:
>>> On 11/25/20 11:30 PM, olcott wrote:
>>>>>
>>>>
>>>> 01 void H_Hat(u32 P)
>>>> 02 {
>>>> 03   u32 Aborted = DebugTrace(P, P);
>>>> 04   if (Aborted)
>>>> 05     HALT
>>>> 06   else
>>>> 07     HERE: goto HERE;
>>>> 08 }
>>>>
>>>> The H_Hat() that calls DebugTrace() is computationally identical to the
>>>> H_Hat() that calls Halts() because neither one of them ever gets past
>>>> line 03.
>>>>
>>>> You are the only one that I know smart enough to see this. Ben would
>>>> never say it if he did see it. Richard does not understand these things
>>>> well enough to see this.
>>>>
>>>
>>> The only possible reason to NOT get past line 3 when calling Halts, (if
>>> Halts is supposed to be a proper halt detector), is because Halts is
>>> broken and doesn't meet its requirements.
>>
>> I am probably going to stop responding to you because you do not have
>> enough basic knowledge of things like infinite recursion to ever
>> actually understand what I am saying.
>>
>> It is ridiculous to assume that a function designed to detect Halting
>> would be required rewrite the code that it is testing to remove the
>> infinite recursion of this code.
>>
> 
> WHERE DO I SAY RE-WRITE CODE. Maybe the way you are implementing your
> halt detector is SO wrong that it has gotten itself into a jam, but then
> that is YOUR problem.
> 
When you expect Halts() to return a value to H_Hat() that is exactly the 
same as expecting DebugTrace() to return a value to H_Hat(), thus 
proving that you must be clueless about how infinite recursion works.


int DebugTrace(u32 P, u32 I)
{
   ((int(*)(int))P)(I);
   return 1;
}

void H_Hat(u32 P)
{
   u32 Aborted = DebugTrace(P, P);
   if (Aborted)
     HALT
   else
     HERE: goto HERE;
}

int main()
{
   u32 P = (u32)H_Hat;
   DebugTrace(P, P);
   HALT;
}

-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#1909 — Re: It is known that a correct halt decider must return false (in this case)[V2](whole solution)

Fromolcott <NoOne@NoWhere.com>
Date2020-11-26 11:50 -0600
SubjectRe: It is known that a correct halt decider must return false (in this case)[V2](whole solution)
Message-ID<ELGdnQFzyJJHdyLCnZ2dnUU7-XPNnZ2d@giganews.com>
In reply to#1905
On 11/26/2020 11:21 AM, Ben Bacarisse wrote:
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
> 
>> On Thursday, 26 November 2020 at 15:49:31 UTC, olcott wrote:
> <cut>
>>> int DebugTrace(u32 P, u32 I)
>>> {
>>> ((int(*)(int))P)(I);
>>> return 1;
>>> }
>>>
>>> void H_Hat(u32 P)
>>> {
>>> u32 Aborted = DebugTrace(P, P);
>>> if (Aborted)
>>> HALT
>>> else
>>> HERE: goto HERE;
>>> }
>>>
>>> int main()
>>> {
>>> u32 P = (u32)H_Hat;
>>> DebugTrace(P, P);
>>> HALT;
>>> }
> 
> (The indentation was lost before I replied, honest, guv.)
>   
>> That's infinite recusion, right enough.
>> But if Halts() detects the infinite recursion  and reports "Doesn't halt"
>> then it is no longer infinite recursion.
> 
> Which is the key to PO's halting problem 2.0.  A program is non-halting
> not because it doesn't halt, but because it wouldn't halt if weren't
> halted.  Simples!
> 

Every program / (TMD being simulated) that does not halt unless it is 
forced to halt is a non halting program / (TMD being simulated).

Every program / (TMD being simulated) that halts without being forced to 
halt is a halting program / (TMD being simulated).

Thus dividing inputs into halting and not halting as the actual Halting 
Problem itself requires.

The Halting problem is a problem in computer science. The problem is 
looking at a computer program and finding out if the program is going to 
run forever or not.  https://simple.wikipedia.org/wiki/Halting_problem


-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#1911 — Re: It is known that a correct halt decider must return false (in this case)[V2](whole solution)

Fromolcott <NoOne@NoWhere.com>
Date2020-11-26 12:41 -0600
SubjectRe: It is known that a correct halt decider must return false (in this case)[V2](whole solution)
Message-ID<wIudneo02KJXayLCnZ2dnUU7-YXNnZ2d@giganews.com>
In reply to#1909
On 11/26/2020 12:29 PM, Malcolm McLean wrote:
> On Thursday, 26 November 2020 at 17:50:26 UTC, olcott wrote:
>> On 11/26/2020 11:21 AM, Ben Bacarisse wrote:
>>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>>
>>>> On Thursday, 26 November 2020 at 15:49:31 UTC, olcott wrote:
>>> <cut>
>>>>> int DebugTrace(u32 P, u32 I)
>>>>> {
>>>>> ((int(*)(int))P)(I);
>>>>> return 1;
>>>>> }
>>>>>
>>>>> void H_Hat(u32 P)
>>>>> {
>>>>> u32 Aborted = DebugTrace(P, P);
>>>>> if (Aborted)
>>>>> HALT
>>>>> else
>>>>> HERE: goto HERE;
>>>>> }
>>>>>
>>>>> int main()
>>>>> {
>>>>> u32 P = (u32)H_Hat;
>>>>> DebugTrace(P, P);
>>>>> HALT;
>>>>> }
>>>
>>> (The indentation was lost before I replied, honest, guv.)
>>>
>>>> That's infinite recusion, right enough.
>>>> But if Halts() detects the infinite recursion and reports "Doesn't halt"
>>>> then it is no longer infinite recursion.
>>>
>>> Which is the key to PO's halting problem 2.0. A program is non-halting
>>> not because it doesn't halt, but because it wouldn't halt if weren't
>>> halted. Simples!
>>>
>> Every program / (TMD being simulated) that does not halt unless it is
>> forced to halt is a non halting program / (TMD being simulated).
>>
>> Every program / (TMD being simulated) that halts without being forced to
>> halt is a halting program / (TMD being simulated).
>>
> The point of the H_Hat proof is that "Halts()" is fed to itself. So if Halts() terminates
> what would otherwise be an infinite recursion, as it must do if it is to be a
> halt detector, the termination is also in the Halts() that is fed to Halts().
> 
> There's no way out. But I thought that had been agreed long ago.

Those words seem incoherent to me.

>>
>> Thus dividing inputs into halting and not halting as the actual Halting
>> Problem itself requires.
>>
>> The Halting problem is a problem in computer science. The problem is
>> looking at a computer program and finding out if the program is going to
>> run forever or not. https://simple.wikipedia.org/wiki/Halting_problem
>>
> You've been mislead by the term "halting problem". There are plenty  of
> genuinely open problems in computer science, like whether large integers can
> be factored other than by exhaustive search, or whether graphs can be laid
> out on two dimensional visual representations in polynomial time. The
> "halting problem", despite its name, is not one of these problems.
> 

     The input to H will be the description (encoded in some form)
     of M, say WM, as well as the input w. The requirement is then
     that, given any (WM, w), the Turing machine H will halt with
     either a yes or no answer.

     H.q0 wMw ⊢* H.yes   if M applied to w halts, and
     H.q0 wMw ⊢* H.no    if M applied to w would not halt.
     (Linz 1990:318)



-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#1912 — Re: It is known that a correct halt decider must return false (in this case)[V2](whole solution)

Fromolcott <NoOne@NoWhere.com>
Date2020-11-26 13:07 -0600
SubjectRe: It is known that a correct halt decider must return false (in this case)[V2](whole solution)
Message-ID<ycqdnZ03aq9uYSLCnZ2dnUU7-enNnZ2d@giganews.com>
In reply to#1911
On 11/26/2020 12:47 PM, Richard Damon wrote:
> On 11/26/20 1:41 PM, olcott wrote:
>> On 11/26/2020 12:29 PM, Malcolm McLean wrote:
>>> On Thursday, 26 November 2020 at 17:50:26 UTC, olcott wrote:
>>>> On 11/26/2020 11:21 AM, Ben Bacarisse wrote:
>>>>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>>>>
>>>>>> On Thursday, 26 November 2020 at 15:49:31 UTC, olcott wrote:
>>>>> <cut>
>>>>>>> int DebugTrace(u32 P, u32 I)
>>>>>>> {
>>>>>>> ((int(*)(int))P)(I);
>>>>>>> return 1;
>>>>>>> }
>>>>>>>
>>>>>>> void H_Hat(u32 P)
>>>>>>> {
>>>>>>> u32 Aborted = DebugTrace(P, P);
>>>>>>> if (Aborted)
>>>>>>> HALT
>>>>>>> else
>>>>>>> HERE: goto HERE;
>>>>>>> }
>>>>>>>
>>>>>>> int main()
>>>>>>> {
>>>>>>> u32 P = (u32)H_Hat;
>>>>>>> DebugTrace(P, P);
>>>>>>> HALT;
>>>>>>> }
>>>>>
>>>>> (The indentation was lost before I replied, honest, guv.)
>>>>>
>>>>>> That's infinite recusion, right enough.
>>>>>> But if Halts() detects the infinite recursion and reports "Doesn't
>>>>>> halt"
>>>>>> then it is no longer infinite recursion.
>>>>>
>>>>> Which is the key to PO's halting problem 2.0. A program is non-halting
>>>>> not because it doesn't halt, but because it wouldn't halt if weren't
>>>>> halted. Simples!
>>>>>
>>>> Every program / (TMD being simulated) that does not halt unless it is
>>>> forced to halt is a non halting program / (TMD being simulated).
>>>>
>>>> Every program / (TMD being simulated) that halts without being forced to
>>>> halt is a halting program / (TMD being simulated).
>>>>
>>> The point of the H_Hat proof is that "Halts()" is fed to itself. So if
>>> Halts() terminates
>>> what would otherwise be an infinite recursion, as it must do if it is
>>> to be a
>>> halt detector, the termination is also in the Halts() that is fed to
>>> Halts().
>>>
>>> There's no way out. But I thought that had been agreed long ago.
>>
>> Those words seem incoherent to me.
> 
> Sounds about right for you
>>
>>>>
>>>> Thus dividing inputs into halting and not halting as the actual Halting
>>>> Problem itself requires.
>>>>
>>>> The Halting problem is a problem in computer science. The problem is
>>>> looking at a computer program and finding out if the program is going to
>>>> run forever or not. https://simple.wikipedia.org/wiki/Halting_problem
>>>>
>>> You've been mislead by the term "halting problem". There are plenty  of
>>> genuinely open problems in computer science, like whether large
>>> integers can
>>> be factored other than by exhaustive search, or whether graphs can be
>>> laid
>>> out on two dimensional visual representations in polynomial time. The
>>> "halting problem", despite its name, is not one of these problems.
>>>
>>
>>      The input to H will be the description (encoded in some form)
>>      of M, say WM, as well as the input w. The requirement is then
>>      that, given any (WM, w), the Turing machine H will halt with
>>      either a yes or no answer.
>>
>>      H.q0 wMw ⊢* H.yes   if M applied to w halts, and
>>      H.q0 wMw ⊢* H.no    if M applied to w would not halt.
>>      (Linz 1990:318)
> 
> Yes, that is the statement of the Halting Problem, but Linz 'solved' it
> on one sense by showing that there was NO unversal solutions to the problem.
> 
> There can still be work on special cases, which don't need to be
> universal, but that is really a different sort of problem.
> 


(1) The code below is obviously infinitely recursive.

(2) Halts() has identical behavior to DebugStep() until Halts() decides 
to terminate its input.

∴ swapping function calls to Halts() for the two function calls to 
DebugStep() makes the function call to Halts() from H_Hat infinitely 
recursive.

∴ The decision of Halts() to abort H_Hat at its line 03 is necessarily a 
correct not halting decision.

int DebugTrace(u32 P, u32 I)
{
   ((int(*)(int))P)(I);
   return 1;
}

01 void H_Hat(u32 P)
02 {
03   u32 Aborted = DebugTrace(P, P);
04   if (Aborted)
05     HALT
06   else
07     HERE: goto HERE;
08 }

int main()
{
   u32 P = (u32)H_Hat;
   DebugTrace(P, P);
   HALT;
}








-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#1917 — Re: It is known that a correct halt decider must return false (in this case)[V2](whole solution)

Fromolcott <NoOne@NoWhere.com>
Date2020-11-26 15:12 -0600
SubjectRe: It is known that a correct halt decider must return false (in this case)[V2](whole solution)
Message-ID<bJmdnTaeTNnMh13CnZ2dnUU7-V_NnZ2d@giganews.com>
In reply to#1912
On 11/26/2020 3:02 PM, Richard Damon wrote:
> On 11/26/20 2:07 PM, olcott wrote:
>> On 11/26/2020 12:47 PM, Richard Damon wrote:
>>> On 11/26/20 1:41 PM, olcott wrote:
>>>> On 11/26/2020 12:29 PM, Malcolm McLean wrote:
>>>>> On Thursday, 26 November 2020 at 17:50:26 UTC, olcott wrote:
>>>>>> On 11/26/2020 11:21 AM, Ben Bacarisse wrote:
>>>>>>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>>>>>>
>>>>>>>> On Thursday, 26 November 2020 at 15:49:31 UTC, olcott wrote:
>>>>>>> <cut>
>>>>>>>>> int DebugTrace(u32 P, u32 I)
>>>>>>>>> {
>>>>>>>>> ((int(*)(int))P)(I);
>>>>>>>>> return 1;
>>>>>>>>> }
>>>>>>>>>
>>>>>>>>> void H_Hat(u32 P)
>>>>>>>>> {
>>>>>>>>> u32 Aborted = DebugTrace(P, P);
>>>>>>>>> if (Aborted)
>>>>>>>>> HALT
>>>>>>>>> else
>>>>>>>>> HERE: goto HERE;
>>>>>>>>> }
>>>>>>>>>
>>>>>>>>> int main()
>>>>>>>>> {
>>>>>>>>> u32 P = (u32)H_Hat;
>>>>>>>>> DebugTrace(P, P);
>>>>>>>>> HALT;
>>>>>>>>> }
>>>>>>>
>>>>>>> (The indentation was lost before I replied, honest, guv.)
>>>>>>>
>>>>>>>> That's infinite recusion, right enough.
>>>>>>>> But if Halts() detects the infinite recursion and reports "Doesn't
>>>>>>>> halt"
>>>>>>>> then it is no longer infinite recursion.
>>>>>>>
>>>>>>> Which is the key to PO's halting problem 2.0. A program is
>>>>>>> non-halting
>>>>>>> not because it doesn't halt, but because it wouldn't halt if weren't
>>>>>>> halted. Simples!
>>>>>>>
>>>>>> Every program / (TMD being simulated) that does not halt unless it is
>>>>>> forced to halt is a non halting program / (TMD being simulated).
>>>>>>
>>>>>> Every program / (TMD being simulated) that halts without being
>>>>>> forced to
>>>>>> halt is a halting program / (TMD being simulated).
>>>>>>
>>>>> The point of the H_Hat proof is that "Halts()" is fed to itself. So if
>>>>> Halts() terminates
>>>>> what would otherwise be an infinite recursion, as it must do if it is
>>>>> to be a
>>>>> halt detector, the termination is also in the Halts() that is fed to
>>>>> Halts().
>>>>>
>>>>> There's no way out. But I thought that had been agreed long ago.
>>>>
>>>> Those words seem incoherent to me.
>>>
>>> Sounds about right for you
>>>>
>>>>>>
>>>>>> Thus dividing inputs into halting and not halting as the actual
>>>>>> Halting
>>>>>> Problem itself requires.
>>>>>>
>>>>>> The Halting problem is a problem in computer science. The problem is
>>>>>> looking at a computer program and finding out if the program is
>>>>>> going to
>>>>>> run forever or not. https://simple.wikipedia.org/wiki/Halting_problem
>>>>>>
>>>>> You've been mislead by the term "halting problem". There are plenty  of
>>>>> genuinely open problems in computer science, like whether large
>>>>> integers can
>>>>> be factored other than by exhaustive search, or whether graphs can be
>>>>> laid
>>>>> out on two dimensional visual representations in polynomial time. The
>>>>> "halting problem", despite its name, is not one of these problems.
>>>>>
>>>>
>>>>       The input to H will be the description (encoded in some form)
>>>>       of M, say WM, as well as the input w. The requirement is then
>>>>       that, given any (WM, w), the Turing machine H will halt with
>>>>       either a yes or no answer.
>>>>
>>>>       H.q0 wMw ⊢* H.yes   if M applied to w halts, and
>>>>       H.q0 wMw ⊢* H.no    if M applied to w would not halt.
>>>>       (Linz 1990:318)
>>>
>>> Yes, that is the statement of the Halting Problem, but Linz 'solved' it
>>> on one sense by showing that there was NO unversal solutions to the
>>> problem.
>>>
>>> There can still be work on special cases, which don't need to be
>>> universal, but that is really a different sort of problem.
>>>
>>
>>
>> (1) The code below is obviously infinitely recursive.
> 
> Yes.
> 
>>
>> (2) Halts() has identical behavior to DebugStep() until Halts() decides
>> to terminate its input.
> 
> Ok. Does it promise to always work in finite time?
>>
>> ∴ swapping function calls to Halts() for the two function calls to
>> DebugStep() makes the function call to Halts() from H_Hat infinitely
>> recursive.>
>> ∴ The decision of Halts() to abort H_Hat at its line 03 is necessarily a
>> correct not halting decision.
>>
> 
> If its indication is that it found infinite recursion instead of
> claiming it has determined non-halting behavior, and it doesn't promise
> to always make its decision in fintie time, then depending on exactly
> what its indication is supposed to mean, it may be correct.
> 
> Halts does NOT meet the requirements of a classical halting detector.
Halts() does meet the requirements of a classical partial halt decider 
on input H_Hat.

> 
>> int DebugTrace(u32 P, u32 I)
>> {
>>    ((int(*)(int))P)(I);
>>    return 1;
>> }
>>
>> 01 void H_Hat(u32 P)
>> 02 {
>> 03   u32 Aborted = DebugTrace(P, P);
>> 04   if (Aborted)
>> 05     HALT
>> 06   else
>> 07     HERE: goto HERE;
>> 08 }
>>
>> int main()
>> {
>>    u32 P = (u32)H_Hat;
>>    DebugTrace(P, P);
>>    HALT;
>> }



-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#1920 — Re: It is known that a correct halt decider must return false (in this case)[V2](whole solution)

Fromolcott <NoOne@NoWhere.com>
Date2020-11-26 15:56 -0600
SubjectRe: It is known that a correct halt decider must return false (in this case)[V2](whole solution)
Message-ID<C42dnQ5NJ54SuV3CnZ2dnUU7-IHNnZ2d@giganews.com>
In reply to#1917
On 11/26/2020 3:42 PM, Malcolm McLean wrote:
> On Thursday, 26 November 2020 at 21:12:56 UTC, olcott wrote:
>>
>> Halts() does meet the requirements of a classical partial halt decider
>> on input H_Hat.
>>
> No it doesn't. Because Halts() is fed a copy of itself, then H_Hat inverts the
> result. There is no way round this. As I thought we agreed long ago.
> 

You may have thought you understood it you did not:

Any input (TMD / DATA) that would never halt unless its (UTM) stopped 
simulating it expresses behavior that is not halting behavior.

The invocation of Halts() on line 12 aborts the invocation of Halts() on 
line 03 because it specifies infinite recursion. Line 03 is aborted 
before it ever returns any value to H_Hat.

01 void H_Hat(u32 P)
02 {
03   u32 Aborted = Halts(P, P);
94   if (Aborted)
05     HALT
06   else
07     HERE: goto HERE;
08 }

09 int main()
10 {
11   u32 P = (u32)H_Hat;
12   Halts(P, P);
13   HALT;
14 }


-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.software-eng


csiph-web