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


Groups > comp.theory > #32496 > unrolled thread

Mutual agreement on the definition of a [computation] in computer science

Started byolcott <NoOne@NoWhere.com>
First post2021-05-01 11:30 -0500
Last post2021-05-02 21:46 +0100
Articles 20 on this page of 92 — 7 participants

Back to article view | Back to comp.theory


Contents

  Mutual agreement on the definition of a [computation] in computer science olcott <NoOne@NoWhere.com> - 2021-05-01 11:30 -0500
    Re: Mutual agreement on the definition of a [computation] in computer science olcott <NoOne@NoWhere.com> - 2021-05-01 11:37 -0500
      Re: Mutual agreement on the definition of a [computation] in computer science olcott <NoOne@NoWhere.com> - 2021-05-01 12:40 -0500
        Re: Mutual agreement on the definition of a [computation] in computer science Richard Damon <Richard@Damon-Family.org> - 2021-05-01 14:55 -0400
          Re: Mutual agreement on the definition of a [computation] in computer science olcott <NoOne@NoWhere.com> - 2021-05-01 14:09 -0500
            Re: Mutual agreement on the definition of a [computation] in computer science Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk> - 2021-05-01 22:42 +0100
              Re: Mutual agreement on the definition of a [computation] in computer science olcott <NoOne@NoWhere.com> - 2021-05-01 17:32 -0500
                Re: Mutual agreement on the definition of a [computation] in computer science Richard Damon <Richard@Damon-Family.org> - 2021-05-01 18:43 -0400
                  Re: Mutual agreement on the definition of a [computation] in computer science olcott <NoOne@NoWhere.com> - 2021-05-01 18:16 -0500
                    Re: Mutual agreement on the definition of a [computation] in computer science Richard Damon <Richard@Damon-Family.org> - 2021-05-01 21:20 -0400
                Re: Mutual agreement on the definition of a [computation] in computer science Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk> - 2021-05-02 00:49 +0100
            Re: Mutual agreement on the definition of a [computation] in computer science Richard Damon <Richard@Damon-Family.org> - 2021-05-01 18:02 -0400
              Re: Mutual agreement on the definition of a [computation] in computer science olcott <NoOne@NoWhere.com> - 2021-05-01 17:49 -0500
                Re: Mutual agreement on the definition of a [computation] in computer science André G. Isaak <agisaak@gm.invalid> - 2021-05-01 17:28 -0600
                  Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-01 18:42 -0500
                    Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-02 01:51 +0100
                      Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-01 20:05 -0500
                        Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-02 02:20 +0100
                          Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-01 20:42 -0500
                            Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-01 22:10 -0400
                            Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-02 03:30 +0100
                              Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-01 23:36 -0500
                                Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-02 07:51 -0400
                                Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-02 21:38 +0100
                                  Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-02 17:11 -0400
                                    Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-03 00:53 +0100
                                      Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-02 19:45 -0500
                                        Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-02 20:56 -0400
                                      Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-02 20:55 -0400
                                        Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-03 13:43 +0100
                                          Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-03 09:06 -0500
                                            Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-03 10:34 -0400
                                            Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-04 00:58 +0100
                                              Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-04 10:12 -0500
                                                Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-04 21:57 +0100
                                          Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Jeff Barnett <jbb@notatt.com> - 2021-05-03 11:39 -0600
                                  Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-02 17:41 -0500
                                    Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-03 00:52 +0100
                                      Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-02 19:34 -0500
                                        Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-02 20:49 -0400
                                        Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-03 17:23 +0100
                                          Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-03 14:00 -0500
                                            Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-03 15:23 -0400
                                              Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-04 09:53 -0500
                                                Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-04 11:21 -0400
                                                  Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-04 10:28 -0500
                                                    Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-04 11:40 -0400
                                                Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-04 17:11 +0100
                                                  Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-04 11:23 -0500
                                                    Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-04 12:40 -0400
                                                      Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-04 11:46 -0500
                                                        Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-04 13:17 -0400
                                                    Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-04 21:47 +0100
                                                      Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-04 17:31 -0400
                                                        Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-04 23:21 +0100
                                            Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-04 00:49 +0100
                                              Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-04 10:09 -0500
                                              Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-04 10:45 -0500
                                                Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-04 19:50 +0100
                                          Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-04 10:04 -0500
                                            Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-04 11:22 -0400
                                              Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-04 10:31 -0500
                                                Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-04 11:46 -0400
                                            Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-04 19:56 +0100
                                    Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-02 20:44 -0400
                            Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] André G. Isaak <agisaak@gm.invalid> - 2021-05-01 21:14 -0600
                              Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-02 00:04 -0500
                                Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] André G. Isaak <agisaak@gm.invalid> - 2021-05-01 23:27 -0600
                                  Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-02 12:47 -0500
                                    Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-02 14:38 -0400
                        Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-01 21:40 -0400
                    Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-01 21:35 -0400
                Re: Mutual agreement on the definition of a [computation] in computer science Richard Damon <Richard@Damon-Family.org> - 2021-05-01 21:29 -0400
      Re: Mutual agreement on the definition of a [computation] in computer science Richard Damon <Richard@Damon-Family.org> - 2021-05-01 14:49 -0400
        Re: Mutual agreement on the definition of a [computation] in computer science olcott <NoOne@NoWhere.com> - 2021-05-01 14:02 -0500
      Re: Mutual agreement on the definition of a [computation] in computer science Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-01 22:50 +0100
    Re: Mutual agreement on the definition of a [computation] in computer science Kaz Kylheku <563-365-8930@kylheku.com> - 2021-05-01 18:22 +0000
      Re: Mutual agreement on the definition of a [computation] in computer science olcott <NoOne@NoWhere.com> - 2021-05-01 13:35 -0500
    Re: Mutual agreement on the definition of a [computation] in computer science Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk> - 2021-05-01 22:39 +0100
    Re: Mutual agreement on the definition of a [computation] in computer science Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-01 22:49 +0100
      Re: Mutual agreement on the definition of a [computation] in computer science olcott <NoOne@NoWhere.com> - 2021-05-01 18:35 -0500
        Re: Mutual agreement on the definition of a [computation] in computer science Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-02 01:56 +0100
          Re: Mutual agreement on the definition of a [computation] in computer science olcott <NoOne@NoWhere.com> - 2021-05-01 20:22 -0500
            Re: Mutual agreement on the definition of a [computation] in computer science Richard Damon <Richard@Damon-Family.org> - 2021-05-01 21:45 -0400
            Re: Mutual agreement on the definition of a [computation] in computer science Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-02 02:53 +0100
              Re: Mutual agreement on the definition of a [computation] in computer science olcott <NoOne@NoWhere.com> - 2021-05-01 23:55 -0500
                Re: Mutual agreement on the definition of a [computation] in computer science André G. Isaak <agisaak@gm.invalid> - 2021-05-01 23:07 -0600
                Re: Mutual agreement on the definition of a [computation] in computer science Richard Damon <Richard@Damon-Family.org> - 2021-05-02 08:10 -0400
                Re: Mutual agreement on the definition of a [computation] in computer science Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-02 20:29 +0100
                  Re: Mutual agreement on the definition of a [computation] in computer science olcott <NoOne@NoWhere.com> - 2021-05-02 14:34 -0500
                    Re: Mutual agreement on the definition of a [computation] in computer science Richard Damon <Richard@Damon-Family.org> - 2021-05-02 15:48 -0400
                    Re: Mutual agreement on the definition of a [computation] in computer science Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-02 21:46 +0100

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


#32673 — Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]

FromRichard Damon <Richard@Damon-Family.org>
Date2021-05-04 11:22 -0400
SubjectRe: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]
Message-ID<jFdkI.174786$N_4.56181@fx36.iad>
In reply to#32669
On 5/4/21 11:04 AM, olcott wrote:
> On 5/3/2021 11:23 AM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/2/2021 6:52 PM, Ben Bacarisse wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 5/2/2021 3:38 PM, Ben Bacarisse wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>
>>>>>>> On 5/1/2021 9:30 PM, Ben Bacarisse wrote:
>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>
>>>>>>>>> On 5/1/2021 8:20 PM, Ben Bacarisse wrote:
>>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>>
>>>>>>>>>>> On 5/1/2021 7:51 PM, Ben Bacarisse wrote:
>>>>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>>>>
>>>>>>>>>>>>> No H_Hat() in the universe ever stops running unless its
>>>>>>>>>>>>> otherwise
>>>>>>>>>>>>> infinite recursion is aborted at some point.
>>>>>>>>>>>>
>>>>>>>>>>>> This is just a silly word game.  What a computation would do
>>>>>>>>>>>> "otherwise"
>>>>>>>>>>>> is irrelevant.  H_Hat(H_Hat) is finite and it does not
>>>>>>>>>>>> matter how or
>>>>>>>>>>>> why.  It is a finite computation, and should be reported as
>>>>>>>>>>>> such.
>>>>>>>>>>>
>>>>>>>>>>> So in other words you believe that it is ridiculous for
>>>>>>>>>>> anyone to ever
>>>>>>>>>>> consider defining a partial halt decider because everyone
>>>>>>>>>>> agrees that
>>>>>>>>>>> is cannot be done perfectly so why bother doing this at all.
>>>>>>>>>>
>>>>>>>>>> No.  I am saying that your wording is silly because it
>>>>>>>>>> attempts to
>>>>>>>>>> justify the wrong answer using another, different, computation.
>>>>>>>>>> H_Hat(H_Hat) is finite.
>>>>>>>>
>>>>>>>> I see you don't dispute these facts.
>>>>>>
>>>>>> Good to see these facts confirmed by you once again.  If you dispute
>>>>>> that you justify giving the wrong answer using another related
>>>>>> computation, all you need to do is say so (and correct the record
>>>>>> where
>>>>>> you say that Halts(H_Hat, H_Hat) is false, but the arguments to Halts
>>>>>> denote a finite computation).
>>>>
>>>> I think we can safely assume that you do not want to dispute any of
>>>> these facts.
>>
>> All the smoke you are trying to blow below can not detract from this end
>> result.  You are stupidly trying to get away with the wrong answer.
>>
>>>>>>>>> The above criteria does correctly decide infinite recursion.
>>>>>>>>
>>>>>>>> What has this got to do with the computation H_Hat(H_Hat) (the
>>>>>>>> real one,
>>>>>>>> not the one you posted recently to poison the well)?  It calls no
>>>>>>>> functions that call H_Hat.  In the world of C and x86 code, that
>>>>>>>> means
>>>>>>>> it is not recursive at all.
>>>>>>
>>>>>>>> You ignored the key facts I put to you.  These were facts that
>>>>>>>> you told
>>>>>>>> me so you are stuck with them until you correct the record.
>>>>>>>
>>>>>>> The key fact is that every time H_Hat() calls Halts() it meets the
>>>>>>> above criteria of infinite recursion, you can dodge this fact but
>>>>>>> you
>>>>>>> cannot correctly refute this fact.
>>>>>>
>>>>>> I am not dodging it -- I am telling you it's a lie.
>>>>>
>>>>> You can even tell me that it is a lie, what you cannot do is prove
>>>>> that it is false.
>>>>
>>>> I don't know what that means.  I take what you say about the trace at
>>>> face value because I don't want to look at it without knowing what's
>>>> being traced.  You appear to be suggesting that the trace shows
>>>> recursive calls where there should be none.  I am happy to be corrected
>>>> on this point.  Does the trace show infinite nested simulations
>>>> instead?
>>>
>>> Since the halt deciding criteria that matches infinite recursion is
>>> exactly the same as the criteria that matches infinite nested
>>> simulations and infinite nested simulations are computationally
>>> equivalent to infinite recursion I can them both infinite recursion.
>>
>> I /think/ this means that you now know you used the wrong words but you
>> were not trying to mislead anyone.  Is that about it?
>>
>>>>>> I started out being
>>>>>> polite and technical, but it amounts to the same thing: if the trace
>>>>>> shows recursion, it is a fake.
>>>>>
>>>>> void H_Hat2(u32 P)
>>>>> {
>>>>>     u32 Input_Would_Halt = Simulate(P, P);
>>>>> }
>>>>>
>>>>> int main()
>>>>> {
>>>>>     u32 Input_Would_Halt = Halts((u32)H_Hat2, (u32)H_Hat2);
>>>>> }
>>>>>
>>>>> In other words you are saying that the above is not computationally
>>>>> equivalent to infinite recursion.
>>>>
>>>> What a mess.  More code missing in action.  More odd phrases.  My best
>>>> guess at what "computationally equivalent to infinite recursion" means
>>>> is simply any non-finite computation.
>>>
>>> It is a specific dynamic behavior pattern that the halt decider has
>>> matched. It only distinguishes between infinite recursion and infinite
>>> loops.
>>
>> In the case that matters, Halts(H_Hat, H_Hat), (when Halts gets the
>> answer wrong) Halts again detects something "computationally equivalent
>> to infinite recursion" but the arguments to Halts denote a finite
>> computation do they not?
> Halts(H_Hat, H_Hat) correctly decides not halting on the basis that
> H_Hat(H_Hat) matches the [infinite recursion]** dynamic behavior pattern.
> 
> An infinite loop is correctly decided to specify non halting behavior on
> the basis that it matches the [infinite loop] dynamic behavior pattern.
> The fact that it does halt because the halt decider forced it to halt
> does not change this.

Correction, INcorrectly decided because it uses an INCORRECT and
UNPROVEN pattern

> 
> The fact that H_Hat() always matches the [infinite recursion]** dynamic
> behavior pattern (when it is executed with itself as input) is what
> makes the halt decider's decision correct. The fact that it does halt
> because the halt decider forced it to halt does not change this.
> 
> ** Also applies to infinitely nested simulations.
> 

H_Hat(H_Hat) halts because:

1) Halts is stipulated to meet the requirements of a Halt Decider for
Computation Theory, as used in the proof of Linz and Sipser.

2) Halts is stipulated to return non-Halting on Halts(H_Hat, H_Hat) when
asked directly.

3) H_Hat is stipulated to be built like Linz or Sipser, in that it will
halt when the Halt decider it is built on decides H_Hat’s input is
non-Halting on itself.

4) 1 Means that Halts is a Computation, and will always return the same
answer (or never return an answer) for a given input.

5) H_Hat(H_Hat) when run as a Machine will perform the Computation
Halts(H_Hat, H_Hat)

6) by 4 and 2, this means that Halts will return the decision on
non-halting to H_Hat

7) By 3, this means that H_Hat will Halt.


Find the error.

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


#32677 — Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]

Fromolcott <NoOne@NoWhere.com>
Date2021-05-04 10:31 -0500
SubjectRe: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]
Message-ID<cN-dnQm6K54o9Qz9nZ2dnUU7-ctQAAAA@giganews.com>
In reply to#32673
On 5/4/2021 10:22 AM, Richard Damon wrote:
> On 5/4/21 11:04 AM, olcott wrote:
>> On 5/3/2021 11:23 AM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/2/2021 6:52 PM, Ben Bacarisse wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> On 5/2/2021 3:38 PM, Ben Bacarisse wrote:
>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>
>>>>>>>> On 5/1/2021 9:30 PM, Ben Bacarisse wrote:
>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>
>>>>>>>>>> On 5/1/2021 8:20 PM, Ben Bacarisse wrote:
>>>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>>>
>>>>>>>>>>>> On 5/1/2021 7:51 PM, Ben Bacarisse wrote:
>>>>>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>>>>>
>>>>>>>>>>>>>> No H_Hat() in the universe ever stops running unless its
>>>>>>>>>>>>>> otherwise
>>>>>>>>>>>>>> infinite recursion is aborted at some point.
>>>>>>>>>>>>>
>>>>>>>>>>>>> This is just a silly word game.  What a computation would do
>>>>>>>>>>>>> "otherwise"
>>>>>>>>>>>>> is irrelevant.  H_Hat(H_Hat) is finite and it does not
>>>>>>>>>>>>> matter how or
>>>>>>>>>>>>> why.  It is a finite computation, and should be reported as
>>>>>>>>>>>>> such.
>>>>>>>>>>>>
>>>>>>>>>>>> So in other words you believe that it is ridiculous for
>>>>>>>>>>>> anyone to ever
>>>>>>>>>>>> consider defining a partial halt decider because everyone
>>>>>>>>>>>> agrees that
>>>>>>>>>>>> is cannot be done perfectly so why bother doing this at all.
>>>>>>>>>>>
>>>>>>>>>>> No.  I am saying that your wording is silly because it
>>>>>>>>>>> attempts to
>>>>>>>>>>> justify the wrong answer using another, different, computation.
>>>>>>>>>>> H_Hat(H_Hat) is finite.
>>>>>>>>>
>>>>>>>>> I see you don't dispute these facts.
>>>>>>>
>>>>>>> Good to see these facts confirmed by you once again.  If you dispute
>>>>>>> that you justify giving the wrong answer using another related
>>>>>>> computation, all you need to do is say so (and correct the record
>>>>>>> where
>>>>>>> you say that Halts(H_Hat, H_Hat) is false, but the arguments to Halts
>>>>>>> denote a finite computation).
>>>>>
>>>>> I think we can safely assume that you do not want to dispute any of
>>>>> these facts.
>>>
>>> All the smoke you are trying to blow below can not detract from this end
>>> result.  You are stupidly trying to get away with the wrong answer.
>>>
>>>>>>>>>> The above criteria does correctly decide infinite recursion.
>>>>>>>>>
>>>>>>>>> What has this got to do with the computation H_Hat(H_Hat) (the
>>>>>>>>> real one,
>>>>>>>>> not the one you posted recently to poison the well)?  It calls no
>>>>>>>>> functions that call H_Hat.  In the world of C and x86 code, that
>>>>>>>>> means
>>>>>>>>> it is not recursive at all.
>>>>>>>
>>>>>>>>> You ignored the key facts I put to you.  These were facts that
>>>>>>>>> you told
>>>>>>>>> me so you are stuck with them until you correct the record.
>>>>>>>>
>>>>>>>> The key fact is that every time H_Hat() calls Halts() it meets the
>>>>>>>> above criteria of infinite recursion, you can dodge this fact but
>>>>>>>> you
>>>>>>>> cannot correctly refute this fact.
>>>>>>>
>>>>>>> I am not dodging it -- I am telling you it's a lie.
>>>>>>
>>>>>> You can even tell me that it is a lie, what you cannot do is prove
>>>>>> that it is false.
>>>>>
>>>>> I don't know what that means.  I take what you say about the trace at
>>>>> face value because I don't want to look at it without knowing what's
>>>>> being traced.  You appear to be suggesting that the trace shows
>>>>> recursive calls where there should be none.  I am happy to be corrected
>>>>> on this point.  Does the trace show infinite nested simulations
>>>>> instead?
>>>>
>>>> Since the halt deciding criteria that matches infinite recursion is
>>>> exactly the same as the criteria that matches infinite nested
>>>> simulations and infinite nested simulations are computationally
>>>> equivalent to infinite recursion I can them both infinite recursion.
>>>
>>> I /think/ this means that you now know you used the wrong words but you
>>> were not trying to mislead anyone.  Is that about it?
>>>
>>>>>>> I started out being
>>>>>>> polite and technical, but it amounts to the same thing: if the trace
>>>>>>> shows recursion, it is a fake.
>>>>>>
>>>>>> void H_Hat2(u32 P)
>>>>>> {
>>>>>>      u32 Input_Would_Halt = Simulate(P, P);
>>>>>> }
>>>>>>
>>>>>> int main()
>>>>>> {
>>>>>>      u32 Input_Would_Halt = Halts((u32)H_Hat2, (u32)H_Hat2);
>>>>>> }
>>>>>>
>>>>>> In other words you are saying that the above is not computationally
>>>>>> equivalent to infinite recursion.
>>>>>
>>>>> What a mess.  More code missing in action.  More odd phrases.  My best
>>>>> guess at what "computationally equivalent to infinite recursion" means
>>>>> is simply any non-finite computation.
>>>>
>>>> It is a specific dynamic behavior pattern that the halt decider has
>>>> matched. It only distinguishes between infinite recursion and infinite
>>>> loops.
>>>
>>> In the case that matters, Halts(H_Hat, H_Hat), (when Halts gets the
>>> answer wrong) Halts again detects something "computationally equivalent
>>> to infinite recursion" but the arguments to Halts denote a finite
>>> computation do they not?
>> Halts(H_Hat, H_Hat) correctly decides not halting on the basis that
>> H_Hat(H_Hat) matches the [infinite recursion]** dynamic behavior pattern.
>>
>> An infinite loop is correctly decided to specify non halting behavior on
>> the basis that it matches the [infinite loop] dynamic behavior pattern.
>> The fact that it does halt because the halt decider forced it to halt
>> does not change this.
> 
> Correction, INcorrectly decided because it uses an INCORRECT and
> UNPROVEN pattern
> 


That is a woefully stupid thing to say because I never even provided the 
[Infinite Loop] dynamic behavior pattern. It is the woefully stupid 
things like this that cause me to ignore most of your posts.

-- 
Copyright 2021 Pete Olcott

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

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


#32681 — Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]

FromRichard Damon <Richard@Damon-Family.org>
Date2021-05-04 11:46 -0400
SubjectRe: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]
Message-ID<e%dkI.133190$Qf2.131201@fx38.iad>
In reply to#32677
On 5/4/21 11:31 AM, olcott wrote:
> On 5/4/2021 10:22 AM, Richard Damon wrote:
>> On 5/4/21 11:04 AM, olcott wrote:
>>> On 5/3/2021 11:23 AM, Ben Bacarisse wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 5/2/2021 6:52 PM, Ben Bacarisse wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>
>>>>>>> On 5/2/2021 3:38 PM, Ben Bacarisse wrote:
>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>
>>>>>>>>> On 5/1/2021 9:30 PM, Ben Bacarisse wrote:
>>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>>
>>>>>>>>>>> On 5/1/2021 8:20 PM, Ben Bacarisse wrote:
>>>>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>>>>
>>>>>>>>>>>>> On 5/1/2021 7:51 PM, Ben Bacarisse wrote:
>>>>>>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> No H_Hat() in the universe ever stops running unless its
>>>>>>>>>>>>>>> otherwise
>>>>>>>>>>>>>>> infinite recursion is aborted at some point.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> This is just a silly word game.  What a computation would do
>>>>>>>>>>>>>> "otherwise"
>>>>>>>>>>>>>> is irrelevant.  H_Hat(H_Hat) is finite and it does not
>>>>>>>>>>>>>> matter how or
>>>>>>>>>>>>>> why.  It is a finite computation, and should be reported as
>>>>>>>>>>>>>> such.
>>>>>>>>>>>>>
>>>>>>>>>>>>> So in other words you believe that it is ridiculous for
>>>>>>>>>>>>> anyone to ever
>>>>>>>>>>>>> consider defining a partial halt decider because everyone
>>>>>>>>>>>>> agrees that
>>>>>>>>>>>>> is cannot be done perfectly so why bother doing this at all.
>>>>>>>>>>>>
>>>>>>>>>>>> No.  I am saying that your wording is silly because it
>>>>>>>>>>>> attempts to
>>>>>>>>>>>> justify the wrong answer using another, different, computation.
>>>>>>>>>>>> H_Hat(H_Hat) is finite.
>>>>>>>>>>
>>>>>>>>>> I see you don't dispute these facts.
>>>>>>>>
>>>>>>>> Good to see these facts confirmed by you once again.  If you
>>>>>>>> dispute
>>>>>>>> that you justify giving the wrong answer using another related
>>>>>>>> computation, all you need to do is say so (and correct the record
>>>>>>>> where
>>>>>>>> you say that Halts(H_Hat, H_Hat) is false, but the arguments to
>>>>>>>> Halts
>>>>>>>> denote a finite computation).
>>>>>>
>>>>>> I think we can safely assume that you do not want to dispute any of
>>>>>> these facts.
>>>>
>>>> All the smoke you are trying to blow below can not detract from this
>>>> end
>>>> result.  You are stupidly trying to get away with the wrong answer.
>>>>
>>>>>>>>>>> The above criteria does correctly decide infinite recursion.
>>>>>>>>>>
>>>>>>>>>> What has this got to do with the computation H_Hat(H_Hat) (the
>>>>>>>>>> real one,
>>>>>>>>>> not the one you posted recently to poison the well)?  It calls no
>>>>>>>>>> functions that call H_Hat.  In the world of C and x86 code, that
>>>>>>>>>> means
>>>>>>>>>> it is not recursive at all.
>>>>>>>>
>>>>>>>>>> You ignored the key facts I put to you.  These were facts that
>>>>>>>>>> you told
>>>>>>>>>> me so you are stuck with them until you correct the record.
>>>>>>>>>
>>>>>>>>> The key fact is that every time H_Hat() calls Halts() it meets the
>>>>>>>>> above criteria of infinite recursion, you can dodge this fact but
>>>>>>>>> you
>>>>>>>>> cannot correctly refute this fact.
>>>>>>>>
>>>>>>>> I am not dodging it -- I am telling you it's a lie.
>>>>>>>
>>>>>>> You can even tell me that it is a lie, what you cannot do is prove
>>>>>>> that it is false.
>>>>>>
>>>>>> I don't know what that means.  I take what you say about the trace at
>>>>>> face value because I don't want to look at it without knowing what's
>>>>>> being traced.  You appear to be suggesting that the trace shows
>>>>>> recursive calls where there should be none.  I am happy to be
>>>>>> corrected
>>>>>> on this point.  Does the trace show infinite nested simulations
>>>>>> instead?
>>>>>
>>>>> Since the halt deciding criteria that matches infinite recursion is
>>>>> exactly the same as the criteria that matches infinite nested
>>>>> simulations and infinite nested simulations are computationally
>>>>> equivalent to infinite recursion I can them both infinite recursion.
>>>>
>>>> I /think/ this means that you now know you used the wrong words but you
>>>> were not trying to mislead anyone.  Is that about it?
>>>>
>>>>>>>> I started out being
>>>>>>>> polite and technical, but it amounts to the same thing: if the
>>>>>>>> trace
>>>>>>>> shows recursion, it is a fake.
>>>>>>>
>>>>>>> void H_Hat2(u32 P)
>>>>>>> {
>>>>>>>      u32 Input_Would_Halt = Simulate(P, P);
>>>>>>> }
>>>>>>>
>>>>>>> int main()
>>>>>>> {
>>>>>>>      u32 Input_Would_Halt = Halts((u32)H_Hat2, (u32)H_Hat2);
>>>>>>> }
>>>>>>>
>>>>>>> In other words you are saying that the above is not computationally
>>>>>>> equivalent to infinite recursion.
>>>>>>
>>>>>> What a mess.  More code missing in action.  More odd phrases.  My
>>>>>> best
>>>>>> guess at what "computationally equivalent to infinite recursion"
>>>>>> means
>>>>>> is simply any non-finite computation.
>>>>>
>>>>> It is a specific dynamic behavior pattern that the halt decider has
>>>>> matched. It only distinguishes between infinite recursion and infinite
>>>>> loops.
>>>>
>>>> In the case that matters, Halts(H_Hat, H_Hat), (when Halts gets the
>>>> answer wrong) Halts again detects something "computationally equivalent
>>>> to infinite recursion" but the arguments to Halts denote a finite
>>>> computation do they not?
>>> Halts(H_Hat, H_Hat) correctly decides not halting on the basis that
>>> H_Hat(H_Hat) matches the [infinite recursion]** dynamic behavior
>>> pattern.
>>>
>>> An infinite loop is correctly decided to specify non halting behavior on
>>> the basis that it matches the [infinite loop] dynamic behavior pattern.
>>> The fact that it does halt because the halt decider forced it to halt
>>> does not change this.
>>
>> Correction, INcorrectly decided because it uses an INCORRECT and
>> UNPROVEN pattern
>>
> 
> 
> That is a woefully stupid thing to say because I never even provided the
> [Infinite Loop] dynamic behavior pattern. It is the woefully stupid
> things like this that cause me to ignore most of your posts.
> 

If you give the arguemnt that A implies B, and it is known that not B is
true, then even without knowing A, I can say it is false.

Simple Logical deduction.

Also, you have at least described what you seem to be calling the
Infinite Loop pattern with your twisted arguments about Y() and X().

So you LIE if you say you haven't provided them, or you LIE when you say
you have presented evidence that it meets the pattern if you haven't
said it.

Here, let me give a go at this logic.

Olcott's arguement fits the pattern of stupidity.

Therefor Olcott's argument IS Stupid.

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


#32701 — Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-05-04 19:56 +0100
SubjectRe: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]
Message-ID<875yzy49b5.fsf@bsb.me.uk>
In reply to#32669
olcott <NoOne@NoWhere.com> writes:

> On 5/3/2021 11:23 AM, Ben Bacarisse wrote:

>> In the case that matters, Halts(H_Hat, H_Hat), (when Halts gets the
>> answer wrong) Halts again detects something "computationally equivalent
>> to infinite recursion" but the arguments to Halts denote a finite
>> computation do they not?

> Halts(H_Hat, H_Hat) correctly decides not halting on the basis that
> H_Hat(H_Hat) matches the [infinite recursion]** dynamic behavior
> pattern.

H_Hat(H_Hat) is a halting computation.  Halts(H_Hat, H_Hat) gives the
wrong answer.  What halts should be detecting is halting (or
non-halting) computations.

You can't make the wrong answer the right one by sheer force of flannel.

-- 
Ben.

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


#32601 — Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]

FromRichard Damon <Richard@Damon-Family.org>
Date2021-05-02 20:44 -0400
SubjectRe: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]
Message-ID<4IHjI.16129$8O4.1028@fx16.iad>
In reply to#32596
On 5/2/21 6:41 PM, olcott wrote:
> On 5/2/2021 3:38 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/1/2021 9:30 PM, Ben Bacarisse wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 5/1/2021 8:20 PM, Ben Bacarisse wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>
>>>>>>> On 5/1/2021 7:51 PM, Ben Bacarisse wrote:
>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>
>>>>>>>>> No H_Hat() in the universe ever stops running unless its otherwise
>>>>>>>>> infinite recursion is aborted at some point.
>>>>>>>>
>>>>>>>> This is just a silly word game.  What a computation would do
>>>>>>>> "otherwise"
>>>>>>>> is irrelevant.  H_Hat(H_Hat) is finite and it does not matter
>>>>>>>> how or
>>>>>>>> why.  It is a finite computation, and should be reported as such.
>>>>>>>
>>>>>>> So in other words you believe that it is ridiculous for anyone to
>>>>>>> ever
>>>>>>> consider defining a partial halt decider because everyone agrees
>>>>>>> that
>>>>>>> is cannot be done perfectly so why bother doing this at all.
>>>>>>
>>>>>> No.  I am saying that your wording is silly because it attempts to
>>>>>> justify the wrong answer using another, different, computation.
>>>>>> H_Hat(H_Hat) is finite.
>>>>
>>>> I see you don't dispute these facts.
>>
>> Good to see these facts confirmed by you once again.  If you dispute
>> that you justify giving the wrong answer using another related
>> computation, all you need to do is say so (and correct the record where
>> you say that Halts(H_Hat, H_Hat) is false, but the arguments to Halts
>> denote a finite computation).
>>
>>>>> The above criteria does correctly decide infinite recursion.
>>>>
>>>> What has this got to do with the computation H_Hat(H_Hat) (the real
>>>> one,
>>>> not the one you posted recently to poison the well)?  It calls no
>>>> functions that call H_Hat.  In the world of C and x86 code, that means
>>>> it is not recursive at all.
>>
>>>> You ignored the key facts I put to you.  These were facts that you told
>>>> me so you are stuck with them until you correct the record.
>>>
>>> The key fact is that every time H_Hat() calls Halts() it meets the
>>> above criteria of infinite recursion, you can dodge this fact but you
>>> cannot correctly refute this fact.
>>
>> I am not dodging it -- I am telling you it's a lie.  
> 
> You can even tell me that it is a lie, what you cannot do is prove that
> it is false.
> 
>> I started out being
>> polite and technical, but it amounts to the same thing: if the trace
>> shows recursion, it is a fake.  
> 
> 
> void H_Hat2(u32 P)
> {
>  u32 Input_Would_Halt = Simulate(P, P);
> }
> 
> int main()
> {
>  u32 Input_Would_Halt = Halts((u32)H_Hat2, (u32)H_Hat2);
> }
> 
> In other words you are saying that the above is not computationally
> equivalent to infinite recursion.

Since you have equivocated on the capability of Simulate, that even
Simulate might terminate an operation if it detects what it thinks is
infinite behavior, we really can't say what it will do. THAT is YOUR
fault for not sticking with the definition for functions.

Note, the phrase 'Computationally Equivalent to infinite recursion'
doesn't really make sense, since 'recursion' isn't one of the things
that Computational Equivalence describes (it only deals with the mapping
of inputs to outputs, and recursion isn't an output).

The closest you get is being Computationally Equivalent to a non-Halting
Computation.

> 
>> The only clue you have given us at to
>> what Halts does made it plain that there is no recursive call, so the
> 
> Computationally equivalent to a recursive call is you insistent on being
> so damned (condemned to Hell) nit picky.

Again, a non-sense term.
> 
>> trace you show is, as far anyone can tell, a fiction, a lie, published
> 
> It can be very easily verified as necessarily correct on the basis of
> the provided disassembled x86 code. The x86 source code proves that
> H_Hat() would do exactly what its execution trace shows that it does.

Except that the trace doesn't include all of the code executed under the
algorithm of H_Hat, since it doesn't show what happens in Halts when
H_Hat calls it.

That IS part of the algorithm of H_Hat, so needs to be analysed to see
what H_Hat does.

This is one of your flaws.

> 
>> in order to be able to show /something/ when you dare not show the code.
>> If the trace shows a recursive call, it does not comport with what you
>> have published about Halts and that makes one or other of those (the
>> sketch of Halts or the trace) a plain deception.
>>
> 
> I need not show the code of Halts(), anyone can understand that it is an
> x86 emulator that does correctly match certain dynamic patterns of non
> halting behavior on the basis of this paper:
> 
> http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf
> 

Except that when H_Hat calls it, its behavior is part of H_Hat, and as
such what it does can matter.

Without the actual code, all we can do is reason about it based on what
you have said. From that we can deduce that H_Hat will halt because:


1) Halts is stipulated to meet the requirements of a Halt Decider for
Computation Theory, as used in the proof of Linz and Sipser.

2) Halts is stipulated to return non-Halting on Halts(H_Hat, H_Hat) when
asked directly.

3) H_Hat is stipulated to be built like Linz or Sipser, in that it will
halt when the Halt decider it is built on decides H_Hat’s input is
non-Halting on itself.

4) 1 Means that Halts is a Computation, and will always return the same
answer (or never return an answer) for a given input.

5) H_Hat when run as a Machine will perform the Computation Halts(H_Hat,
H_Hat)

6) by 4 and 2, this means that Halts will return the decision on
non-halting to H_Hat

7) By 3, this means that H_Hat will Halt.

8) This means that H_Hat is a Halting Computation, and because of 2,
Halts is wrong.


And in fact, you have show a trace that shows exactly that:

On 4/27/21 12:55 AM, olcott wrote:
> void H_Hat(u32 P)
> {
>  u32 Input_Halts = Halts(P, P);
>  if (Input_Halts)
>    HERE: goto HERE;
> }
>
>
> int main()
> {
>  H_Hat((u32)H_Hat);
> }
>
>
> _H_Hat()
> [00000b98](01)  55                  	push ebp
> [00000b99](02)  8bec                	mov ebp,esp
> [00000b9b](01)  51                  	push ecx
> [00000b9c](03)  8b4508              	mov eax,[ebp+08]
> [00000b9f](01)  50                  	push eax
> [00000ba0](03)  8b4d08              	mov ecx,[ebp+08]
> [00000ba3](01)  51                  	push ecx
> [00000ba4](05)  e88ffdffff          	call 00000938
> [00000ba9](03)  83c408              	add esp,+08
> [00000bac](03)  8945fc              	mov [ebp-04],eax
> [00000baf](04)  837dfc00            	cmp dword [ebp-04],+00
> [00000bb3](02)  7402                	jz 00000bb7
> [00000bb5](02)  ebfe                	jmp 00000bb5
> [00000bb7](02)  8be5                	mov esp,ebp
> [00000bb9](01)  5d                  	pop ebp
> [00000bba](01)  c3                  	ret
> Size in bytes:(0035) [00000bba]
>
> _main()
> [00000bc8](01)  55                  	push ebp
> [00000bc9](02)  8bec                	mov ebp,esp
> [00000bcb](05)  68980b0000          	push 00000b98
> [00000bd0](05)  e8c3ffffff          	call 00000b98
> [00000bd5](03)  83c404              	add esp,+04
> [00000bd8](02)  33c0                	xor eax,eax
> [00000bda](01)  5d                  	pop ebp
> [00000bdb](01)  c3                  	ret
> Size in bytes:(0020) [00000bdb]
>
> ===============================
> ...[00000bc8][001015d4][00000000](01)  55                  	push ebp
> ...[00000bc9][001015d4][00000000](02)  8bec                	mov ebp,esp
> ...[00000bcb][001015d0][00000b98](05)  68980b0000          	push
> 00000b98
> ...[00000bd0][001015cc][00000bd5](05)  e8c3ffffff          	call
> 00000b98
> ...[00000b98][001015c8][001015d4](01)  55                  	push ebp
> ...[00000b99][001015c8][001015d4](02)  8bec                	mov ebp,esp
> ...[00000b9b][001015c4][00000000](01)  51                  	push ecx
> ...[00000b9c][001015c4][00000000](03)  8b4508              	mov
> eax,[ebp+08]
> ...[00000b9f][001015c0][00000b98](01)  50                  	push eax
> ...[00000ba0][001015c0][00000b98](03)  8b4d08              	mov
> ecx,[ebp+08]
> ...[00000ba3][001015bc][00000b98](01)  51                  	push ecx
> ...[00000ba4][001015b8][00000ba9](05)  e88ffdffff          	call
> 00000938
> Begin Local Halt Decider Simulation at Machine Address:b98
> ...[00000b98][00211674][00211678](01)  55                  	push ebp
> ...[00000b99][00211674][00211678](02)  8bec                	mov ebp,esp
> ...[00000b9b][00211670][00201644](01)  51                  	push ecx
> ...[00000b9c][00211670][00201644](03)  8b4508              	mov
> eax,[ebp+08]
> ...[00000b9f][0021166c][00000b98](01)  50                  	push eax
> ...[00000ba0][0021166c][00000b98](03)  8b4d08              	mov
> ecx,[ebp+08]
> ...[00000ba3][00211668][00000b98](01)  51                  	push ecx
> ...[00000ba4][00211664][00000ba9](05)  e88ffdffff          	call
> 00000938
> ...[00000b98][0025c09c][0025c0a0](01)  55                  	push ebp
> ...[00000b99][0025c09c][0025c0a0](02)  8bec                	mov ebp,esp
> ...[00000b9b][0025c098][0024c06c](01)  51                  	push ecx
> ...[00000b9c][0025c098][0024c06c](03)  8b4508              	mov
> eax,[ebp+08]
> ...[00000b9f][0025c094][00000b98](01)  50                  	push eax
> ...[00000ba0][0025c094][00000b98](03)  8b4d08              	mov
> ecx,[ebp+08]
> ...[00000ba3][0025c090][00000b98](01)  51                  	push ecx
> ...[00000ba4][0025c08c][00000ba9](05)  e88ffdffff          	call
> 00000938
> Local Halt Decider: Infinite Recursion Detected Simulation Stopped
> ...[00000ba9][001015c4][00000000](03)  83c408              	add esp,+08
> ...[00000bac][001015c4][00000000](03)  8945fc              	mov
> [ebp-04],eax
> ...[00000baf][001015c4][00000000](04)  837dfc00            	cmp dword
> [ebp-04],+00
> ...[00000bb3][001015c4][00000000](02)  7402                	jz 00000bb7
> ...[00000bb7][001015c8][001015d4](02)  8be5                	mov esp,ebp
> ...[00000bb9][001015cc][00000bd5](01)  5d                  	pop ebp
> ...[00000bba][001015d0][00000b98](01)  c3                  	ret
> ...[00000bd5][001015d4][00000000](03)  83c404              	add esp,+04
> ...[00000bd8][001015d4][00000000](02)  33c0                	xor eax,eax
> ...[00000bda][001015d8][00100000](01)  5d                  	pop ebp
> ...[00000bdb][001015dc][00000098](01)  c3                  	ret
> Number_of_User_Instructions(39)
> Number of Instructions Executed(26567)
>

So despite your claims that it must be non-Halting for various
argumentes, it is also clearly halting by simple proof and by your own
demonstration.

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


#32552 — Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]

FromAndré G. Isaak <agisaak@gm.invalid>
Date2021-05-01 21:14 -0600
SubjectRe: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]
Message-ID<s6l5ei$il3$1@dont-email.me>
In reply to#32546
On 2021-05-01 19:42, olcott wrote:
> On 5/1/2021 8:20 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/1/2021 7:51 PM, Ben Bacarisse wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> No H_Hat() in the universe ever stops running unless its otherwise
>>>>> infinite recursion is aborted at some point.
>>>>
>>>> This is just a silly word game.  What a computation would do 
>>>> "otherwise"
>>>> is irrelevant.  H_Hat(H_Hat) is finite and it does not matter how or
>>>> why.  It is a finite computation, and should be reported as such.
>>>
>>> So in other words you believe that it is ridiculous for anyone to ever
>>> consider defining a partial halt decider because everyone agrees that
>>> is cannot be done perfectly so why bother doing this at all.
>>
>> No.  I am saying that your wording is silly because it attempts to
>> justify the wrong answer using another, different, computation.
>> H_Hat(H_Hat) is finite. 
> 
> If the execution trace of function X() called by function Y() shows:
> (1) Function X() is called twice in sequence from the same machine 
> address of Y().

This part you really need to elaborate on. H_Hat(X) calls Halts(X, X), 
which then emulates X(X) based on the description of X which it has been 
passed. How does Halts determine whether that X describes 'the same' 
function as one previously called? i.e. how does it figure out that X is 
a description of H_Hat?

André

> (2) With the same parameters to X().
> (3) With no conditional branch or indexed jump instructions in Y().
> (4) With no function call returns from X().
> then the function call from Y() to X() is infinitely recursive.
> 
> The above criteria does correctly decide infinite recursion.
> The above criteria does correctly decide infinite recursion.
> The above criteria does correctly decide infinite recursion.
> 
> Every call from H_Hat() to Halts() meets this criteria.
> Every call from H_Hat() to Halts() meets this criteria.
> Every call from H_Hat() to Halts() meets this criteria.
> 
> Ignoring this key fact is no form of correct rebuttal.
> Ignoring this key fact is no form of correct rebuttal.
> Ignoring this key fact is no form of correct rebuttal.
> 
>> Halts(H_Hat, H_Hat) should be true, but you
>> have written Halts so that it's false and you justify that wrong answer
>> by what would happen were things not as they are.  It's flagrant
>> silliness.
> 
>> When you find yourself starting off "So in other words you believe..."
>> you should stop and ask yourself, "what point am I trying to avoid by
>> putting words into my interlocutor's mount?".
>>
> 
> 


-- 
To email remove 'invalid' & replace 'gm' with well known Google mail 
service.

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


#32555 — Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]

Fromolcott <NoOne@NoWhere.com>
Date2021-05-02 00:04 -0500
SubjectRe: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]
Message-ID<f9adncB8zpRKrxP9nZ2dnUU7-I3NnZ2d@giganews.com>
In reply to#32552
On 5/1/2021 10:14 PM, André G. Isaak wrote:
> On 2021-05-01 19:42, olcott wrote:
>> On 5/1/2021 8:20 PM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/1/2021 7:51 PM, Ben Bacarisse wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> No H_Hat() in the universe ever stops running unless its otherwise
>>>>>> infinite recursion is aborted at some point.
>>>>>
>>>>> This is just a silly word game.  What a computation would do 
>>>>> "otherwise"
>>>>> is irrelevant.  H_Hat(H_Hat) is finite and it does not matter how or
>>>>> why.  It is a finite computation, and should be reported as such.
>>>>
>>>> So in other words you believe that it is ridiculous for anyone to ever
>>>> consider defining a partial halt decider because everyone agrees that
>>>> is cannot be done perfectly so why bother doing this at all.
>>>
>>> No.  I am saying that your wording is silly because it attempts to
>>> justify the wrong answer using another, different, computation.
>>> H_Hat(H_Hat) is finite. 
>>
>> If the execution trace of function X() called by function Y() shows:
>> (1) Function X() is called twice in sequence from the same machine 
>> address of Y().
> 

If the execution trace of function H_Hat() calling function Halts() shows:
(1) Function Halts() is called twice in sequence from the same machine 
address of H_Hat().
(2) With the same parameters to Halts().
(3) With no conditional branch or indexed jump instructions in H_Hat().
(4) With no function call returns from Halts().
then the function call from H_Hat() to Halts() is infinitely recursive.


_H_Hat()
[00000adb](01)  55                      push ebp
[00000adc](02)  8bec                    mov ebp,esp
[00000ade](01)  51                      push ecx
[00000adf](03)  8b4508                  mov eax,[ebp+08]
[00000ae2](01)  50                      push eax
[00000ae3](03)  8b4d08                  mov ecx,[ebp+08]
[00000ae6](01)  51                      push ecx
[00000ae7](05)  e85ffeffff              call 0000094b
[00000aec](03)  83c408                  add esp,+08
[00000aef](03)  8945fc                  mov [ebp-04],eax
[00000af2](02)  8be5                    mov esp,ebp
[00000af4](01)  5d                      pop ebp
[00000af5](01)  c3                      ret
Size in bytes:(0027) [00000af5]

Begin Local Halt Decider Simulation at Machine Address:adb
...[00000adb][0021158c][00211590](01)  55                      push ebp
...[00000adc][0021158c][00211590](02)  8bec                    mov ebp,esp
...[00000ade][00211588][0020155c](01)  51                      push ecx
...[00000adf][00211588][0020155c](03)  8b4508                  mov 
eax,[ebp+08]
...[00000ae2][00211584][00000adb](01)  50                      push eax
...[00000ae3][00211584][00000adb](03)  8b4d08                  mov 
ecx,[ebp+08]
...[00000ae6][00211580][00000adb](01)  51                      push ecx
...[00000ae7][0021157c][00000aec](05)  e85ffeffff              call 0000094b
...[00000adb][0025bfb4][0025bfb8](01)  55                      push ebp
...[00000adc][0025bfb4][0025bfb8](02)  8bec                    mov ebp,esp
...[00000ade][0025bfb0][0024bf84](01)  51                      push ecx
...[00000adf][0025bfb0][0024bf84](03)  8b4508                  mov 
eax,[ebp+08]
...[00000ae2][0025bfac][00000adb](01)  50                      push eax
...[00000ae3][0025bfac][00000adb](03)  8b4d08                  mov 
ecx,[ebp+08]
...[00000ae6][0025bfa8][00000adb](01)  51                      push ecx
...[00000ae7][0025bfa4][00000aec](05)  e85ffeffff              call 0000094b
Local Halt Decider: Infinite Recursion Detected Simulation Stopped


> This part you really need to elaborate on. H_Hat(X) calls Halts(X, X), 
> which then emulates X(X) based on the description of X which it has been 
> passed. How does Halts determine whether that X describes 'the same' 
> function as one previously called? i.e. how does it figure out that X is 
> a description of H_Hat?
> 
> André
> 
>> (2) With the same parameters to X().
>> (3) With no conditional branch or indexed jump instructions in Y().
>> (4) With no function call returns from X().
>> then the function call from Y() to X() is infinitely recursive.
>>
>> The above criteria does correctly decide infinite recursion.
>> The above criteria does correctly decide infinite recursion.
>> The above criteria does correctly decide infinite recursion.
>>
>> Every call from H_Hat() to Halts() meets this criteria.
>> Every call from H_Hat() to Halts() meets this criteria.
>> Every call from H_Hat() to Halts() meets this criteria.
>>
>> Ignoring this key fact is no form of correct rebuttal.
>> Ignoring this key fact is no form of correct rebuttal.
>> Ignoring this key fact is no form of correct rebuttal.
>>
>>> Halts(H_Hat, H_Hat) should be true, but you
>>> have written Halts so that it's false and you justify that wrong answer
>>> by what would happen were things not as they are.  It's flagrant
>>> silliness.
>>
>>> When you find yourself starting off "So in other words you believe..."
>>> you should stop and ask yourself, "what point am I trying to avoid by
>>> putting words into my interlocutor's mount?".
>>>
>>
>>
> 
> 


-- 
Copyright 2021 Pete Olcott

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

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


#32557 — Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]

FromAndré G. Isaak <agisaak@gm.invalid>
Date2021-05-01 23:27 -0600
SubjectRe: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]
Message-ID<s6ld88$lr6$1@dont-email.me>
In reply to#32555
On 2021-05-01 23:04, olcott wrote:
> On 5/1/2021 10:14 PM, André G. Isaak wrote:
>> On 2021-05-01 19:42, olcott wrote:
>>> On 5/1/2021 8:20 PM, Ben Bacarisse wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 5/1/2021 7:51 PM, Ben Bacarisse wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>
>>>>>>> No H_Hat() in the universe ever stops running unless its otherwise
>>>>>>> infinite recursion is aborted at some point.
>>>>>>
>>>>>> This is just a silly word game.  What a computation would do 
>>>>>> "otherwise"
>>>>>> is irrelevant.  H_Hat(H_Hat) is finite and it does not matter how or
>>>>>> why.  It is a finite computation, and should be reported as such.
>>>>>
>>>>> So in other words you believe that it is ridiculous for anyone to ever
>>>>> consider defining a partial halt decider because everyone agrees that
>>>>> is cannot be done perfectly so why bother doing this at all.
>>>>
>>>> No.  I am saying that your wording is silly because it attempts to
>>>> justify the wrong answer using another, different, computation.
>>>> H_Hat(H_Hat) is finite. 
>>>
>>> If the execution trace of function X() called by function Y() shows:
>>> (1) Function X() is called twice in sequence from the same machine 
>>> address of Y().
>>
> 
> If the execution trace of function H_Hat() calling function Halts() shows:
> (1) Function Halts() is called twice in sequence from the same machine 
> address of H_Hat().

But Halts() is *emulating* H_Hat. That means that the 'call' to Halts 
inside H_Hat is also being emulated. It isn't an actual call.

So how does Halts() determine that the routine which it is emulating 
inside H_Hat is a call to Halts() as opposed to something else?

In the past you've said that you do this based on addresses, but an 
emulator should have an entirely separate (emulated) address space from 
code which is actually being executed. Furthermore, you've said your 
machine descriptions are in COFF files. A COFF file doesn't indicate 
*where* in memory a particular piece of code should be placed. So how 
does the emulator decide that a particular piece of code should be given 
the same (emulated) address as the (actual) address of Halts()?

André

> (2) With the same parameters to Halts().
> (3) With no conditional branch or indexed jump instructions in H_Hat().
> (4) With no function call returns from Halts().
> then the function call from H_Hat() to Halts() is infinitely recursive.
> 
> 
> _H_Hat()
> [00000adb](01)  55                      push ebp
> [00000adc](02)  8bec                    mov ebp,esp
> [00000ade](01)  51                      push ecx
> [00000adf](03)  8b4508                  mov eax,[ebp+08]
> [00000ae2](01)  50                      push eax
> [00000ae3](03)  8b4d08                  mov ecx,[ebp+08]
> [00000ae6](01)  51                      push ecx
> [00000ae7](05)  e85ffeffff              call 0000094b
> [00000aec](03)  83c408                  add esp,+08
> [00000aef](03)  8945fc                  mov [ebp-04],eax
> [00000af2](02)  8be5                    mov esp,ebp
> [00000af4](01)  5d                      pop ebp
> [00000af5](01)  c3                      ret
> Size in bytes:(0027) [00000af5]
> 
> Begin Local Halt Decider Simulation at Machine Address:adb
> ...[00000adb][0021158c][00211590](01)  55                      push ebp
> ...[00000adc][0021158c][00211590](02)  8bec                    mov ebp,esp
> ...[00000ade][00211588][0020155c](01)  51                      push ecx
> ...[00000adf][00211588][0020155c](03)  8b4508                  mov 
> eax,[ebp+08]
> ...[00000ae2][00211584][00000adb](01)  50                      push eax
> ...[00000ae3][00211584][00000adb](03)  8b4d08                  mov 
> ecx,[ebp+08]
> ...[00000ae6][00211580][00000adb](01)  51                      push ecx
> ...[00000ae7][0021157c][00000aec](05)  e85ffeffff              call 
> 0000094b
> ...[00000adb][0025bfb4][0025bfb8](01)  55                      push ebp
> ...[00000adc][0025bfb4][0025bfb8](02)  8bec                    mov ebp,esp
> ...[00000ade][0025bfb0][0024bf84](01)  51                      push ecx
> ...[00000adf][0025bfb0][0024bf84](03)  8b4508                  mov 
> eax,[ebp+08]
> ...[00000ae2][0025bfac][00000adb](01)  50                      push eax
> ...[00000ae3][0025bfac][00000adb](03)  8b4d08                  mov 
> ecx,[ebp+08]
> ...[00000ae6][0025bfa8][00000adb](01)  51                      push ecx
> ...[00000ae7][0025bfa4][00000aec](05)  e85ffeffff              call 
> 0000094b
> Local Halt Decider: Infinite Recursion Detected Simulation Stopped
> 
> 
>> This part you really need to elaborate on. H_Hat(X) calls Halts(X, X), 
>> which then emulates X(X) based on the description of X which it has 
>> been passed. How does Halts determine whether that X describes 'the 
>> same' function as one previously called? i.e. how does it figure out 
>> that X is a description of H_Hat?
>>
>> André
>>
>>> (2) With the same parameters to X().
>>> (3) With no conditional branch or indexed jump instructions in Y().
>>> (4) With no function call returns from X().
>>> then the function call from Y() to X() is infinitely recursive.
>>>
>>> The above criteria does correctly decide infinite recursion.
>>> The above criteria does correctly decide infinite recursion.
>>> The above criteria does correctly decide infinite recursion.
>>>
>>> Every call from H_Hat() to Halts() meets this criteria.
>>> Every call from H_Hat() to Halts() meets this criteria.
>>> Every call from H_Hat() to Halts() meets this criteria.
>>>
>>> Ignoring this key fact is no form of correct rebuttal.
>>> Ignoring this key fact is no form of correct rebuttal.
>>> Ignoring this key fact is no form of correct rebuttal.
>>>
>>>> Halts(H_Hat, H_Hat) should be true, but you
>>>> have written Halts so that it's false and you justify that wrong answer
>>>> by what would happen were things not as they are.  It's flagrant
>>>> silliness.
>>>
>>>> When you find yourself starting off "So in other words you believe..."
>>>> you should stop and ask yourself, "what point am I trying to avoid by
>>>> putting words into my interlocutor's mount?".
>>>>
>>>
>>>
>>
>>
> 
> 


-- 
To email remove 'invalid' & replace 'gm' with well known Google mail 
service.

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


#32576 — Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]

Fromolcott <NoOne@NoWhere.com>
Date2021-05-02 12:47 -0500
SubjectRe: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]
Message-ID<i8-dnYJ5wYsweBP9nZ2dnUU7-SHNnZ2d@giganews.com>
In reply to#32557
On 5/2/2021 12:27 AM, André G. Isaak wrote:
> On 2021-05-01 23:04, olcott wrote:
>> On 5/1/2021 10:14 PM, André G. Isaak wrote:
>>> On 2021-05-01 19:42, olcott wrote:
>>>> On 5/1/2021 8:20 PM, Ben Bacarisse wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> On 5/1/2021 7:51 PM, Ben Bacarisse wrote:
>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>
>>>>>>>> No H_Hat() in the universe ever stops running unless its otherwise
>>>>>>>> infinite recursion is aborted at some point.
>>>>>>>
>>>>>>> This is just a silly word game.  What a computation would do 
>>>>>>> "otherwise"
>>>>>>> is irrelevant.  H_Hat(H_Hat) is finite and it does not matter how or
>>>>>>> why.  It is a finite computation, and should be reported as such.
>>>>>>
>>>>>> So in other words you believe that it is ridiculous for anyone to 
>>>>>> ever
>>>>>> consider defining a partial halt decider because everyone agrees that
>>>>>> is cannot be done perfectly so why bother doing this at all.
>>>>>
>>>>> No.  I am saying that your wording is silly because it attempts to
>>>>> justify the wrong answer using another, different, computation.
>>>>> H_Hat(H_Hat) is finite. 
>>>>
>>>> If the execution trace of function X() called by function Y() shows:
>>>> (1) Function X() is called twice in sequence from the same machine 
>>>> address of Y().
>>>
>>
>> If the execution trace of function H_Hat() calling function Halts() 
>> shows:
>> (1) Function Halts() is called twice in sequence from the same machine 
>> address of H_Hat().
> 
> But Halts() is *emulating* H_Hat. That means that the 'call' to Halts 
> inside H_Hat is also being emulated. It isn't an actual call.
> 

It is computationally equivalent to a call.

> So how does Halts() determine that the routine which it is emulating 
> inside H_Hat is a call to Halts() as opposed to something else?
> 

It can do this on the basis of the machine address ranges.
It does not need to know this, it only needs to know that the infinite 
recursion criteria has been met.

> In the past you've said that you do this based on addresses, but an 
> emulator should have an entirely separate (emulated) address space from 
> code which is actually being executed. 

There is no actual need for this. The key element of the emulation is 
that the emulated execution of each instruction <is> a part of a single 
computation and the emulator is free to stop its emulation as soon as 
non-halting behavior criteria is met.

> Furthermore, you've said your 
> machine descriptions are in COFF files. A COFF file doesn't indicate 
> *where* in memory a particular piece of code should be placed. So how 

I just leave code where it already is in the COFF file.

//  This file reads a Microsoft COFF Object file and patches
//  all the otherwise relocatable data address references to
//  their actual physical file offsets.

> does the emulator decide that a particular piece of code should be given 
> the same (emulated) address as the (actual) address of Halts()?
> 

The executing x86 code knows nothing about names, it only deals with 
machine addresses. Every function has its own unique machine address as 
an offset in the COFF object file.

> André
> 
>> (2) With the same parameters to Halts().
>> (3) With no conditional branch or indexed jump instructions in H_Hat().
>> (4) With no function call returns from Halts().
>> then the function call from H_Hat() to Halts() is infinitely recursive.
>>
>>
>> _H_Hat()
>> [00000adb](01)  55                      push ebp
>> [00000adc](02)  8bec                    mov ebp,esp
>> [00000ade](01)  51                      push ecx
>> [00000adf](03)  8b4508                  mov eax,[ebp+08]
>> [00000ae2](01)  50                      push eax
>> [00000ae3](03)  8b4d08                  mov ecx,[ebp+08]
>> [00000ae6](01)  51                      push ecx

This is where Halts() is called with the machine address of H_Hat() 
having been pushed onto the stack in the prior two push instructions.

>> [00000ae7](05)  e85ffeffff              call 0000094b
>> [00000aec](03)  83c408                  add esp,+08
>> [00000aef](03)  8945fc                  mov [ebp-04],eax
>> [00000af2](02)  8be5                    mov esp,ebp
>> [00000af4](01)  5d                      pop ebp
>> [00000af5](01)  c3                      ret
>> Size in bytes:(0027) [00000af5]
>>
>> Begin Local Halt Decider Simulation at Machine Address:adb
>> ...[00000adb][0021158c][00211590](01)  55                      push ebp
>> ...[00000adc][0021158c][00211590](02)  8bec                    mov 
>> ebp,esp
>> ...[00000ade][00211588][0020155c](01)  51                      push ecx
>> ...[00000adf][00211588][0020155c](03)  8b4508                  mov 
>> eax,[ebp+08]
>> ...[00000ae2][00211584][00000adb](01)  50                      push eax
>> ...[00000ae3][00211584][00000adb](03)  8b4d08                  mov 
>> ecx,[ebp+08]
>> ...[00000ae6][00211580][00000adb](01)  51                      push ecx
>> ...[00000ae7][0021157c][00000aec](05)  e85ffeffff              call 
>> 0000094b
>> ...[00000adb][0025bfb4][0025bfb8](01)  55                      push ebp
>> ...[00000adc][0025bfb4][0025bfb8](02)  8bec                    mov 
>> ebp,esp
>> ...[00000ade][0025bfb0][0024bf84](01)  51                      push ecx
>> ...[00000adf][0025bfb0][0024bf84](03)  8b4508                  mov 
>> eax,[ebp+08]
>> ...[00000ae2][0025bfac][00000adb](01)  50                      push eax
>> ...[00000ae3][0025bfac][00000adb](03)  8b4d08                  mov 
>> ecx,[ebp+08]
>> ...[00000ae6][0025bfa8][00000adb](01)  51                      push ecx
>> ...[00000ae7][0025bfa4][00000aec](05)  e85ffeffff              call 
>> 0000094b
>> Local Halt Decider: Infinite Recursion Detected Simulation Stopped
>>
>>
>>> This part you really need to elaborate on. H_Hat(X) calls Halts(X, 
>>> X), which then emulates X(X) based on the description of X which it 
>>> has been passed. How does Halts determine whether that X describes 
>>> 'the same' function as one previously called? i.e. how does it figure 
>>> out that X is a description of H_Hat?
>>>
>>> André
>>>
>>>> (2) With the same parameters to X().
>>>> (3) With no conditional branch or indexed jump instructions in Y().
>>>> (4) With no function call returns from X().
>>>> then the function call from Y() to X() is infinitely recursive.
>>>>
>>>> The above criteria does correctly decide infinite recursion.
>>>> The above criteria does correctly decide infinite recursion.
>>>> The above criteria does correctly decide infinite recursion.
>>>>
>>>> Every call from H_Hat() to Halts() meets this criteria.
>>>> Every call from H_Hat() to Halts() meets this criteria.
>>>> Every call from H_Hat() to Halts() meets this criteria.
>>>>
>>>> Ignoring this key fact is no form of correct rebuttal.
>>>> Ignoring this key fact is no form of correct rebuttal.
>>>> Ignoring this key fact is no form of correct rebuttal.
>>>>
>>>>> Halts(H_Hat, H_Hat) should be true, but you
>>>>> have written Halts so that it's false and you justify that wrong 
>>>>> answer
>>>>> by what would happen were things not as they are.  It's flagrant
>>>>> silliness.
>>>>
>>>>> When you find yourself starting off "So in other words you believe..."
>>>>> you should stop and ask yourself, "what point am I trying to avoid by
>>>>> putting words into my interlocutor's mount?".
>>>>>
>>>>
>>>>
>>>
>>>
>>
>>
> 
> 


-- 
Copyright 2021 Pete Olcott

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

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


#32583 — Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]

FromRichard Damon <Richard@Damon-Family.org>
Date2021-05-02 14:38 -0400
SubjectRe: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]
Message-ID<okCjI.23562$ft1.12865@fx10.iad>
In reply to#32576
On 5/2/21 1:47 PM, olcott wrote:
> On 5/2/2021 12:27 AM, André G. Isaak wrote:
>> On 2021-05-01 23:04, olcott wrote:
>>> On 5/1/2021 10:14 PM, André G. Isaak wrote:
>>>> On 2021-05-01 19:42, olcott wrote:
>>>>> On 5/1/2021 8:20 PM, Ben Bacarisse wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>
>>>>>>> On 5/1/2021 7:51 PM, Ben Bacarisse wrote:
>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>
>>>>>>>>> No H_Hat() in the universe ever stops running unless its otherwise
>>>>>>>>> infinite recursion is aborted at some point.
>>>>>>>>
>>>>>>>> This is just a silly word game.  What a computation would do
>>>>>>>> "otherwise"
>>>>>>>> is irrelevant.  H_Hat(H_Hat) is finite and it does not matter
>>>>>>>> how or
>>>>>>>> why.  It is a finite computation, and should be reported as such.
>>>>>>>
>>>>>>> So in other words you believe that it is ridiculous for anyone to
>>>>>>> ever
>>>>>>> consider defining a partial halt decider because everyone agrees
>>>>>>> that
>>>>>>> is cannot be done perfectly so why bother doing this at all.
>>>>>>
>>>>>> No.  I am saying that your wording is silly because it attempts to
>>>>>> justify the wrong answer using another, different, computation.
>>>>>> H_Hat(H_Hat) is finite. 
>>>>>
>>>>> If the execution trace of function X() called by function Y() shows:
>>>>> (1) Function X() is called twice in sequence from the same machine
>>>>> address of Y().
>>>>
>>>
>>> If the execution trace of function H_Hat() calling function Halts()
>>> shows:
>>> (1) Function Halts() is called twice in sequence from the same
>>> machine address of H_Hat().
>>
>> But Halts() is *emulating* H_Hat. That means that the 'call' to Halts
>> inside H_Hat is also being emulated. It isn't an actual call.
>>
> 
> It is computationally equivalent to a call.

Error of category. Computationally Equivalence is a property of Full
Computatons, not individual machine instructions.

> 
>> So how does Halts() determine that the routine which it is emulating
>> inside H_Hat is a call to Halts() as opposed to something else?
>>
> 
> It can do this on the basis of the machine address ranges.
> It does not need to know this, it only needs to know that the infinite
> recursion criteria has been met.

The issue is that first this test doesn't have meaning when you think
about converting to a Turing Equivalent, and can only be done because
you didn't fully form H_Hat correctly. H_Hat, by its definition of
formation includes its own copy of ALL the code it uses, including
Halts. If fact, because we pass it a representation of a machine, that
machine needs to be a totally independent 'program', which DEFINITELY
can not call back to subroutines within the original simulator. Once you
change your program to do this, your 'machine address range' test just
fails.

This goes back to you definitions. You have 'defined' that Halts is
supposed to be deciding based on providing it a COFF file, but Halts
does not actually take a COFF file as its input, but addresses in its
own program space. This makes H_Hat and Halts to not be in the
relationship they need to be inorder to really be the equivalents of the
needed Turing Machine.

It turns out, as long as you still keep to the real definition of
Halting and Computations, this error isn't enough let you cheat the
proof through, but it does get you close enough that this bogus
recursion definition can almost sound convinsing for a Rhetorical
Argument. By pulling the code for Halts out of H_Hat, you can try to
argue that the decision of the copy of Halts that was called by H_Hat
isn't really part of the execution of H_Hat, but it really is.

The fact that the Halts that is execution within the context of H_Hat is
deciding to stop its simulation of the provided copy of H_Hat, doesn't
make H_Hat 'infinittelly recursive' but actually is part of the reason
it is finite. It is exactly the same reasoning that

for(int i = 0; i < 5; i++) continue;

is a finite loop, a decision, WITHIN the loop or within the execution of
H_Hat (in the code of Halts that H_Hat called) made the decision to
terminate and thus the loop ended.

Ultimately, the answer of H_Hat being halting or non-halting is shown by
actually running it, and as been show, it DOES halt.

YOU try to mislead by saying it is only halting because Halts stopped
it, which in one sense is true, but the Halts that stopped it was the
Halts that was PART of H_Hat.

It doesn't matter that the simulation seemed to have only stopped
because the Halts running the simulation needed to make the decision,
that is a limitation of how you have setup your simulator. The real test
is what does the actual machine do.

We CAN also show that Halts didn't need to stop the simulation, by
changing the outer Halts, and ONLY the outer Halts, to be a pure
simulator and not a halt decider.

You try to argue that if we make this change we need to change all
copies of Halts, but that is incorrect, that would change the definition
of the program under test, which isn't allowed. Remember, H_Hat was
defined to be built on a specific algrorithm with at the time it was
created was the thing called Halts. It isn't defined to use whatever is
called Halts, the name doesn't matter, it is to use the algorithm of the
decider that it is supposed to foil. That is why it takes a copy. Not
making the copy breaks the needed relationship between H_Hat and Halts.


> 
>> In the past you've said that you do this based on addresses, but an
>> emulator should have an entirely separate (emulated) address space
>> from code which is actually being executed. 
> 
> There is no actual need for this. The key element of the emulation is
> that the emulated execution of each instruction <is> a part of a single
> computation and the emulator is free to stop its emulation as soon as
> non-halting behavior criteria is met.
> 
>> Furthermore, you've said your machine descriptions are in COFF files.
>> A COFF file doesn't indicate *where* in memory a particular piece of
>> code should be placed. So how 
> 
> I just leave code where it already is in the COFF file.
> 
> //  This file reads a Microsoft COFF Object file and patches
> //  all the otherwise relocatable data address references to
> //  their actual physical file offsets.
> 
>> does the emulator decide that a particular piece of code should be
>> given the same (emulated) address as the (actual) address of Halts()?
>>
> 
> The executing x86 code knows nothing about names, it only deals with
> machine addresses. Every function has its own unique machine address as
> an offset in the COFF object file.
> 
>> André
>>
>>> (2) With the same parameters to Halts().
>>> (3) With no conditional branch or indexed jump instructions in H_Hat().
>>> (4) With no function call returns from Halts().
>>> then the function call from H_Hat() to Halts() is infinitely recursive.
>>>
>>>
>>> _H_Hat()
>>> [00000adb](01)  55                      push ebp
>>> [00000adc](02)  8bec                    mov ebp,esp
>>> [00000ade](01)  51                      push ecx
>>> [00000adf](03)  8b4508                  mov eax,[ebp+08]
>>> [00000ae2](01)  50                      push eax
>>> [00000ae3](03)  8b4d08                  mov ecx,[ebp+08]
>>> [00000ae6](01)  51                      push ecx
> 
> This is where Halts() is called with the machine address of H_Hat()
> having been pushed onto the stack in the prior two push instructions.
> 
>>> [00000ae7](05)  e85ffeffff              call 0000094b
>>> [00000aec](03)  83c408                  add esp,+08
>>> [00000aef](03)  8945fc                  mov [ebp-04],eax
>>> [00000af2](02)  8be5                    mov esp,ebp
>>> [00000af4](01)  5d                      pop ebp
>>> [00000af5](01)  c3                      ret
>>> Size in bytes:(0027) [00000af5]
>>>
>>> Begin Local Halt Decider Simulation at Machine Address:adb
>>> ...[00000adb][0021158c][00211590](01)  55                      push ebp
>>> ...[00000adc][0021158c][00211590](02)  8bec                    mov
>>> ebp,esp
>>> ...[00000ade][00211588][0020155c](01)  51                      push ecx
>>> ...[00000adf][00211588][0020155c](03)  8b4508                  mov
>>> eax,[ebp+08]
>>> ...[00000ae2][00211584][00000adb](01)  50                      push eax
>>> ...[00000ae3][00211584][00000adb](03)  8b4d08                  mov
>>> ecx,[ebp+08]
>>> ...[00000ae6][00211580][00000adb](01)  51                      push ecx
>>> ...[00000ae7][0021157c][00000aec](05)  e85ffeffff              call
>>> 0000094b
>>> ...[00000adb][0025bfb4][0025bfb8](01)  55                      push ebp
>>> ...[00000adc][0025bfb4][0025bfb8](02)  8bec                    mov
>>> ebp,esp
>>> ...[00000ade][0025bfb0][0024bf84](01)  51                      push ecx
>>> ...[00000adf][0025bfb0][0024bf84](03)  8b4508                  mov
>>> eax,[ebp+08]
>>> ...[00000ae2][0025bfac][00000adb](01)  50                      push eax
>>> ...[00000ae3][0025bfac][00000adb](03)  8b4d08                  mov
>>> ecx,[ebp+08]
>>> ...[00000ae6][0025bfa8][00000adb](01)  51                      push ecx
>>> ...[00000ae7][0025bfa4][00000aec](05)  e85ffeffff              call
>>> 0000094b
>>> Local Halt Decider: Infinite Recursion Detected Simulation Stopped
>>>
>>>
>>>> This part you really need to elaborate on. H_Hat(X) calls Halts(X,
>>>> X), which then emulates X(X) based on the description of X which it
>>>> has been passed. How does Halts determine whether that X describes
>>>> 'the same' function as one previously called? i.e. how does it
>>>> figure out that X is a description of H_Hat?
>>>>
>>>> André
>>>>
>>>>> (2) With the same parameters to X().
>>>>> (3) With no conditional branch or indexed jump instructions in Y().
>>>>> (4) With no function call returns from X().
>>>>> then the function call from Y() to X() is infinitely recursive.
>>>>>
>>>>> The above criteria does correctly decide infinite recursion.
>>>>> The above criteria does correctly decide infinite recursion.
>>>>> The above criteria does correctly decide infinite recursion.
>>>>>
>>>>> Every call from H_Hat() to Halts() meets this criteria.
>>>>> Every call from H_Hat() to Halts() meets this criteria.
>>>>> Every call from H_Hat() to Halts() meets this criteria.
>>>>>
>>>>> Ignoring this key fact is no form of correct rebuttal.
>>>>> Ignoring this key fact is no form of correct rebuttal.
>>>>> Ignoring this key fact is no form of correct rebuttal.
>>>>>
>>>>>> Halts(H_Hat, H_Hat) should be true, but you
>>>>>> have written Halts so that it's false and you justify that wrong
>>>>>> answer
>>>>>> by what would happen were things not as they are.  It's flagrant
>>>>>> silliness.
>>>>>
>>>>>> When you find yourself starting off "So in other words you
>>>>>> believe..."
>>>>>> you should stop and ask yourself, "what point am I trying to avoid by
>>>>>> putting words into my interlocutor's mount?".
>>>>>>
>>>>>
>>>>>
>>>>
>>>>
>>>
>>>
>>
>>
> 
> 

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


#32545 — Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]

FromRichard Damon <Richard@Damon-Family.org>
Date2021-05-01 21:40 -0400
SubjectRe: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]
Message-ID<rqnjI.269456$2N3.150154@fx33.iad>
In reply to#32538
On 5/1/21 9:05 PM, olcott wrote:
> On 5/1/2021 7:51 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> No H_Hat() in the universe ever stops running unless its otherwise
>>> infinite recursion is aborted at some point.
>>
>> This is just a silly word game.  What a computation would do "otherwise"
>> is irrelevant.  H_Hat(H_Hat) is finite and it does not matter how or
>> why.  It is a finite computation, and should be reported as such.
>>
> 
> So in other words you believe that it is ridiculous for anyone to ever
> consider defining a partial halt decider because everyone agrees that is
> cannot be done perfectly so why bother doing this at all.
> 
> On the other hand there are only two possible choices for any partial
> halt decider:
> (a) static analysis or
> (b) dynamic analysis
> 
> that you reject dynamic analysis out-of-hand as "just silly" is a
> sufficiently strong indication that you have no interest in any honest
> dialogue.
> 

There is nothing wrong with working on a partial halt decider.
There is nothing wrong with using dynamic analysis for a halt decider.

It just is a fact that for ANY given partial halt decider, one program
that it can not get right is the H^ build on it.

It is OK for a Halt Decider to be wrong, that doesn't make the universe
explode, it just make the decider wrong.

Just like you can't write an algorithm to always win at Tic-Tak-Toe, you
can't write an algorithm that will always be right at deciding the
Halting of Turing Machines.

That is just the way it is.

Live with it.

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


#32544 — Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]

FromRichard Damon <Richard@Damon-Family.org>
Date2021-05-01 21:35 -0400
SubjectRe: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]
Message-ID<3mnjI.172559$ST2.107000@fx47.iad>
In reply to#32533
On 5/1/21 7:42 PM, olcott wrote:
> On 5/1/2021 6:28 PM, André G. Isaak wrote:
>> On 2021-05-01 16:49, olcott wrote:
>>
>>>> 7) By 3, this means that H_Hat will Halt.
>>>
>>> The H_Hat in main() halts only because the H_Hat() simulated in
>>> H_Hat() is forced to halt on the basis that
>>>
>>> Every computation that never stops unless its simulator stops
>>> simulating it <is> a non halting computation.
>>>
>>>> 8) This means that H_Hat is a Halting Computation, and because of 2,
>>>> Halts is wrong.
>>>
>>> WRONG:
>>> Every computation that never stops unless its simulator stops
>>> simulating it <is> a non halting computation.
>>
>> You really need to learn to be consistent with respect to the
>> antecedent of 'its'. The H_Hat in main is the computation being asked
>> about, and it doesn't *have* a simulator. Only the embedded H_Hat
>> does, but that's an entirely different call. You're shifting the
>> antecedent of 'its' from the actual computation under consideration to
>> a call inside of it.
>>
>> H_Hat halts not because some simulator stops it. It halts because it
>> is a finite computation. The simulator *inside* H_Hat might stop
>> simulating its input (which isn't the same as halting), but that's not
>> what's being asked about.
> 
> No H_Hat() in the universe ever stops running unless its otherwise
> infinite recursion is aborted at some point.
> 
> That this otherwise infinite recursion is aborted on its second call to
> the same function from the same machine address with the same data or
> the 13th time that this occurs makes no difference, H_Hat() ALWAYS
> specifies infinite recursion that must be aborted.
> 

In that case, Halts also has infinite recursion and is a non-halting
computation and thus can't be a halt decider. It only stops the infinite
recursion because something stopped it.

You need to get straight that the Turing Machine H_Hat that is actually
running as a Turing Machine is DIFFERENT then the simulation of H_Hat
being run with Halts inside that H_Hat.

If you read a book about someone killing you, do you die?

There IS no simulator to abort the operation of the Turing Machine
H_Hat. It is running as an actual machine.

You are imagining something that doesn't exist.

Also, H_Hat get credit for the Halts that runs as part of it, that Halts
is PART of the algorithm for H_Hat, because H_Hat has a copy of it
within it.

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


#32543

FromRichard Damon <Richard@Damon-Family.org>
Date2021-05-01 21:29 -0400
Message-ID<ugnjI.165204$J_5.77495@fx46.iad>
In reply to#32526
On 5/1/21 6:49 PM, olcott wrote:
> On 5/1/2021 5:02 PM, Richard Damon wrote:
>> On 5/1/21 3:09 PM, olcott wrote:
>>> On 5/1/2021 1:55 PM, Richard Damon wrote:
>>>> On 5/1/21 1:40 PM, olcott wrote:
>>>>> On 5/1/2021 11:37 AM, olcott wrote:
>>>>>> On 5/1/2021 11:30 AM, olcott wrote:
>>>>>>> There seems to be little agreement on the precise details of what is
>>>>>>> and what is not a computation in computer science across respondents
>>>>>>> here and textbook definitions.
>>>>>>>
>>>>>>> I will provide and analyze the textbook definitions of: {Linz,
>>>>>>> Sipser
>>>>>>> and Kozen} for "computable function".
>>>>>>>
>>>>>>> A function f with domain f is said to be Turing-computable of just
>>>>>>> computable if there exists some Turing machine M = (Q, Σ, Γ, δ, q0,
>>>>>>> □, F)
>>>>>>>
>>>>>>> such that q0w ⊢* Mqₘf(w), qₘ ∈ F, for all w ∈ D
>>>>>>>
>>>>>>> Paraphrase: Turing machine M begins in its start state and after
>>>>>>> making an arbitrary number of moves on input w in domain D halts
>>>>>>> in a
>>>>>>> final state of its set of final states of M.
>>>>>>>
>>>>>>> Linz, Peter 1990. An Introduction to Formal Languages and Automata.
>>>>>>> Lexington/Toronto: D. C. Heath and Company. (243)
>>>>>>>
>>>>>>> Computable Functions
>>>>>>> A Turing machine computes a function by starting with the input to
>>>>>>> the function on the tape and halting with the output of the function
>>>>>>> on the tape.
>>>>>>>
>>>>>>> Definition 5.12
>>>>>>> A function f: Σ* → Σ* is a computable function if some Turing
>>>>>>> machine
>>>>>>> M, on every input w, halts with just f(w) on its tape.
>>>>>>>
>>>>>>> Paraphrase: Turing machine M transforms input finite string w into
>>>>>>> output finite string M(w). This regular expression Σ* indicates zero
>>>>>>> or more elements of Σ (the input alphabet).
>>>>>>>
>>>>>>> Sipser, Michael 1997. Introduction to the Theory of Computation.
>>>>>>> Boston: PWS Publishing Company (190)
>>>>>>>
>>>>>>> A partial function σ: Σ* → Σ* is said to be a computable function if
>>>>>>> σ(x) = M(x) for some Turing machine M.
>>>>>>>
>>>>>>> Kozen, Dexter 1997. Automata and Computability. New York:
>>>>>>> Springer-Verlag. (347).
>>>>>>>
>>>>>>> When we combine all the definitions together we can simplify Linz
>>>>>>> and
>>>>>>> instead of saying that w ∈ D, we say that w is a (possibly empty)
>>>>>>> finite string of the input alphabet.
>>>>>>>
>>>>>>> All of the definitions require M to halt. Linz requires M to halt in
>>>>>>> a final state of the final states of M. Kozen requires that an input
>>>>>>> finite string derives an output finite string. Sipser require the
>>>>>>> same a Kozen yet the input finite string must be also erased.
>>>>>>>
>>>>>>> If we unify these definitions we might say that a [computable
>>>>>>> function] is some Turing machine M that makes an arbitrary number of
>>>>>>> moves on a some (possibly empty) finite string w ∈ Σ* of its input
>>>>>>> alphabet and ends up in a final state of its set of final states.
>>>>>>>
>>>>>>> Optionally there may be some finite string x ∈ Σ* of its input
>>>>>>> alphabet on it tape. I will ignore the apparent Sipser
>>>>>>> requirement to
>>>>>>> erase the input string.
>>>>>>>
>>>>>>> Since the input finite string can possibly be empty a Turing machine
>>>>>>> M that simply transitions from its start state to its final state
>>>>>>> would be a computable function.
>>>>>>>
>>>>>>
>>>>>> A [computable function] is some Turing machine M that makes an
>>>>>> arbitrary number of moves from its start state on a some (possibly
>>>>>> empty) finite string w ∈ Σ* of its input alphabet and ends up in a
>>>>>> final state of its set of final states.
>>>>>>
>>>>>> Optionally there may be some finite string x ∈ Σ* output left on its
>>>>>> tape.  Because the input string can be empty and the output string is
>>>>>> optional the definition of [computable function] would define a
>>>>>> [computation] as any Turing machine that halts.
>>>>>
>>>>>
>>>>> To make [computable function] generic to all models of computation:
>>>>> A [computable function] is some sequence of mechanical steps that
>>>>> begins
>>>>> at a start state (initial configuration) and ends in some specific
>>>>> final
>>>>> state (final configuration) on some possibly empty input finite
>>>>> string.
>>>>> An optional finite string output is construed as an aspect of the
>>>>> final
>>>>> configuration.
>>>>>
>>>>>
>>>> As I mentioned in my other reply, once you leave the domain of Turing
>>>> Machines, the requirement of a given input always giving the same
>>>> output
>>>> becomes an important restriction, and a necessity for the operation to
>>>> be able to have a Turing Machine equivalent.
>>>>
>>>
>>> In the case of the mapping from Halts(H_Hat, H_Hat) to a final state
>>> indicating "No" (not halting) it can perform any mechanical steps in any
>>> way as long as the mapping from the input to the final state always
>>> produces the same result.
>>>
>>> The part that you can never seem to understand is that between the start
>>> state and the final state this machine is free to do anything that
>>> machines can possibly do. You have never seemed to get this part.
>>
>> Not 'Anything' as it is constrained by the definition of a Computation,
>> and as such it MUST return its answer to its caller. With those basic
>> requirements, we can show that we can make a Computation that it will
>> get its decision wrong on.
>>
>> Find the error:
>>
>> 1) Halts is stipulated to meet the requirements of a Halt Decider for
>> Computation Theory, as used in the proof of Linz and Sipser.
> 
> It halts in a final state indicating yes or no to the question does this
> input machine description finite string pair specify a finite computation.
> 

Right.
>>
>> 2) Halts is stipulated to return non-Halting on Halts(H_Hat, H_Hat) when
>> asked direction (If you want to change that, we can give the other
>> argument for why that will be wrong)
> 
> I understand what "asked direction means" for questions such as "which
> way to Walmart?" I have no idea what you are referring to by asked
> direction.

That was supposed to be 'asked directly', apparently a spell check went
wonky.

> 
>> 3) H_Hat is stipulated to be built like Linz or Sipser, in that it will
>> halt when the Halt decider it is built on decides H_Hat’s input is
>> non-Halting on itself.
> Yes
> 
>> 4) 1 Means that Halts is a Computation, and will always return the same
>> answer (or never return an answer) for a given input.
> Yes.
> 
>> 5) H_Hat when run as a Machine will perform the Computation Halts(H_Hat,
>> H_Hat)
> Yes
> 
>> 6) by 4 and 2, this means that Halts will return the decision on
>> non-halting to H_Hat
> By (2)(4) and (5).
> 
> 
> void H_Hat(u32 P)
> {
>  u32 Input_Halts = Halts(P, P);
>  if (Input_Halts)
>    HERE: goto HERE;
> }
> 
> 
> int main()
> {
>  H_Hat((u32)H_Hat);
> }
> 
>> 7) By 3, this means that H_Hat will Halt.
> 
> The H_Hat in main() halts only because the H_Hat() simulated in H_Hat()
> is forced to halt on the basis that
> 
> Every computation that never stops unless its simulator stops simulating
> it <is> a non halting computation.
> 
>> 8) This means that H_Hat is a Halting Computation, and because of 2,
>> Halts is wrong.
> 
> WRONG:
> Every computation that never stops unless its simulator stops simulating
> it <is> a non halting computation.

WRONG. If it stops on its own, including the actions of any part of it,
it is Halting.

There was NO simulator for the Turing Machine H_Hat in the above, it was
a pure Turing Machine.

No Simulatore was there TO stop it, so no simulator did.

The Halts within H_Hat simulated a description of the machine, but that
is part of the algorithm of H_Hat.

Is this an infinite loop?:

for(int i=0; i < 5; i++) continue;

It is exactly the same sort of logic, a decision that is part of the
algorithm makes the decision to terminate the loop.

> 
> If your reasoning was correct then when Halts() forces Infinite_Loop()
> to stop running this "proves" that Infinite_Loop() is not an infinite loop.
> 
> void Infinite_Loop()
> {
>  HERE: goto HERE;
> }
> 
> int main()
> {
>  u32 Input_Would_Halt = Halts((u32)Infinite_Loop, (u32)Infinite_Loop);
> }
> 
> 


WRONG. There the Turing Machine is Halts, not Infinite_Loop, so the
halting was of Halts, not Infinite_loop.

Run Infinite_Loop from main instead, and it won't halt.

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


#32506

FromRichard Damon <Richard@Damon-Family.org>
Date2021-05-01 14:49 -0400
Message-ID<_ohjI.73721$sd3.27264@fx02.iad>
In reply to#32497
On 5/1/21 12:37 PM, olcott wrote:
> On 5/1/2021 11:30 AM, olcott wrote:
>> There seems to be little agreement on the precise details of what is
>> and what is not a computation in computer science across respondents
>> here and textbook definitions.
>>
>> I will provide and analyze the textbook definitions of: {Linz, Sipser
>> and Kozen} for "computable function".
>>
>> A function f with domain f is said to be Turing-computable of just
>> computable if there exists some Turing machine M = (Q, Σ, Γ, δ, q0, □, F)
>>
>> such that q0w ⊢* Mqₘf(w), qₘ ∈ F, for all w ∈ D
>>
>> Paraphrase: Turing machine M begins in its start state and after
>> making an arbitrary number of moves on input w in domain D halts in a
>> final state of its set of final states of M.
>>
>> Linz, Peter 1990. An Introduction to Formal Languages and Automata.
>> Lexington/Toronto: D. C. Heath and Company. (243)
>>
>> Computable Functions
>> A Turing machine computes a function by starting with the input to the
>> function on the tape and halting with the output of the function on
>> the tape.
>>
>> Definition 5.12
>> A function f: Σ* → Σ* is a computable function if some Turing machine
>> M, on every input w, halts with just f(w) on its tape.
>>
>> Paraphrase: Turing machine M transforms input finite string w into
>> output finite string M(w). This regular expression Σ* indicates zero
>> or more elements of Σ (the input alphabet).
>>
>> Sipser, Michael 1997. Introduction to the Theory of Computation.
>> Boston: PWS Publishing Company (190)
>>
>> A partial function σ: Σ* → Σ* is said to be a computable function if
>> σ(x) = M(x) for some Turing machine M.
>>
>> Kozen, Dexter 1997. Automata and Computability. New York:
>> Springer-Verlag. (347).
>>
>> When we combine all the definitions together we can simplify Linz and
>> instead of saying that w ∈ D, we say that w is a (possibly empty)
>> finite string of the input alphabet.
>>
>> All of the definitions require M to halt. Linz requires M to halt in a
>> final state of the final states of M. Kozen requires that an input
>> finite string derives an output finite string. Sipser require the same
>> a Kozen yet the input finite string must be also erased.
>>
>> If we unify these definitions we might say that a [computable
>> function] is some Turing machine M that makes an arbitrary number of
>> moves on a some (possibly empty) finite string w ∈ Σ* of its input
>> alphabet and ends up in a final state of its set of final states.
>>
>> Optionally there may be some finite string x ∈ Σ* of its input
>> alphabet on it tape. I will ignore the apparent Sipser requirement to
>> erase the input string.
>>
>> Since the input finite string can possibly be empty a Turing machine M
>> that simply transitions from its start state to its final state would
>> be a computable function.
>>
> 
> A [computable function] is some Turing machine M that makes an arbitrary
> number of moves from its start state on a some (possibly empty) finite
> string w ∈ Σ* of its input alphabet and ends up in a final state of its
> set of final states.
> 
> Optionally there may be some finite string x ∈ Σ* output left on its
> tape.  Because the input string can be empty and the output string is
> optional the definition of [computable function] would define a
> [computation] as any Turing machine that halts.
> 

One consequence of this definition that you seem to be missing is that
for a given input a given machine will ALWAYS give the same output
(final state + contents of tape). This is a direct consequence of how
Turing Machines work, but if you want to define the Computation /
Computable Function independent of a Turing Machine, this becomes part
of its requirements.

Note, you don't really need to treat the 'Empty Tape' as a special case,
as it is just a tape with zero symbols on it. The Computation might
define that you ignore the output tape, and just treat the state it
halted in, or even just that it halted as the 'output'.

Some of the variations depends a bit on exactly what branch or use of
Computation theory you are using. I think Computable Function always
implies that the Computation is finite (and thus Halt-Deciding is asking
does the Turing Machine with that input define a Computable Function or
not). Computation sometimes is just a synonym for this, or sometimes
includes the case where the Turing Machine never halts, being merely the
effect of combining a Turing Machine with an input Tape.

One other comment, the Computable Function isn't the Turing Machine
itself in the normal definitions, but the mapping of input to output,
the Turing Machine is just the implementation of it.

More specifically, Computatable Function refers to the mapping,
Computation deals with how that is done, being the combination of an
Algorithm (which the Turing Machine implements) and an input data (the
Tape of the Turing Machine). An Algorithm being a finite listing of
'mechanical' steps to perform to do the Computation to get the
Computable Function.

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


#32509

Fromolcott <NoOne@NoWhere.com>
Date2021-05-01 14:02 -0500
Message-ID<29idnYB-Gq4rOBD9nZ2dnUU7-WfNnZ2d@giganews.com>
In reply to#32506
On 5/1/2021 1:49 PM, Richard Damon wrote:
> On 5/1/21 12:37 PM, olcott wrote:
>> On 5/1/2021 11:30 AM, olcott wrote:
>>> There seems to be little agreement on the precise details of what is
>>> and what is not a computation in computer science across respondents
>>> here and textbook definitions.
>>>
>>> I will provide and analyze the textbook definitions of: {Linz, Sipser
>>> and Kozen} for "computable function".
>>>
>>> A function f with domain f is said to be Turing-computable of just
>>> computable if there exists some Turing machine M = (Q, Σ, Γ, δ, q0, □, F)
>>>
>>> such that q0w ⊢* Mqₘf(w), qₘ ∈ F, for all w ∈ D
>>>
>>> Paraphrase: Turing machine M begins in its start state and after
>>> making an arbitrary number of moves on input w in domain D halts in a
>>> final state of its set of final states of M.
>>>
>>> Linz, Peter 1990. An Introduction to Formal Languages and Automata.
>>> Lexington/Toronto: D. C. Heath and Company. (243)
>>>
>>> Computable Functions
>>> A Turing machine computes a function by starting with the input to the
>>> function on the tape and halting with the output of the function on
>>> the tape.
>>>
>>> Definition 5.12
>>> A function f: Σ* → Σ* is a computable function if some Turing machine
>>> M, on every input w, halts with just f(w) on its tape.
>>>
>>> Paraphrase: Turing machine M transforms input finite string w into
>>> output finite string M(w). This regular expression Σ* indicates zero
>>> or more elements of Σ (the input alphabet).
>>>
>>> Sipser, Michael 1997. Introduction to the Theory of Computation.
>>> Boston: PWS Publishing Company (190)
>>>
>>> A partial function σ: Σ* → Σ* is said to be a computable function if
>>> σ(x) = M(x) for some Turing machine M.
>>>
>>> Kozen, Dexter 1997. Automata and Computability. New York:
>>> Springer-Verlag. (347).
>>>
>>> When we combine all the definitions together we can simplify Linz and
>>> instead of saying that w ∈ D, we say that w is a (possibly empty)
>>> finite string of the input alphabet.
>>>
>>> All of the definitions require M to halt. Linz requires M to halt in a
>>> final state of the final states of M. Kozen requires that an input
>>> finite string derives an output finite string. Sipser require the same
>>> a Kozen yet the input finite string must be also erased.
>>>
>>> If we unify these definitions we might say that a [computable
>>> function] is some Turing machine M that makes an arbitrary number of
>>> moves on a some (possibly empty) finite string w ∈ Σ* of its input
>>> alphabet and ends up in a final state of its set of final states.
>>>
>>> Optionally there may be some finite string x ∈ Σ* of its input
>>> alphabet on it tape. I will ignore the apparent Sipser requirement to
>>> erase the input string.
>>>
>>> Since the input finite string can possibly be empty a Turing machine M
>>> that simply transitions from its start state to its final state would
>>> be a computable function.
>>>
>>
>> A [computable function] is some Turing machine M that makes an arbitrary
>> number of moves from its start state on a some (possibly empty) finite
>> string w ∈ Σ* of its input alphabet and ends up in a final state of its
>> set of final states.
>>
>> Optionally there may be some finite string x ∈ Σ* output left on its
>> tape.  Because the input string can be empty and the output string is
>> optional the definition of [computable function] would define a
>> [computation] as any Turing machine that halts.
>>
> 
> One consequence of this definition that you seem to be missing is that
> for a given input a given machine will ALWAYS give the same output
> (final state + contents of tape). This is a direct consequence of how
> Turing Machines work, but if you want to define the Computation /
> Computable Function independent of a Turing Machine, this becomes part
> of its requirements.
> 
> Note, you don't really need to treat the 'Empty Tape' as a special case,
> as it is just a tape with zero symbols on it. The Computation might
> define that you ignore the output tape, and just treat the state it
> halted in, or even just that it halted as the 'output'.
> 

It is a key distinction because several people here seem to believe that 
a computation must have a non-empty input.

> Some of the variations depends a bit on exactly what branch or use of
> Computation theory you are using. I think Computable Function always
> implies that the Computation is finite (and thus Halt-Deciding is asking
> does the Turing Machine with that input define a Computable Function or
> not). Computation sometimes is just a synonym for this, 

> or sometimes
> includes the case where the Turing Machine never halts, 

No it never includes this.

> being merely the
> effect of combining a Turing Machine with an input Tape.
> 
> One other comment, the Computable Function isn't the Turing Machine
> itself in the normal definitions, but the mapping of input to output,
> the Turing Machine is just the implementation of it.
> 

Yes. It must be a mapping of some possibly empty input to some possibly 
empty output and it must halt.

> More specifically, Computatable Function refers to the mapping,
> Computation deals with how that is done, being the combination of an
> Algorithm (which the Turing Machine implements) and an input data (the
> Tape of the Turing Machine). An Algorithm being a finite listing of
> 'mechanical' steps to perform to do the Computation to get the
> Computable Function.
> 


-- 
Copyright 2021 Pete Olcott

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

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


#32519

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-05-01 22:50 +0100
Message-ID<87h7jmazub.fsf@bsb.me.uk>
In reply to#32497
olcott <NoOne@NoWhere.com> writes:

> A [computable function] is some Turing machine M

No.  Category error.

-- 
Ben.

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


#32501

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2021-05-01 18:22 +0000
Message-ID<20210501112124.596@kylheku.com>
In reply to#32496
On 2021-05-01, olcott <NoOne@NoWhere.com> wrote:
> There seems to be little agreement on the precise details of what is and 
> what is not a computation in computer science across respondents here 
> and textbook definitions.

So you think, but actually no there isn't any disagreement whatsoever.

You just don't understand the concepts enough to recognize the
equivalence of different angles on the subject.

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


#32503

Fromolcott <NoOne@NoWhere.com>
Date2021-05-01 13:35 -0500
Message-ID<prudnUOVFczUAhD9nZ2dnUU7-YHNnZ2d@giganews.com>
In reply to#32501
On 5/1/2021 1:22 PM, Kaz Kylheku wrote:
> On 2021-05-01, olcott <NoOne@NoWhere.com> wrote:
>> There seems to be little agreement on the precise details of what is and
>> what is not a computation in computer science across respondents here
>> and textbook definitions.
> 
> So you think, but actually no there isn't any disagreement whatsoever.
> 
> You just don't understand the concepts enough to recognize the
> equivalence of different angles on the subject.
> 

Yes if you just glance at a few words before forming your rebuttal this 
would be the conclusion that you would draw.

Several people here do not seem to be aware that a computable function 
can have the empty string for input (A convoluted way of saying no 
input). Also only Sipser seems to believe that the input must be erased.

-- 
Copyright 2021 Pete Olcott

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

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


#32515

FromMr Flibble <flibble@i42.REMOVETHISBIT.co.uk>
Date2021-05-01 22:39 +0100
Message-ID<6UjjI.241616$Qjyf.227863@fx14.ams4>
In reply to#32496
On 01/05/2021 17:30, olcott wrote:
> There seems to be little agreement on the precise details of what is and what is 
> not a computation in computer science across respondents here and textbook 
> definitions.
> 
> I will provide and analyze the textbook definitions of: {Linz, Sipser and Kozen} 
> for "computable function".
> 
> A function f with domain f is said to be Turing-computable of just computable if 
> there exists some Turing machine M = (Q, Σ, Γ, δ, q0, □, F)
> 
> such that q0w ⊢* Mqₘf(w), qₘ ∈ F, for all w ∈ D
> 
> Paraphrase: Turing machine M begins in its start state and after making an 
> arbitrary number of moves on input w in domain D halts in a final state of its 
> set of final states of M.
> 
> Linz, Peter 1990. An Introduction to Formal Languages and Automata. 
> Lexington/Toronto: D. C. Heath and Company. (243)
> 
> Computable Functions
> A Turing machine computes a function by starting with the input to the function 
> on the tape and halting with the output of the function on the tape.
> 
> Definition 5.12
> A function f: Σ* → Σ* is a computable function if some Turing machine M, on 
> every input w, halts with just f(w) on its tape.
> 
> Paraphrase: Turing machine M transforms input finite string w into output finite 
> string M(w). This regular expression Σ* indicates zero or more elements of Σ 
> (the input alphabet).
> 
> Sipser, Michael 1997. Introduction to the Theory of Computation. Boston: PWS 
> Publishing Company (190)
> 
> A partial function σ: Σ* → Σ* is said to be a computable function if σ(x) = M(x) 
> for some Turing machine M.
> 
> Kozen, Dexter 1997. Automata and Computability. New York: Springer-Verlag. (347).
> 
> When we combine all the definitions together we can simplify Linz and instead of 
> saying that w ∈ D, we say that w is a (possibly empty) finite string of the 
> input alphabet.
> 
> All of the definitions require M to halt. Linz requires M to halt in a final 
> state of the final states of M. Kozen requires that an input finite string 
> derives an output finite string. Sipser require the same a Kozen yet the input 
> finite string must be also erased.
> 
> If we unify these definitions we might say that a [computable function] is some 
> Turing machine M that makes an arbitrary number of moves on a some (possibly 
> empty) finite string w ∈ Σ* of its input alphabet and ends up in a final state 
> of its set of final states.
> 
> Optionally there may be some finite string x ∈ Σ* of its input alphabet on it 
> tape. I will ignore the apparent Sipser requirement to erase the input string.
> 
> Since the input finite string can possibly be empty a Turing machine M that 
> simply transitions from its start state to its final state would be a computable 
> function.

Garbage.

/Flibble

-- 
😎

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


#32518

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-05-01 22:49 +0100
Message-ID<87k0oiazun.fsf@bsb.me.uk>
In reply to#32496
olcott <NoOne@NoWhere.com> writes:

> There seems to be little agreement on the precise details of what is
> and what is not a computation in computer science across respondents
> here and textbook definitions.

No.  /You/ may me confused by slightly different definitions, but there
is no substantive disagreement on this matter.

> Since the input finite string can possibly be empty a Turing machine M
> that simply transitions from its start state to its final state would
> be a computable function.

Category error.

-- 
Ben.

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


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

Back to top | Article view | comp.theory


csiph-web