On 7/9/2022 4:51 PM, André G. Isaak wrote:
> On 2022-07-09 15:41, olcott wrote:
>> On 7/9/2022 4:34 PM, André G. Isaak wrote:
>>> On 2022-07-09 15:20, olcott wrote:
>>>> On 7/9/2022 4:12 PM, André G. Isaak wrote:
>>>>> On 2022-07-09 15:05, olcott wrote:
>>>>>> On 7/9/2022 4:03 PM, André G. Isaak wrote:
>>>>>
>>>>>>> You said you were talking about the "diagonal argument of the
>>>>>>> halting theorem", so I assumed you were talking about Sipser's
>>>>>>> proof of the halting theorem. The diagonalization argument you
>>>>>>> are discussing here doesn't deal directly with the halting
>>>>>>> problem (though it is closely related to it). That proof
>>>>>>> demonstrates that not all languages are decidable.
>>>>>>>
>>>>>>> André
>>>>>>>
>>>>>>>
>>>>>>
>>>>>> So you also never noticed the title of the post?
>>>>>> Did I encode Sipser correctly?
>>>>>
>>>>> "Sipser" is the name of an individual and/or book, not of a proof.
>>>>> Sipser gives many proofs.
>>>>>
>>>>
>>>> And I provided the whole proof that I was referring to.
>>>>
>>>>> It was perfectly reasonably of me to assume
>>>>
>>>> It is always totally unreasonable to ever assume anything contrary
>>>> to what was explicitly specified.
>>>>
>>>> I need to carefully analyze the diagonal argument and when I did
>>>> this with Kaz it was obvious that it is not the same as Linz.
>>>>
>>>> L15: Proof by Diagonalization that ATM (Halting Problem) is Not
>>>> Decidable
>>>> https://www.youtube.com/watch?v=jM6osxSX9GA
>>>
>>> ATM as described in both the textbook and the above video is *not*
>>> the halting problem.
>>>
>>> André
>>>
>>>
>>
>> What do you mean by this?
>
> ATM is a language consisting of all strings <M, w> such that M *accepts*
> w. His diagonalization proof shows that ATM is not a decidable language.
> It follows as a straightforward corollary that halting is undecidable,
> but whether ATM is decidable and whether halting is decidable are two
> separate (though related) problems.
>
> André
>

I still need to know whether or not I encoded Sipser correctly:

typedef void (*ptr)();

// Sipser's diagonal argument
int D(ptr x)
{ if (H(x,x) == 0) // reject
return 1;
else // accept
return 0;
}

int main()
{ Output("Input_Halts = ", H(D, D));
}

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

On 2022-07-09 16:05, olcott wrote:
> On 7/9/2022 4:51 PM, André G. Isaak wrote:
>> On 2022-07-09 15:41, olcott wrote:
>>> On 7/9/2022 4:34 PM, André G. Isaak wrote:
>>>> On 2022-07-09 15:20, olcott wrote:
>>>>> On 7/9/2022 4:12 PM, André G. Isaak wrote:
>>>>>> On 2022-07-09 15:05, olcott wrote:
>>>>>>> On 7/9/2022 4:03 PM, André G. Isaak wrote:
>>>>>>
>>>>>>>> You said you were talking about the "diagonal argument of the
>>>>>>>> halting theorem", so I assumed you were talking about Sipser's
>>>>>>>> proof of the halting theorem. The diagonalization argument you
>>>>>>>> are discussing here doesn't deal directly with the halting
>>>>>>>> problem (though it is closely related to it). That proof
>>>>>>>> demonstrates that not all languages are decidable.
>>>>>>>>
>>>>>>>> André
>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>> So you also never noticed the title of the post?
>>>>>>> Did I encode Sipser correctly?
>>>>>>
>>>>>> "Sipser" is the name of an individual and/or book, not of a proof.
>>>>>> Sipser gives many proofs.
>>>>>>
>>>>>
>>>>> And I provided the whole proof that I was referring to.
>>>>>
>>>>>> It was perfectly reasonably of me to assume
>>>>>
>>>>> It is always totally unreasonable to ever assume anything contrary
>>>>> to what was explicitly specified.
>>>>>
>>>>> I need to carefully analyze the diagonal argument and when I did
>>>>> this with Kaz it was obvious that it is not the same as Linz.
>>>>>
>>>>> L15: Proof by Diagonalization that ATM (Halting Problem) is Not
>>>>> Decidable
>>>>> https://www.youtube.com/watch?v=jM6osxSX9GA
>>>>
>>>> ATM as described in both the textbook and the above video is *not*
>>>> the halting problem.
>>>>
>>>> André
>>>>
>>>>
>>>
>>> What do you mean by this?
>>
>> ATM is a language consisting of all strings <M, w> such that M
>> *accepts* w. His diagonalization proof shows that ATM is not a
>> decidable language. It follows as a straightforward corollary that
>> halting is undecidable, but whether ATM is decidable and whether
>> halting is decidable are two separate (though related) problems.
>>
>> André
>>
>
> I still need to know whether or not I encoded Sipser correctly:

You mean did you translate it into C correctly? Since you've presented a
program below that won't compile due to the fact that H() is undefined,
who can possibly tell? But since the Sipser proof shows that neither H
nor D are possible, this should come as no surprise.

André

> typedef void (*ptr)();
>
> // Sipser's diagonal argument
> int D(ptr x)
> {
>   if (H(x,x) == 0) // reject
>     return 1;
>   else             // accept
>     return 0;
> }
>
> int main()
> {
>   Output("Input_Halts = ", H(D, D));
> }
>

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

On 7/9/22 5:59 PM, André G. Isaak wrote:
> On 2022-07-09 14:26, Richard Damon wrote:
>> On 7/9/22 4:14 PM, André G. Isaak wrote:
>>> On 2022-07-09 14:11, Richard Damon wrote:
>>>
>>>> H is REQUIRED (to be correct) to give the answer that D will give if
>>>> D will give an answer,
>>>
>>> No, H is required to answer "true" if D will give an answer,
>>> regardless of what that answer might be.
>>
>> I though in Sipser, H was supposed to be a decider where H accepts D,x
>> if D will accept x, and reject if D doesn't accept x (either reject or
>> not-answer).
>>
>> D is then defined to accept if T rejects and rejects if T accepts.
>
> mea culpa. I was confused by Sipser's use of H to refer not to a halt
> decider but to a decider of A_TM. Admittedly I should have verified this
> against the PDF.
>
> André
>

Yes, the notation adopted in that paper is a bit confusing.

Not certain which book he his violating the Copyrights of, but it seems
poorly edited.

It looks like he has created a dummy Word Press sight just to post these
copyright violations on.

I can't see how without attached comments (just highlighting) it comes
close to the requirements of "Fair Use"

On 2022-07-09 16:37, Richard Damon wrote:
> On 7/9/22 5:59 PM, André G. Isaak wrote:
>> On 2022-07-09 14:26, Richard Damon wrote:
>>> On 7/9/22 4:14 PM, André G. Isaak wrote:
>>>> On 2022-07-09 14:11, Richard Damon wrote:
>>>>
>>>>> H is REQUIRED (to be correct) to give the answer that D will give
>>>>> if D will give an answer,
>>>>
>>>> No, H is required to answer "true" if D will give an answer,
>>>> regardless of what that answer might be.
>>>
>>> I though in Sipser, H was supposed to be a decider where H accepts
>>> D,x if D will accept x, and reject if D doesn't accept x (either
>>> reject or not-answer).
>>>
>>> D is then defined to accept if T rejects and rejects if T accepts.
>>
>> mea culpa. I was confused by Sipser's use of H to refer not to a halt
>> decider but to a decider of A_TM. Admittedly I should have verified
>> this against the PDF.
>>
>> André
>>
>
> Yes, the notation adopted in that paper is a bit confusing.
>
> Not certain which book he his violating the Copyrights of, but it seems
> poorly edited.
>
> It looks like he has created a dummy Word Press sight just to post these
> copyright violations on.
>
> I can't see how without attached comments (just highlighting) it comes
> close to the requirements of "Fair Use"

It is a bit strange that someone who insists on putting a copyright
notice on even the most asinine things has such little regard for copyright.

André

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

Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:

> On 09/07/2022 21:26, Richard Damon wrote:
>> On 7/9/22 4:14 PM, André G. Isaak wrote:
>>> On 2022-07-09 14:11, Richard Damon wrote:
>>>
>>>> H is REQUIRED (to be correct) to give the answer that D will give if D will give an answer,
>>>
>>> No, H is required to answer "true" if D will give an answer, regardless of what that answer might be.
>> I though in Sipser, H was supposed to be a decider where H accepts D,x if D will accept x, and
>> reject if D doesn't accept x (either reject or not-answer).
>> D is then defined to accept if T rejects and rejects if T accepts.
>
> Yes, this is what PO is talking about in Sipser. (You use T above,
> but Sipser uses H as the proposed decider, and D as the derived test
> TM for H, which reveals the contradiction.) H is supposed to be
> deciding
>
> A_TM = {<M,w)> : M is a TM and M accepts w}.
>
> H is not PO's normal proposed Halting decider, which has caused some
> confusion.

Can I add a plea? Given the mess that PO has made by ignoring encoding,
I don't think he should be allowed to get away with ignoring it for this
new, closely related, problem. H (in Sipser) is a function of /strings/
so the translation into C should be a function with const char *
parameters. That way PO must explain how to write the string the
represents a computation -- the obvious one being C source code.

I can't be bothered, but there are people still talking to him so why
let him make the same mistakes again?

--
Ben.

On 7/9/22 6:48 PM, André G. Isaak wrote:
> On 2022-07-09 16:37, Richard Damon wrote:
>> On 7/9/22 5:59 PM, André G. Isaak wrote:
>>> On 2022-07-09 14:26, Richard Damon wrote:
>>>> On 7/9/22 4:14 PM, André G. Isaak wrote:
>>>>> On 2022-07-09 14:11, Richard Damon wrote:
>>>>>
>>>>>> H is REQUIRED (to be correct) to give the answer that D will give
>>>>>> if D will give an answer,
>>>>>
>>>>> No, H is required to answer "true" if D will give an answer,
>>>>> regardless of what that answer might be.
>>>>
>>>> I though in Sipser, H was supposed to be a decider where H accepts
>>>> D,x if D will accept x, and reject if D doesn't accept x (either
>>>> reject or not-answer).
>>>>
>>>> D is then defined to accept if T rejects and rejects if T accepts.
>>>
>>> mea culpa. I was confused by Sipser's use of H to refer not to a halt
>>> decider but to a decider of A_TM. Admittedly I should have verified
>>> this against the PDF.
>>>
>>> André
>>>
>>
>> Yes, the notation adopted in that paper is a bit confusing.
>>
>> Not certain which book he his violating the Copyrights of, but it
>> seems poorly edited.
>>
>> It looks like he has created a dummy Word Press sight just to post
>> these copyright violations on.
>>
>> I can't see how without attached comments (just highlighting) it comes
>> close to the requirements of "Fair Use"
>
> It is a bit strange that someone who insists on putting a copyright
> notice on even the most asinine things has such little regard for
> copyright.
>
> André
>

Just shows that he really doesn't know what copyright means, just like
he doesn't bother to find out what a lot of things actually mean.

On 7/9/2022 6:04 PM, Ben Bacarisse wrote:
> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
>
>> On 09/07/2022 21:26, Richard Damon wrote:
>>> On 7/9/22 4:14 PM, André G. Isaak wrote:
>>>> On 2022-07-09 14:11, Richard Damon wrote:
>>>>
>>>>> H is REQUIRED (to be correct) to give the answer that D will give if D will give an answer,
>>>>
>>>> No, H is required to answer "true" if D will give an answer, regardless of what that answer might be.
>>> I though in Sipser, H was supposed to be a decider where H accepts D,x if D will accept x, and
>>> reject if D doesn't accept x (either reject or not-answer).
>>> D is then defined to accept if T rejects and rejects if T accepts.
>>
>> Yes, this is what PO is talking about in Sipser. (You use T above,
>> but Sipser uses H as the proposed decider, and D as the derived test
>> TM for H, which reveals the contradiction.) H is supposed to be
>> deciding
>>
>> A_TM = {<M,w)> : M is a TM and M accepts w}.
>>
>> H is not PO's normal proposed Halting decider, which has caused some
>> confusion.
>
> Can I add a plea? Given the mess that PO has made by ignoring encoding,
> I don't think he should be allowed to get away with ignoring it for this
> new, closely related, problem. H (in Sipser) is a function of /strings/
> so the translation into C should be a function with const char *
> parameters. That way PO must explain how to write the string the
> represents a computation -- the obvious one being C source code.

As I have told you every time that you keep bringing this up the input
to H <is> a pointer to finite string of machine-code bytes.

As you already know (yet disingenuously pretend to not know) there are
no strings in C besides pointers to sequences of bytes.

Since I am clearly correct on the important stuff you conti9nue to
nitpick at trivialities.

>
> I can't be bothered, but there are people still talking to him so why
> let him make the same mistakes again?
>

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

On 2022-07-09 17:36, olcott wrote:
> On 7/9/2022 6:04 PM, Ben Bacarisse wrote:
>> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
>>
>>> On 09/07/2022 21:26, Richard Damon wrote:
>>>> On 7/9/22 4:14 PM, André G. Isaak wrote:
>>>>> On 2022-07-09 14:11, Richard Damon wrote:
>>>>>
>>>>>> H is REQUIRED (to be correct) to give the answer that D will give
>>>>>> if D will give an answer,
>>>>>
>>>>> No, H is required to answer "true" if D will give an answer,
>>>>> regardless of what that answer might be.
>>>> I though in Sipser, H was supposed to be a decider where H accepts
>>>> D,x if D will accept x, and
>>>> reject if D doesn't accept x (either reject or not-answer).
>>>> D is then defined to accept if T rejects and rejects if T accepts.
>>>
>>> Yes, this is what PO is talking about in Sipser.  (You use T above,
>>> but Sipser uses H as the proposed decider, and D as the derived test
>>> TM for H, which reveals the contradiction.)  H is supposed to be
>>> deciding
>>>
>>>     A_TM = {<M,w)> : M is a TM and M accepts w}.
>>>
>>> H is not PO's normal proposed Halting decider, which has caused some
>>> confusion.
>>
>> Can I add a plea?  Given the mess that PO has made by ignoring encoding,
>> I don't think he should be allowed to get away with ignoring it for this
>> new, closely related, problem.  H (in Sipser) is a function of /strings/
>> so the translation into C should be a function with const char *
>> parameters.  That way PO must explain how to write the string the
>> represents a computation -- the obvious one being C source code.
>
> As I have told you every time that you keep bringing this up the input
> to H <is> a pointer to finite string of machine-code bytes.
>
> As you already know (yet disingenuously pretend to not know) there are
> no strings in C besides pointers to sequences of bytes.

Of course there are strings in C. A string and a pointer to a string are
two different types.

Yes, conventionally functions dealing with strings are passed pointers
to the strings rather than the strings themselves, but there is nothing
that prevents you from writing code in C in which the actual string is
passed as an argument. It's a bit more cumbersome, but it is what is
required by the definition of the problem under consideration.

André

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

On 7/9/2022 6:49 PM, André G. Isaak wrote:
> On 2022-07-09 17:36, olcott wrote:
>> On 7/9/2022 6:04 PM, Ben Bacarisse wrote:
>>> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
>>>
>>>> On 09/07/2022 21:26, Richard Damon wrote:
>>>>> On 7/9/22 4:14 PM, André G. Isaak wrote:
>>>>>> On 2022-07-09 14:11, Richard Damon wrote:
>>>>>>
>>>>>>> H is REQUIRED (to be correct) to give the answer that D will give
>>>>>>> if D will give an answer,
>>>>>>
>>>>>> No, H is required to answer "true" if D will give an answer,
>>>>>> regardless of what that answer might be.
>>>>> I though in Sipser, H was supposed to be a decider where H accepts
>>>>> D,x if D will accept x, and
>>>>> reject if D doesn't accept x (either reject or not-answer).
>>>>> D is then defined to accept if T rejects and rejects if T accepts.
>>>>
>>>> Yes, this is what PO is talking about in Sipser.  (You use T above,
>>>> but Sipser uses H as the proposed decider, and D as the derived test
>>>> TM for H, which reveals the contradiction.)  H is supposed to be
>>>> deciding
>>>>
>>>>     A_TM = {<M,w)> : M is a TM and M accepts w}.
>>>>
>>>> H is not PO's normal proposed Halting decider, which has caused some
>>>> confusion.
>>>
>>> Can I add a plea?  Given the mess that PO has made by ignoring encoding,
>>> I don't think he should be allowed to get away with ignoring it for this
>>> new, closely related, problem.  H (in Sipser) is a function of /strings/
>>> so the translation into C should be a function with const char *
>>> parameters.  That way PO must explain how to write the string the
>>> represents a computation -- the obvious one being C source code.
>>
>> As I have told you every time that you keep bringing this up the input
>> to H <is> a pointer to finite string of machine-code bytes.
>>
>> As you already know (yet disingenuously pretend to not know) there are
>> no strings in C besides pointers to sequences of bytes.
>
> Of course there are strings in C. A string and a pointer to a string are
> two different types.
>
> Yes, conventionally functions dealing with strings are passed pointers
> to the strings rather than the strings themselves,

And Ben keeps pretending to not know this:
any little trick to stay focused on rebuttal mode.

Ben and David may still fail to comprehend that x86 machine language
(having ready-made indexed directed graphs of all control flow) are much
easier for a halt decider to process than C source code.

> but there is nothing
> that prevents you from writing code in C in which the actual string is
> passed as an argument. It's a bit more cumbersome, but it is what is
> required by the definition of the problem under consideration.
>
> André
>

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

On 7/9/22 7:49 PM, André G. Isaak wrote:
> On 2022-07-09 17:36, olcott wrote:
>> On 7/9/2022 6:04 PM, Ben Bacarisse wrote:
>>> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
>>>
>>>> On 09/07/2022 21:26, Richard Damon wrote:
>>>>> On 7/9/22 4:14 PM, André G. Isaak wrote:
>>>>>> On 2022-07-09 14:11, Richard Damon wrote:
>>>>>>
>>>>>>> H is REQUIRED (to be correct) to give the answer that D will give
>>>>>>> if D will give an answer,
>>>>>>
>>>>>> No, H is required to answer "true" if D will give an answer,
>>>>>> regardless of what that answer might be.
>>>>> I though in Sipser, H was supposed to be a decider where H accepts
>>>>> D,x if D will accept x, and
>>>>> reject if D doesn't accept x (either reject or not-answer).
>>>>> D is then defined to accept if T rejects and rejects if T accepts.
>>>>
>>>> Yes, this is what PO is talking about in Sipser.  (You use T above,
>>>> but Sipser uses H as the proposed decider, and D as the derived test
>>>> TM for H, which reveals the contradiction.)  H is supposed to be
>>>> deciding
>>>>
>>>>     A_TM = {<M,w)> : M is a TM and M accepts w}.
>>>>
>>>> H is not PO's normal proposed Halting decider, which has caused some
>>>> confusion.
>>>
>>> Can I add a plea?  Given the mess that PO has made by ignoring encoding,
>>> I don't think he should be allowed to get away with ignoring it for this
>>> new, closely related, problem.  H (in Sipser) is a function of /strings/
>>> so the translation into C should be a function with const char *
>>> parameters.  That way PO must explain how to write the string the
>>> represents a computation -- the obvious one being C source code.
>>
>> As I have told you every time that you keep bringing this up the input
>> to H <is> a pointer to finite string of machine-code bytes.
>>
>> As you already know (yet disingenuously pretend to not know) there are
>> no strings in C besides pointers to sequences of bytes.
>
> Of course there are strings in C. A string and a pointer to a string are
> two different types.
>
> Yes, conventionally functions dealing with strings are passed pointers
> to the strings rather than the strings themselves, but there is nothing
> that prevents you from writing code in C in which the actual string is
> passed as an argument. It's a bit more cumbersome, but it is what is
> required by the definition of the problem under consideration.
>
> André
>

Since in C strings are arrays of characters with a terminating NUL, you
can not pass a string by itself, only as the element of a structure
(which also requires the string to be of known and declared maximum length.

You run into the problem that arrays aren't full objects by themselves,
so you can't pass array values around except by encasing them in a
structure.

On 2022-07-09 18:42, Richard Damon wrote:
>
> On 7/9/22 7:49 PM, André G. Isaak wrote:
>> On 2022-07-09 17:36, olcott wrote:
>>> On 7/9/2022 6:04 PM, Ben Bacarisse wrote:
>>>> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
>>>>
>>>>> On 09/07/2022 21:26, Richard Damon wrote:
>>>>>> On 7/9/22 4:14 PM, André G. Isaak wrote:
>>>>>>> On 2022-07-09 14:11, Richard Damon wrote:
>>>>>>>
>>>>>>>> H is REQUIRED (to be correct) to give the answer that D will
>>>>>>>> give if D will give an answer,
>>>>>>>
>>>>>>> No, H is required to answer "true" if D will give an answer,
>>>>>>> regardless of what that answer might be.
>>>>>> I though in Sipser, H was supposed to be a decider where H accepts
>>>>>> D,x if D will accept x, and
>>>>>> reject if D doesn't accept x (either reject or not-answer).
>>>>>> D is then defined to accept if T rejects and rejects if T accepts.
>>>>>
>>>>> Yes, this is what PO is talking about in Sipser.  (You use T above,
>>>>> but Sipser uses H as the proposed decider, and D as the derived test
>>>>> TM for H, which reveals the contradiction.)  H is supposed to be
>>>>> deciding
>>>>>
>>>>>     A_TM = {<M,w)> : M is a TM and M accepts w}.
>>>>>
>>>>> H is not PO's normal proposed Halting decider, which has caused some
>>>>> confusion.
>>>>
>>>> Can I add a plea?  Given the mess that PO has made by ignoring
>>>> encoding,
>>>> I don't think he should be allowed to get away with ignoring it for
>>>> this
>>>> new, closely related, problem.  H (in Sipser) is a function of
>>>> /strings/
>>>> so the translation into C should be a function with const char *
>>>> parameters.  That way PO must explain how to write the string the
>>>> represents a computation -- the obvious one being C source code.
>>>
>>> As I have told you every time that you keep bringing this up the
>>> input to H <is> a pointer to finite string of machine-code bytes.
>>>
>>> As you already know (yet disingenuously pretend to not know) there
>>> are no strings in C besides pointers to sequences of bytes.
>>
>> Of course there are strings in C. A string and a pointer to a string
>> are two different types.
>>
>> Yes, conventionally functions dealing with strings are passed pointers
>> to the strings rather than the strings themselves, but there is
>> nothing that prevents you from writing code in C in which the actual
>> string is passed as an argument. It's a bit more cumbersome, but it is
>> what is required by the definition of the problem under consideration.
>>
>> André
>>
>
> Since in C strings are arrays of characters with a terminating NUL, you
> can not pass a string by itself, only as the element of a structure
> (which also requires the string to be of known and declared maximum length.

It is possible to pass a variable-length sequence of bytes to a function
using stdarg. Of course, calling such a function with a string of
arbitrary length would be a PITA (probably easiest to manually push the
arguments onto the stack), but its not impossible.

André

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

On 2022-07-09 18:08, olcott wrote:
> On 7/9/2022 6:49 PM, André G. Isaak wrote:
>> On 2022-07-09 17:36, olcott wrote:
>>> On 7/9/2022 6:04 PM, Ben Bacarisse wrote:
>>>> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
>>>>
>>>>> On 09/07/2022 21:26, Richard Damon wrote:
>>>>>> On 7/9/22 4:14 PM, André G. Isaak wrote:
>>>>>>> On 2022-07-09 14:11, Richard Damon wrote:
>>>>>>>
>>>>>>>> H is REQUIRED (to be correct) to give the answer that D will
>>>>>>>> give if D will give an answer,
>>>>>>>
>>>>>>> No, H is required to answer "true" if D will give an answer,
>>>>>>> regardless of what that answer might be.
>>>>>> I though in Sipser, H was supposed to be a decider where H accepts
>>>>>> D,x if D will accept x, and
>>>>>> reject if D doesn't accept x (either reject or not-answer).
>>>>>> D is then defined to accept if T rejects and rejects if T accepts.
>>>>>
>>>>> Yes, this is what PO is talking about in Sipser.  (You use T above,
>>>>> but Sipser uses H as the proposed decider, and D as the derived test
>>>>> TM for H, which reveals the contradiction.)  H is supposed to be
>>>>> deciding
>>>>>
>>>>>     A_TM = {<M,w)> : M is a TM and M accepts w}.
>>>>>
>>>>> H is not PO's normal proposed Halting decider, which has caused some
>>>>> confusion.
>>>>
>>>> Can I add a plea?  Given the mess that PO has made by ignoring
>>>> encoding,
>>>> I don't think he should be allowed to get away with ignoring it for
>>>> this
>>>> new, closely related, problem.  H (in Sipser) is a function of
>>>> /strings/
>>>> so the translation into C should be a function with const char *
>>>> parameters.  That way PO must explain how to write the string the
>>>> represents a computation -- the obvious one being C source code.
>>>
>>> As I have told you every time that you keep bringing this up the
>>> input to H <is> a pointer to finite string of machine-code bytes.
>>>
>>> As you already know (yet disingenuously pretend to not know) there
>>> are no strings in C besides pointers to sequences of bytes.
>>
>> Of course there are strings in C. A string and a pointer to a string
>> are two different types.
>>
>> Yes, conventionally functions dealing with strings are passed pointers
>> to the strings rather than the strings themselves,
>
> And Ben keeps pretending to not know this:

No. He doesn't.

> any little trick to stay focused on rebuttal mode.
>
> Ben and David may still fail to comprehend that x86 machine language
> (having ready-made indexed directed graphs of all control flow) are much
> easier for a halt decider to process than C source code.

There is no 'ready-made indexed directed graph of all control flow'
provided by x86 machine code. You can work out such a directed graph
just as one can work out such a directed graph from C source code using
a more-or-less identical procedure.

Despite what you may believe, a program trace is not a directed graph,
nor does it represent the control flow of a program.

André

>> but there is nothing that prevents you from writing code in C in which
>> the actual string is passed as an argument. It's a bit more
>> cumbersome, but it is what is required by the definition of the
>> problem under consideration.

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

On 7/9/22 8:57 PM, André G. Isaak wrote:
> On 2022-07-09 18:42, Richard Damon wrote:
>>
>> On 7/9/22 7:49 PM, André G. Isaak wrote:
>>> On 2022-07-09 17:36, olcott wrote:
>>>> On 7/9/2022 6:04 PM, Ben Bacarisse wrote:
>>>>> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
>>>>>
>>>>>> On 09/07/2022 21:26, Richard Damon wrote:
>>>>>>> On 7/9/22 4:14 PM, André G. Isaak wrote:
>>>>>>>> On 2022-07-09 14:11, Richard Damon wrote:
>>>>>>>>
>>>>>>>>> H is REQUIRED (to be correct) to give the answer that D will
>>>>>>>>> give if D will give an answer,
>>>>>>>>
>>>>>>>> No, H is required to answer "true" if D will give an answer,
>>>>>>>> regardless of what that answer might be.
>>>>>>> I though in Sipser, H was supposed to be a decider where H
>>>>>>> accepts D,x if D will accept x, and
>>>>>>> reject if D doesn't accept x (either reject or not-answer).
>>>>>>> D is then defined to accept if T rejects and rejects if T accepts.
>>>>>>
>>>>>> Yes, this is what PO is talking about in Sipser.  (You use T above,
>>>>>> but Sipser uses H as the proposed decider, and D as the derived test
>>>>>> TM for H, which reveals the contradiction.)  H is supposed to be
>>>>>> deciding
>>>>>>
>>>>>>     A_TM = {<M,w)> : M is a TM and M accepts w}.
>>>>>>
>>>>>> H is not PO's normal proposed Halting decider, which has caused some
>>>>>> confusion.
>>>>>
>>>>> Can I add a plea?  Given the mess that PO has made by ignoring
>>>>> encoding,
>>>>> I don't think he should be allowed to get away with ignoring it for
>>>>> this
>>>>> new, closely related, problem.  H (in Sipser) is a function of
>>>>> /strings/
>>>>> so the translation into C should be a function with const char *
>>>>> parameters.  That way PO must explain how to write the string the
>>>>> represents a computation -- the obvious one being C source code.
>>>>
>>>> As I have told you every time that you keep bringing this up the
>>>> input to H <is> a pointer to finite string of machine-code bytes.
>>>>
>>>> As you already know (yet disingenuously pretend to not know) there
>>>> are no strings in C besides pointers to sequences of bytes.
>>>
>>> Of course there are strings in C. A string and a pointer to a string
>>> are two different types.
>>>
>>> Yes, conventionally functions dealing with strings are passed
>>> pointers to the strings rather than the strings themselves, but there
>>> is nothing that prevents you from writing code in C in which the
>>> actual string is passed as an argument. It's a bit more cumbersome,
>>> but it is what is required by the definition of the problem under
>>> consideration.
>>>
>>> André
>>>
>>
>> Since in C strings are arrays of characters with a terminating NUL,
>> you can not pass a string by itself, only as the element of a
>> structure (which also requires the string to be of known and declared
>> maximum length.
>
> It is possible to pass a variable-length sequence of bytes to a function
> using stdarg. Of course, calling such a function with a string of
> arbitrary length would be a PITA (probably easiest to manually push the
> arguments onto the stack), but its not impossible.
>
> André
>

Trying to imagine how you pass the actual string to the function except
by calling it a struct that embeds the string (in which case you
technically are not passing a string, but a struct containing a string).

The problem you run into is that the struct may require stricter
alignment than the string, so the casting conversion may be undefined
behavior.

On 7/9/2022 8:04 PM, André G. Isaak wrote:
> On 2022-07-09 18:08, olcott wrote:
>> On 7/9/2022 6:49 PM, André G. Isaak wrote:
>>> On 2022-07-09 17:36, olcott wrote:
>>>> On 7/9/2022 6:04 PM, Ben Bacarisse wrote:
>>>>> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
>>>>>
>>>>>> On 09/07/2022 21:26, Richard Damon wrote:
>>>>>>> On 7/9/22 4:14 PM, André G. Isaak wrote:
>>>>>>>> On 2022-07-09 14:11, Richard Damon wrote:
>>>>>>>>
>>>>>>>>> H is REQUIRED (to be correct) to give the answer that D will
>>>>>>>>> give if D will give an answer,
>>>>>>>>
>>>>>>>> No, H is required to answer "true" if D will give an answer,
>>>>>>>> regardless of what that answer might be.
>>>>>>> I though in Sipser, H was supposed to be a decider where H
>>>>>>> accepts D,x if D will accept x, and
>>>>>>> reject if D doesn't accept x (either reject or not-answer).
>>>>>>> D is then defined to accept if T rejects and rejects if T accepts.
>>>>>>
>>>>>> Yes, this is what PO is talking about in Sipser.  (You use T above,
>>>>>> but Sipser uses H as the proposed decider, and D as the derived test
>>>>>> TM for H, which reveals the contradiction.)  H is supposed to be
>>>>>> deciding
>>>>>>
>>>>>>     A_TM = {<M,w)> : M is a TM and M accepts w}.
>>>>>>
>>>>>> H is not PO's normal proposed Halting decider, which has caused some
>>>>>> confusion.
>>>>>
>>>>> Can I add a plea?  Given the mess that PO has made by ignoring
>>>>> encoding,
>>>>> I don't think he should be allowed to get away with ignoring it for
>>>>> this
>>>>> new, closely related, problem.  H (in Sipser) is a function of
>>>>> /strings/
>>>>> so the translation into C should be a function with const char *
>>>>> parameters.  That way PO must explain how to write the string the
>>>>> represents a computation -- the obvious one being C source code.
>>>>
>>>> As I have told you every time that you keep bringing this up the
>>>> input to H <is> a pointer to finite string of machine-code bytes.
>>>>
>>>> As you already know (yet disingenuously pretend to not know) there
>>>> are no strings in C besides pointers to sequences of bytes.
>>>
>>> Of course there are strings in C. A string and a pointer to a string
>>> are two different types.
>>>
>>> Yes, conventionally functions dealing with strings are passed
>>> pointers to the strings rather than the strings themselves,
>>
>> And Ben keeps pretending to not know this:
>
> No. He doesn't.
>
>> any little trick to stay focused on rebuttal mode.
>>
>> Ben and David may still fail to comprehend that x86 machine language
>> (having ready-made indexed directed graphs of all control flow) are
>> much easier for a halt decider to process than C source code.
>
> There is no 'ready-made indexed directed graph of all control flow'
> provided by x86 machine code.

*Sure there is this is it*
address call address
address jmp address
address jmp-condition address

The first address is the current node
The second address is the next node on the directed path

> You can work out such a directed graph
> just as one can work out such a directed graph from C source code using
> a more-or-less identical procedure.
>
> Despite what you may believe, a program trace is not a directed graph,
> nor does it represent the control flow of a program.
>
> André
>
>>> but there is nothing that prevents you from writing code in C in
>>> which the actual string is passed as an argument. It's a bit more
>>> cumbersome, but it is what is required by the definition of the
>>> problem under consideration.
>

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

On 7/9/22 9:41 PM, olcott wrote:
> On 7/9/2022 8:04 PM, André G. Isaak wrote:
>> On 2022-07-09 18:08, olcott wrote:
>>> On 7/9/2022 6:49 PM, André G. Isaak wrote:
>>>> On 2022-07-09 17:36, olcott wrote:
>>>>> On 7/9/2022 6:04 PM, Ben Bacarisse wrote:
>>>>>> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
>>>>>>
>>>>>>> On 09/07/2022 21:26, Richard Damon wrote:
>>>>>>>> On 7/9/22 4:14 PM, André G. Isaak wrote:
>>>>>>>>> On 2022-07-09 14:11, Richard Damon wrote:
>>>>>>>>>
>>>>>>>>>> H is REQUIRED (to be correct) to give the answer that D will
>>>>>>>>>> give if D will give an answer,
>>>>>>>>>
>>>>>>>>> No, H is required to answer "true" if D will give an answer,
>>>>>>>>> regardless of what that answer might be.
>>>>>>>> I though in Sipser, H was supposed to be a decider where H
>>>>>>>> accepts D,x if D will accept x, and
>>>>>>>> reject if D doesn't accept x (either reject or not-answer).
>>>>>>>> D is then defined to accept if T rejects and rejects if T accepts.
>>>>>>>
>>>>>>> Yes, this is what PO is talking about in Sipser.  (You use T above,
>>>>>>> but Sipser uses H as the proposed decider, and D as the derived test
>>>>>>> TM for H, which reveals the contradiction.)  H is supposed to be
>>>>>>> deciding
>>>>>>>
>>>>>>>     A_TM = {<M,w)> : M is a TM and M accepts w}.
>>>>>>>
>>>>>>> H is not PO's normal proposed Halting decider, which has caused some
>>>>>>> confusion.
>>>>>>
>>>>>> Can I add a plea?  Given the mess that PO has made by ignoring
>>>>>> encoding,
>>>>>> I don't think he should be allowed to get away with ignoring it
>>>>>> for this
>>>>>> new, closely related, problem.  H (in Sipser) is a function of
>>>>>> /strings/
>>>>>> so the translation into C should be a function with const char *
>>>>>> parameters.  That way PO must explain how to write the string the
>>>>>> represents a computation -- the obvious one being C source code.
>>>>>
>>>>> As I have told you every time that you keep bringing this up the
>>>>> input to H <is> a pointer to finite string of machine-code bytes.
>>>>>
>>>>> As you already know (yet disingenuously pretend to not know) there
>>>>> are no strings in C besides pointers to sequences of bytes.
>>>>
>>>> Of course there are strings in C. A string and a pointer to a string
>>>> are two different types.
>>>>
>>>> Yes, conventionally functions dealing with strings are passed
>>>> pointers to the strings rather than the strings themselves,
>>>
>>> And Ben keeps pretending to not know this:
>>
>> No. He doesn't.
>>
>>> any little trick to stay focused on rebuttal mode.
>>>
>>> Ben and David may still fail to comprehend that x86 machine language
>>> (having ready-made indexed directed graphs of all control flow) are
>>> much easier for a halt decider to process than C source code.
>>
>> There is no 'ready-made indexed directed graph of all control flow'
>> provided by x86 machine code.
>
> *Sure there is this is it*
> address call address
> address jmp address
> address jmp-condition address
>
> The first address is the current node
> The second address is the next node on the directed path
>

Obviously, you have never tried to disassemble code.

First, only by actually tracing though the code can you find where the
instruction boundries are (maybe you nave never seen intentionally
obfuscated assembly that uses jumps to middle of instructions to confuse
people trying to decode the program).

You also need to add EVERY instruction to the list to add the address to
next address links or you don't actually get a 'graph' as you
destinations won't match your sources.

You can do exactly the same operations with the source code and get
around the ability to intentionally obfusact the beginning and ends of
source blocks.

>> You can work out such a directed graph just as one can work out such a
>> directed graph from C source code using a more-or-less identical
>> procedure.
>>
>> Despite what you may believe, a program trace is not a directed graph,
>> nor does it represent the control flow of a program.
>>
>> André
>>
>>>> but there is nothing that prevents you from writing code in C in
>>>> which the actual string is passed as an argument. It's a bit more
>>>> cumbersome, but it is what is required by the definition of the
>>>> problem under consideration.
>>
>
>

On 2022-07-09 19:41, olcott wrote:
> On 7/9/2022 8:04 PM, André G. Isaak wrote:
>> On 2022-07-09 18:08, olcott wrote:
>>> On 7/9/2022 6:49 PM, André G. Isaak wrote:
>>>> On 2022-07-09 17:36, olcott wrote:
>>>>> On 7/9/2022 6:04 PM, Ben Bacarisse wrote:
>>>>>> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
>>>>>>
>>>>>>> On 09/07/2022 21:26, Richard Damon wrote:
>>>>>>>> On 7/9/22 4:14 PM, André G. Isaak wrote:
>>>>>>>>> On 2022-07-09 14:11, Richard Damon wrote:
>>>>>>>>>
>>>>>>>>>> H is REQUIRED (to be correct) to give the answer that D will
>>>>>>>>>> give if D will give an answer,
>>>>>>>>>
>>>>>>>>> No, H is required to answer "true" if D will give an answer,
>>>>>>>>> regardless of what that answer might be.
>>>>>>>> I though in Sipser, H was supposed to be a decider where H
>>>>>>>> accepts D,x if D will accept x, and
>>>>>>>> reject if D doesn't accept x (either reject or not-answer).
>>>>>>>> D is then defined to accept if T rejects and rejects if T accepts.
>>>>>>>
>>>>>>> Yes, this is what PO is talking about in Sipser.  (You use T above,
>>>>>>> but Sipser uses H as the proposed decider, and D as the derived test
>>>>>>> TM for H, which reveals the contradiction.)  H is supposed to be
>>>>>>> deciding
>>>>>>>
>>>>>>>     A_TM = {<M,w)> : M is a TM and M accepts w}.
>>>>>>>
>>>>>>> H is not PO's normal proposed Halting decider, which has caused some
>>>>>>> confusion.
>>>>>>
>>>>>> Can I add a plea?  Given the mess that PO has made by ignoring
>>>>>> encoding,
>>>>>> I don't think he should be allowed to get away with ignoring it
>>>>>> for this
>>>>>> new, closely related, problem.  H (in Sipser) is a function of
>>>>>> /strings/
>>>>>> so the translation into C should be a function with const char *
>>>>>> parameters.  That way PO must explain how to write the string the
>>>>>> represents a computation -- the obvious one being C source code.
>>>>>
>>>>> As I have told you every time that you keep bringing this up the
>>>>> input to H <is> a pointer to finite string of machine-code bytes.
>>>>>
>>>>> As you already know (yet disingenuously pretend to not know) there
>>>>> are no strings in C besides pointers to sequences of bytes.
>>>>
>>>> Of course there are strings in C. A string and a pointer to a string
>>>> are two different types.
>>>>
>>>> Yes, conventionally functions dealing with strings are passed
>>>> pointers to the strings rather than the strings themselves,
>>>
>>> And Ben keeps pretending to not know this:
>>
>> No. He doesn't.
>>
>>> any little trick to stay focused on rebuttal mode.
>>>
>>> Ben and David may still fail to comprehend that x86 machine language
>>> (having ready-made indexed directed graphs of all control flow) are
>>> much easier for a halt decider to process than C source code.
>>
>> There is no 'ready-made indexed directed graph of all control flow'
>> provided by x86 machine code.
>
> *Sure there is this is it*
> address call address
> address jmp address
> address jmp-condition address
>
> The first address is the current node
> The second address is the next node on the directed path

What you have above is a list of instructions, not a graph. Sure you can
construct a graph (putting aside the difficulties that Richard pointed
out), but doing so is no easier for assembly than it is for a list of C
instructions or pascal instructions or fortran instructions or....

André

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

On 2022-07-09 19:39, Richard Damon wrote:

> Trying to imagine how you pass the actual string to the function except
> by calling it a struct that embeds the string (in which case you
> technically are not passing a string, but a struct containing a string).
>
> The problem you run into is that the struct may require stricter
> alignment than the string, so the casting conversion may be undefined
> behavior.

Of course, Olcott insists that he is using the "x86 programming
language" and that the C is just there for human readers. You can
certainly push the bytes of an arbitrary-length zero-terminated string
onto the stack in assembly.

André

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

On Saturday, July 9, 2022 at 6:42:00 PM UTC-7, olcott wrote:
> On 7/9/2022 8:04 PM, André G. Isaak wrote:
> > On 2022-07-09 18:08, olcott wrote:
> >> On 7/9/2022 6:49 PM, André G. Isaak wrote:
> >>> On 2022-07-09 17:36, olcott wrote:
> >>>> On 7/9/2022 6:04 PM, Ben Bacarisse wrote:
> >>>>> Mike Terry <news.dead.p...@darjeeling.plus.com> writes:
> >>>>>
> >>>>>> On 09/07/2022 21:26, Richard Damon wrote:
> >>>>>>> On 7/9/22 4:14 PM, André G. Isaak wrote:
> >>>>>>>> On 2022-07-09 14:11, Richard Damon wrote:
> >>>>>>>>
> >>>>>>>>> H is REQUIRED (to be correct) to give the answer that D will
> >>>>>>>>> give if D will give an answer,
> >>>>>>>>
> >>>>>>>> No, H is required to answer "true" if D will give an answer,
> >>>>>>>> regardless of what that answer might be.
> >>>>>>> I though in Sipser, H was supposed to be a decider where H
> >>>>>>> accepts D,x if D will accept x, and
> >>>>>>> reject if D doesn't accept x (either reject or not-answer).
> >>>>>>> D is then defined to accept if T rejects and rejects if T accepts..
> >>>>>>
> >>>>>> Yes, this is what PO is talking about in Sipser. (You use T above,
> >>>>>> but Sipser uses H as the proposed decider, and D as the derived test
> >>>>>> TM for H, which reveals the contradiction.) H is supposed to be
> >>>>>> deciding
> >>>>>>
> >>>>>> A_TM = {<M,w)> : M is a TM and M accepts w}.
> >>>>>>
> >>>>>> H is not PO's normal proposed Halting decider, which has caused some
> >>>>>> confusion.
> >>>>>
> >>>>> Can I add a plea? Given the mess that PO has made by ignoring
> >>>>> encoding,
> >>>>> I don't think he should be allowed to get away with ignoring it for
> >>>>> this
> >>>>> new, closely related, problem. H (in Sipser) is a function of
> >>>>> /strings/
> >>>>> so the translation into C should be a function with const char *
> >>>>> parameters. That way PO must explain how to write the string the
> >>>>> represents a computation -- the obvious one being C source code.
> >>>>
> >>>> As I have told you every time that you keep bringing this up the
> >>>> input to H <is> a pointer to finite string of machine-code bytes.
> >>>>
> >>>> As you already know (yet disingenuously pretend to not know) there
> >>>> are no strings in C besides pointers to sequences of bytes.
> >>>
> >>> Of course there are strings in C. A string and a pointer to a string
> >>> are two different types.
> >>>
> >>> Yes, conventionally functions dealing with strings are passed
> >>> pointers to the strings rather than the strings themselves,
> >>
> >> And Ben keeps pretending to not know this:
> >
> > No. He doesn't.
> >
> >> any little trick to stay focused on rebuttal mode.
> >>
> >> Ben and David may still fail to comprehend that x86 machine language
> >> (having ready-made indexed directed graphs of all control flow) are
> >> much easier for a halt decider to process than C source code.
> >
> > There is no 'ready-made indexed directed graph of all control flow'
> > provided by x86 machine code.
> *Sure there is this is it*
> address call address
> address jmp address
> address jmp-condition address
>
> The first address is the current node
> The second address is the next node on the directed path
> > You can work out such a directed graph
> > just as one can work out such a directed graph from C source code using
> > a more-or-less identical procedure.
> >
> > Despite what you may believe, a program trace is not a directed graph,
> > nor does it represent the control flow of a program.
>
Suppose I am given a program in assembly form. What exactly do I do to
understand the control structure?

First I simplify by throwing away every instruction that is neither a jump
nor a jump target. Note all calls are removed. Then I mark all the
instructions as UNTESTED. Then I start the test loop.

In the test loop I look at the next instruction. If it is UNTESTED I change
that attribute to TESTED and go back for another step in the loop. If it
is TESTED I have discovered a loop. I create a loop record and copy all
the instructions from the current place around the the loop into the
loop record. If any of instruction is in a loop I add a loop dependency
record - the new loop is in the old one. For efficiency I probably make
loop membership an instruction attribute. Finally I pop the alternative
stack and get the next instruction to be tasted. The alternative is built
by pushing the target of every jump instruction onto it. If the alternative
stack is empty we are done.

Jumps to outside the program do not generate alternatives.

After that things get messy. But I do find the loops.

On 7/9/2022 9:04 PM, André G. Isaak wrote:
> On 2022-07-09 19:41, olcott wrote:
>> On 7/9/2022 8:04 PM, André G. Isaak wrote:
>>> On 2022-07-09 18:08, olcott wrote:
>>>> On 7/9/2022 6:49 PM, André G. Isaak wrote:
>>>>> On 2022-07-09 17:36, olcott wrote:
>>>>>> On 7/9/2022 6:04 PM, Ben Bacarisse wrote:
>>>>>>> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
>>>>>>>
>>>>>>>> On 09/07/2022 21:26, Richard Damon wrote:
>>>>>>>>> On 7/9/22 4:14 PM, André G. Isaak wrote:
>>>>>>>>>> On 2022-07-09 14:11, Richard Damon wrote:
>>>>>>>>>>
>>>>>>>>>>> H is REQUIRED (to be correct) to give the answer that D will
>>>>>>>>>>> give if D will give an answer,
>>>>>>>>>>
>>>>>>>>>> No, H is required to answer "true" if D will give an answer,
>>>>>>>>>> regardless of what that answer might be.
>>>>>>>>> I though in Sipser, H was supposed to be a decider where H
>>>>>>>>> accepts D,x if D will accept x, and
>>>>>>>>> reject if D doesn't accept x (either reject or not-answer).
>>>>>>>>> D is then defined to accept if T rejects and rejects if T accepts.
>>>>>>>>
>>>>>>>> Yes, this is what PO is talking about in Sipser.  (You use T above,
>>>>>>>> but Sipser uses H as the proposed decider, and D as the derived
>>>>>>>> test
>>>>>>>> TM for H, which reveals the contradiction.)  H is supposed to be
>>>>>>>> deciding
>>>>>>>>
>>>>>>>>     A_TM = {<M,w)> : M is a TM and M accepts w}.
>>>>>>>>
>>>>>>>> H is not PO's normal proposed Halting decider, which has caused
>>>>>>>> some
>>>>>>>> confusion.
>>>>>>>
>>>>>>> Can I add a plea?  Given the mess that PO has made by ignoring
>>>>>>> encoding,
>>>>>>> I don't think he should be allowed to get away with ignoring it
>>>>>>> for this
>>>>>>> new, closely related, problem.  H (in Sipser) is a function of
>>>>>>> /strings/
>>>>>>> so the translation into C should be a function with const char *
>>>>>>> parameters.  That way PO must explain how to write the string the
>>>>>>> represents a computation -- the obvious one being C source code.
>>>>>>
>>>>>> As I have told you every time that you keep bringing this up the
>>>>>> input to H <is> a pointer to finite string of machine-code bytes.
>>>>>>
>>>>>> As you already know (yet disingenuously pretend to not know) there
>>>>>> are no strings in C besides pointers to sequences of bytes.
>>>>>
>>>>> Of course there are strings in C. A string and a pointer to a
>>>>> string are two different types.
>>>>>
>>>>> Yes, conventionally functions dealing with strings are passed
>>>>> pointers to the strings rather than the strings themselves,
>>>>
>>>> And Ben keeps pretending to not know this:
>>>
>>> No. He doesn't.
>>>
>>>> any little trick to stay focused on rebuttal mode.
>>>>
>>>> Ben and David may still fail to comprehend that x86 machine language
>>>> (having ready-made indexed directed graphs of all control flow) are
>>>> much easier for a halt decider to process than C source code.
>>>
>>> There is no 'ready-made indexed directed graph of all control flow'
>>> provided by x86 machine code.
>>
>> *Sure there is this is it*
>> address call address
>> address jmp address
>> address jmp-condition address
>>
>> The first address is the current node
>> The second address is the next node on the directed path
>
> What you have above is a list of instructions, not a graph. Sure you can
> construct a graph (putting aside the difficulties that Richard pointed

I never see anything that Richard says.
I gave up on him because he keeps perpetually making the same mistakes.

Neither Richard nor Flibble can possibly understand that every function
called in infinite recursion never returns to its caller. Because of
this I gave up on those technically incompetent two.

It seems that both you and David fail to understand how much more
difficult it would be to analyze control flow without the ready-made
directed graph that machine language provides. Neither one of you can
ever understand that it really is a ready-made directed graph.

At least you would fully understand the concept of unreachable code.

> out), but doing so is no easier for assembly than it is for a list of C
> instructions or pascal instructions or fortran instructions or....
>
> André
>

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

On 7/9/2022 9:15 PM, André G. Isaak wrote:
> On 2022-07-09 19:39, Richard Damon wrote:
>
>> Trying to imagine how you pass the actual string to the function
>> except by calling it a struct that embeds the string (in which case
>> you technically are not passing a string, but a struct containing a
>> string).
>>
>> The problem you run into is that the struct may require stricter
>> alignment than the string, so the casting conversion may be undefined
>> behavior.
>
> Of course, Olcott insists that he is using the "x86 programming
> language" and that the C is just there for human readers. You can
> certainly push the bytes of an arbitrary-length zero-terminated string
> onto the stack in assembly.

Such a crazy idea. You can also cross the street by going all the way
around the world in the opposite direction of crossing the street.

>
> André
>

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

On 7/9/2022 9:20 PM, dklei...@gmail.com wrote:
> On Saturday, July 9, 2022 at 6:42:00 PM UTC-7, olcott wrote:
>> On 7/9/2022 8:04 PM, André G. Isaak wrote:
>>> On 2022-07-09 18:08, olcott wrote:
>>>> On 7/9/2022 6:49 PM, André G. Isaak wrote:
>>>>> On 2022-07-09 17:36, olcott wrote:
>>>>>> On 7/9/2022 6:04 PM, Ben Bacarisse wrote:
>>>>>>> Mike Terry <news.dead.p...@darjeeling.plus.com> writes:
>>>>>>>
>>>>>>>> On 09/07/2022 21:26, Richard Damon wrote:
>>>>>>>>> On 7/9/22 4:14 PM, André G. Isaak wrote:
>>>>>>>>>> On 2022-07-09 14:11, Richard Damon wrote:
>>>>>>>>>>
>>>>>>>>>>> H is REQUIRED (to be correct) to give the answer that D will
>>>>>>>>>>> give if D will give an answer,
>>>>>>>>>>
>>>>>>>>>> No, H is required to answer "true" if D will give an answer,
>>>>>>>>>> regardless of what that answer might be.
>>>>>>>>> I though in Sipser, H was supposed to be a decider where H
>>>>>>>>> accepts D,x if D will accept x, and
>>>>>>>>> reject if D doesn't accept x (either reject or not-answer).
>>>>>>>>> D is then defined to accept if T rejects and rejects if T accepts.
>>>>>>>>
>>>>>>>> Yes, this is what PO is talking about in Sipser. (You use T above,
>>>>>>>> but Sipser uses H as the proposed decider, and D as the derived test
>>>>>>>> TM for H, which reveals the contradiction.) H is supposed to be
>>>>>>>> deciding
>>>>>>>>
>>>>>>>> A_TM = {<M,w)> : M is a TM and M accepts w}.
>>>>>>>>
>>>>>>>> H is not PO's normal proposed Halting decider, which has caused some
>>>>>>>> confusion.
>>>>>>>
>>>>>>> Can I add a plea? Given the mess that PO has made by ignoring
>>>>>>> encoding,
>>>>>>> I don't think he should be allowed to get away with ignoring it for
>>>>>>> this
>>>>>>> new, closely related, problem. H (in Sipser) is a function of
>>>>>>> /strings/
>>>>>>> so the translation into C should be a function with const char *
>>>>>>> parameters. That way PO must explain how to write the string the
>>>>>>> represents a computation -- the obvious one being C source code.
>>>>>>
>>>>>> As I have told you every time that you keep bringing this up the
>>>>>> input to H <is> a pointer to finite string of machine-code bytes.
>>>>>>
>>>>>> As you already know (yet disingenuously pretend to not know) there
>>>>>> are no strings in C besides pointers to sequences of bytes.
>>>>>
>>>>> Of course there are strings in C. A string and a pointer to a string
>>>>> are two different types.
>>>>>
>>>>> Yes, conventionally functions dealing with strings are passed
>>>>> pointers to the strings rather than the strings themselves,
>>>>
>>>> And Ben keeps pretending to not know this:
>>>
>>> No. He doesn't.
>>>
>>>> any little trick to stay focused on rebuttal mode.
>>>>
>>>> Ben and David may still fail to comprehend that x86 machine language
>>>> (having ready-made indexed directed graphs of all control flow) are
>>>> much easier for a halt decider to process than C source code.
>>>
>>> There is no 'ready-made indexed directed graph of all control flow'
>>> provided by x86 machine code.
>> *Sure there is this is it*
>> address call address
>> address jmp address
>> address jmp-condition address
>>
>> The first address is the current node
>> The second address is the next node on the directed path
>>> You can work out such a directed graph
>>> just as one can work out such a directed graph from C source code using
>>> a more-or-less identical procedure.
>>>
>>> Despite what you may believe, a program trace is not a directed graph,
>>> nor does it represent the control flow of a program.
>>
> Suppose I am given a program in assembly form. What exactly do I do to
> understand the control structure?
>

The machine has to understand the control flow structure. This is
simplest with the ready-made directed graph that machine-code provides.
A human can simply look at the C source to see the control flow.

The human cannot see what the halt decider is doing from the C source
because the halt decider is only looking at the machine-code. I
carefully disassemble this for human consumption.

The stripped down C source-code of the simplest halt decider and its
simplest inputs is down to 313 lines. The most complex version is 647
lines, has four different halt deciders and many sample inputs.

> First I simplify by throwing away every instruction that is neither a jump
> nor a jump target. Note all calls are removed. Then I mark all the
> instructions as UNTESTED. Then I start the test loop.
>
> In the test loop I look at the next instruction. If it is UNTESTED I change
> that attribute to TESTED and go back for another step in the loop. If it
> is TESTED I have discovered a loop. I create a loop record and copy all
> the instructions from the current place around the the loop into the
> loop record. If any of instruction is in a loop I add a loop dependency
> record - the new loop is in the old one. For efficiency I probably make
> loop membership an instruction attribute. Finally I pop the alternative
> stack and get the next instruction to be tasted. The alternative is built
> by pushing the target of every jump instruction onto it. If the alternative
> stack is empty we are done.
>
> Jumps to outside the program do not generate alternatives.
>
> After that things get messy. But I do find the loops.

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

On 2022-07-09 20:34, olcott wrote:
> On 7/9/2022 9:20 PM, dklei...@gmail.com wrote:
>> On Saturday, July 9, 2022 at 6:42:00 PM UTC-7, olcott wrote:
>>> On 7/9/2022 8:04 PM, André G. Isaak wrote:
>>>> On 2022-07-09 18:08, olcott wrote:
>>>>> On 7/9/2022 6:49 PM, André G. Isaak wrote:
>>>>>> On 2022-07-09 17:36, olcott wrote:
>>>>>>> On 7/9/2022 6:04 PM, Ben Bacarisse wrote:
>>>>>>>> Mike Terry <news.dead.p...@darjeeling.plus.com> writes:
>>>>>>>>
>>>>>>>>> On 09/07/2022 21:26, Richard Damon wrote:
>>>>>>>>>> On 7/9/22 4:14 PM, André G. Isaak wrote:
>>>>>>>>>>> On 2022-07-09 14:11, Richard Damon wrote:
>>>>>>>>>>>
>>>>>>>>>>>> H is REQUIRED (to be correct) to give the answer that D will
>>>>>>>>>>>> give if D will give an answer,
>>>>>>>>>>>
>>>>>>>>>>> No, H is required to answer "true" if D will give an answer,
>>>>>>>>>>> regardless of what that answer might be.
>>>>>>>>>> I though in Sipser, H was supposed to be a decider where H
>>>>>>>>>> accepts D,x if D will accept x, and
>>>>>>>>>> reject if D doesn't accept x (either reject or not-answer).
>>>>>>>>>> D is then defined to accept if T rejects and rejects if T
>>>>>>>>>> accepts.
>>>>>>>>>
>>>>>>>>> Yes, this is what PO is talking about in Sipser.  (You use T
>>>>>>>>> above,
>>>>>>>>> but Sipser uses H as the proposed decider, and D as the derived
>>>>>>>>> test
>>>>>>>>> TM for H, which reveals the contradiction.)  H is supposed to be
>>>>>>>>> deciding
>>>>>>>>>
>>>>>>>>>      A_TM = {<M,w)> : M is a TM and M accepts w}.
>>>>>>>>>
>>>>>>>>> H is not PO's normal proposed Halting decider, which has caused
>>>>>>>>> some
>>>>>>>>> confusion.
>>>>>>>>
>>>>>>>> Can I add a plea?  Given the mess that PO has made by ignoring
>>>>>>>> encoding,
>>>>>>>> I don't think he should be allowed to get away with ignoring it for
>>>>>>>> this
>>>>>>>> new, closely related, problem.  H (in Sipser) is a function of
>>>>>>>> /strings/
>>>>>>>> so the translation into C should be a function with const char *
>>>>>>>> parameters.  That way PO must explain how to write the string the
>>>>>>>> represents a computation -- the obvious one being C source code.
>>>>>>>
>>>>>>> As I have told you every time that you keep bringing this up the
>>>>>>> input to H <is> a pointer to finite string of machine-code bytes.
>>>>>>>
>>>>>>> As you already know (yet disingenuously pretend to not know) there
>>>>>>> are no strings in C besides pointers to sequences of bytes.
>>>>>>
>>>>>> Of course there are strings in C. A string and a pointer to a string
>>>>>> are two different types.
>>>>>>
>>>>>> Yes, conventionally functions dealing with strings are passed
>>>>>> pointers to the strings rather than the strings themselves,
>>>>>
>>>>> And Ben keeps pretending to not know this:
>>>>
>>>> No. He doesn't.
>>>>
>>>>> any little trick to stay focused on rebuttal mode.
>>>>>
>>>>> Ben and David may still fail to comprehend that x86 machine language
>>>>> (having ready-made indexed directed graphs of all control flow) are
>>>>> much easier for a halt decider to process than C source code.
>>>>
>>>> There is no 'ready-made indexed directed graph of all control flow'
>>>> provided by x86 machine code.
>>> *Sure there is this is it*
>>> address call address
>>> address jmp address
>>> address jmp-condition address
>>>
>>> The first address is the current node
>>> The second address is the next node on the directed path
>>>> You can work out such a directed graph
>>>> just as one can work out such a directed graph from C source code using
>>>> a more-or-less identical procedure.
>>>>
>>>> Despite what you may believe, a program trace is not a directed graph,
>>>> nor does it represent the control flow of a program.
>>>
>> Suppose I am given a program in assembly form. What exactly do I do to
>> understand the control structure?
>>
>
> The machine has to understand the control flow structure. This is
> simplest with the ready-made directed graph that machine-code provides.

The machine understands the x86 instructions. But it doesn't see any
sort of 'control flow structure' in those instructions, nor does it
generate any sort of graph. It simply executes instructions one at a
time. For a given input there may be many instructions which the machine
may never even see since they lie on branches not taken for that input.

To generate a directed-graph showing flow control would involve writing
a program which analyzes the x86 instructions to create such a graph by
considering *all* possible branches, not just the ones taken for some
input. This isn't something your machine does automagically, nor is it
something present in the x86 assembly listing. And such a program is no
easier to write than one which analyzes C instructions to create such a
graph.

André

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

On 7/9/22 10:21 PM, olcott wrote:
> On 7/9/2022 9:04 PM, André G. Isaak wrote:
>> On 2022-07-09 19:41, olcott wrote:
>>> On 7/9/2022 8:04 PM, André G. Isaak wrote:
>>>> On 2022-07-09 18:08, olcott wrote:
>>>>> On 7/9/2022 6:49 PM, André G. Isaak wrote:
>>>>>> On 2022-07-09 17:36, olcott wrote:
>>>>>>> On 7/9/2022 6:04 PM, Ben Bacarisse wrote:
>>>>>>>> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
>>>>>>>>
>>>>>>>>> On 09/07/2022 21:26, Richard Damon wrote:
>>>>>>>>>> On 7/9/22 4:14 PM, André G. Isaak wrote:
>>>>>>>>>>> On 2022-07-09 14:11, Richard Damon wrote:
>>>>>>>>>>>
>>>>>>>>>>>> H is REQUIRED (to be correct) to give the answer that D will
>>>>>>>>>>>> give if D will give an answer,
>>>>>>>>>>>
>>>>>>>>>>> No, H is required to answer "true" if D will give an answer,
>>>>>>>>>>> regardless of what that answer might be.
>>>>>>>>>> I though in Sipser, H was supposed to be a decider where H
>>>>>>>>>> accepts D,x if D will accept x, and
>>>>>>>>>> reject if D doesn't accept x (either reject or not-answer).
>>>>>>>>>> D is then defined to accept if T rejects and rejects if T
>>>>>>>>>> accepts.
>>>>>>>>>
>>>>>>>>> Yes, this is what PO is talking about in Sipser.  (You use T
>>>>>>>>> above,
>>>>>>>>> but Sipser uses H as the proposed decider, and D as the derived
>>>>>>>>> test
>>>>>>>>> TM for H, which reveals the contradiction.)  H is supposed to be
>>>>>>>>> deciding
>>>>>>>>>
>>>>>>>>>     A_TM = {<M,w)> : M is a TM and M accepts w}.
>>>>>>>>>
>>>>>>>>> H is not PO's normal proposed Halting decider, which has caused
>>>>>>>>> some
>>>>>>>>> confusion.
>>>>>>>>
>>>>>>>> Can I add a plea?  Given the mess that PO has made by ignoring
>>>>>>>> encoding,
>>>>>>>> I don't think he should be allowed to get away with ignoring it
>>>>>>>> for this
>>>>>>>> new, closely related, problem.  H (in Sipser) is a function of
>>>>>>>> /strings/
>>>>>>>> so the translation into C should be a function with const char *
>>>>>>>> parameters.  That way PO must explain how to write the string the
>>>>>>>> represents a computation -- the obvious one being C source code.
>>>>>>>
>>>>>>> As I have told you every time that you keep bringing this up the
>>>>>>> input to H <is> a pointer to finite string of machine-code bytes.
>>>>>>>
>>>>>>> As you already know (yet disingenuously pretend to not know)
>>>>>>> there are no strings in C besides pointers to sequences of bytes.
>>>>>>
>>>>>> Of course there are strings in C. A string and a pointer to a
>>>>>> string are two different types.
>>>>>>
>>>>>> Yes, conventionally functions dealing with strings are passed
>>>>>> pointers to the strings rather than the strings themselves,
>>>>>
>>>>> And Ben keeps pretending to not know this:
>>>>
>>>> No. He doesn't.
>>>>
>>>>> any little trick to stay focused on rebuttal mode.
>>>>>
>>>>> Ben and David may still fail to comprehend that x86 machine
>>>>> language (having ready-made indexed directed graphs of all control
>>>>> flow) are much easier for a halt decider to process than C source
>>>>> code.
>>>>
>>>> There is no 'ready-made indexed directed graph of all control flow'
>>>> provided by x86 machine code.
>>>
>>> *Sure there is this is it*
>>> address call address
>>> address jmp address
>>> address jmp-condition address
>>>
>>> The first address is the current node
>>> The second address is the next node on the directed path
>>
>> What you have above is a list of instructions, not a graph. Sure you
>> can construct a graph (putting aside the difficulties that Richard
>> pointed
>
> I never see anything that Richard says.
> I gave up on him because he keeps perpetually making the same mistakes.
>
> Neither Richard nor Flibble can possibly understand that every function
> called in infinite recursion never returns to its caller. Because of
> this I gave up on those technically incompetent two.
>

No, you don't understand that a pure function must do the same thing for
every call with the same paramaters, and thus P calling H(P,P) can't
create the infinite recursion you claim if H(P,P) also returns 0 in some
case.

> It seems that both you and David fail to understand how much more
> difficult it would be to analyze control flow without the ready-made
> directed graph that machine language provides. Neither one of you can
> ever understand that it really is a ready-made directed graph.

Nope, you don't understand that the x86 is MORE dificult because it
DOESN'T provide an actual conftol flow until you actually find out where
instructions state.

With C code, you KNOW that blocks are only entered from the top unless
there is a lable inside. There are limited entry and exit points, welll
defined by the syntax of the code (instead of needing to find the
semantics of the x86 code)

>
> At least you would fully understand the concept of unreachable code.

Except that code you call "unreachable" is reached.

>
>> out), but doing so is no easier for assembly than it is for a list of
>> C instructions or pascal instructions or fortran instructions or....
>>
>> André
>>
>
>

On 7/9/22 10:34 PM, olcott wrote:
> On 7/9/2022 9:20 PM, dklei...@gmail.com wrote:
>> On Saturday, July 9, 2022 at 6:42:00 PM UTC-7, olcott wrote:
>>> On 7/9/2022 8:04 PM, André G. Isaak wrote:
>>>> On 2022-07-09 18:08, olcott wrote:
>>>>> On 7/9/2022 6:49 PM, André G. Isaak wrote:
>>>>>> On 2022-07-09 17:36, olcott wrote:
>>>>>>> On 7/9/2022 6:04 PM, Ben Bacarisse wrote:
>>>>>>>> Mike Terry <news.dead.p...@darjeeling.plus.com> writes:
>>>>>>>>
>>>>>>>>> On 09/07/2022 21:26, Richard Damon wrote:
>>>>>>>>>> On 7/9/22 4:14 PM, André G. Isaak wrote:
>>>>>>>>>>> On 2022-07-09 14:11, Richard Damon wrote:
>>>>>>>>>>>
>>>>>>>>>>>> H is REQUIRED (to be correct) to give the answer that D will
>>>>>>>>>>>> give if D will give an answer,
>>>>>>>>>>>
>>>>>>>>>>> No, H is required to answer "true" if D will give an answer,
>>>>>>>>>>> regardless of what that answer might be.
>>>>>>>>>> I though in Sipser, H was supposed to be a decider where H
>>>>>>>>>> accepts D,x if D will accept x, and
>>>>>>>>>> reject if D doesn't accept x (either reject or not-answer).
>>>>>>>>>> D is then defined to accept if T rejects and rejects if T
>>>>>>>>>> accepts.
>>>>>>>>>
>>>>>>>>> Yes, this is what PO is talking about in Sipser.  (You use T
>>>>>>>>> above,
>>>>>>>>> but Sipser uses H as the proposed decider, and D as the derived
>>>>>>>>> test
>>>>>>>>> TM for H, which reveals the contradiction.)  H is supposed to be
>>>>>>>>> deciding
>>>>>>>>>
>>>>>>>>>      A_TM = {<M,w)> : M is a TM and M accepts w}.
>>>>>>>>>
>>>>>>>>> H is not PO's normal proposed Halting decider, which has caused
>>>>>>>>> some
>>>>>>>>> confusion.
>>>>>>>>
>>>>>>>> Can I add a plea?  Given the mess that PO has made by ignoring
>>>>>>>> encoding,
>>>>>>>> I don't think he should be allowed to get away with ignoring it for
>>>>>>>> this
>>>>>>>> new, closely related, problem.  H (in Sipser) is a function of
>>>>>>>> /strings/
>>>>>>>> so the translation into C should be a function with const char *
>>>>>>>> parameters.  That way PO must explain how to write the string the
>>>>>>>> represents a computation -- the obvious one being C source code.
>>>>>>>
>>>>>>> As I have told you every time that you keep bringing this up the
>>>>>>> input to H <is> a pointer to finite string of machine-code bytes.
>>>>>>>
>>>>>>> As you already know (yet disingenuously pretend to not know) there
>>>>>>> are no strings in C besides pointers to sequences of bytes.
>>>>>>
>>>>>> Of course there are strings in C. A string and a pointer to a string
>>>>>> are two different types.
>>>>>>
>>>>>> Yes, conventionally functions dealing with strings are passed
>>>>>> pointers to the strings rather than the strings themselves,
>>>>>
>>>>> And Ben keeps pretending to not know this:
>>>>
>>>> No. He doesn't.
>>>>
>>>>> any little trick to stay focused on rebuttal mode.
>>>>>
>>>>> Ben and David may still fail to comprehend that x86 machine language
>>>>> (having ready-made indexed directed graphs of all control flow) are
>>>>> much easier for a halt decider to process than C source code.
>>>>
>>>> There is no 'ready-made indexed directed graph of all control flow'
>>>> provided by x86 machine code.
>>> *Sure there is this is it*
>>> address call address
>>> address jmp address
>>> address jmp-condition address
>>>
>>> The first address is the current node
>>> The second address is the next node on the directed path
>>>> You can work out such a directed graph
>>>> just as one can work out such a directed graph from C source code using
>>>> a more-or-less identical procedure.
>>>>
>>>> Despite what you may believe, a program trace is not a directed graph,
>>>> nor does it represent the control flow of a program.
>>>
>> Suppose I am given a program in assembly form. What exactly do I do to
>> understand the control structure?
>>
>
> The machine has to understand the control flow structure. This is
> simplest with the ready-made directed graph that machine-code provides.
> A human can simply look at the C source to see the control flow.
>

The machine understand what the code says when it executes it, yes.
Until you know the instruction boundries, you don't know what the
instructions mean.

> The human cannot see what the halt decider is doing from the C source
> because the halt decider is only looking at the machine-code. I
> carefully disassemble this for human consumption.

Only because you have defined your input to be encoded as x86 binary.

Make your decider based on parsing C code, and we can understand that
directly.

>
> The stripped down C source-code of the simplest halt decider and its
> simplest inputs is down to 313 lines. The most complex version is 647
> lines, has four different halt deciders and many sample inputs.

Except you decider gets it wrong, because it presumes that when the
simulate P(P) calls H(P,P) that the results is infinite recursion when
in actuality since H(P,P) aborts its simulation and returns 0, H needed
to have assumed that H(P,P) returned 0, not but non-halting.

H thus is shown to NOT be using valid logic, because you introduced
INCORRECT rules into your logic (i.e. LIES).

You seem to presume that H can be BOTH a complete and correct
enterpreter and also abort its simulation.

You presume that there exists a finite point in time when H can actually
prove that its input is non-halting to be able to correct abort its
simulation.

This is just invoking the fallicy of presuming the conclusion. Yes, if
someone gives you a working Halt Decider, you can build your Halt
Decider around it. Until someone can actually make that ideal halt
decider (that doens't exist) you can't do what you claim.

This is like in a proof you use a step, "If we assume that 2 < 1, then
we can show ...."

>
>> First I simplify by throwing away every instruction that is neither a
>> jump
>> nor a jump target. Note all calls are removed. Then I mark all the
>> instructions as UNTESTED. Then I start the test loop.
>>
>> In the test loop I look at the next instruction. If it is UNTESTED I
>> change
>> that attribute to TESTED and go back for another step in the loop. If it
>> is TESTED I have discovered a loop. I create a loop record and copy all
>> the instructions from the current place around the the loop into the
>> loop record. If any of instruction is in a loop I add a loop dependency
>> record - the new loop is in the old one. For efficiency I probably make
>> loop membership an instruction attribute. Finally I pop the alternative
>> stack and get the next instruction to be tasted. The alternative is built
>> by pushing the target of every jump instruction onto it.  If the
>> alternative
>> stack is empty we are done.
>>
>> Jumps to outside the program do not generate alternatives.
>>
>> After that things get messy. But I do find the loops.
>
>

On 7/9/2022 9:46 PM, André G. Isaak wrote:
> On 2022-07-09 20:34, olcott wrote:
>> On 7/9/2022 9:20 PM, dklei...@gmail.com wrote:
>>> On Saturday, July 9, 2022 at 6:42:00 PM UTC-7, olcott wrote:
>>>> On 7/9/2022 8:04 PM, André G. Isaak wrote:
>>>>> On 2022-07-09 18:08, olcott wrote:
>>>>>> On 7/9/2022 6:49 PM, André G. Isaak wrote:
>>>>>>> On 2022-07-09 17:36, olcott wrote:
>>>>>>>> On 7/9/2022 6:04 PM, Ben Bacarisse wrote:
>>>>>>>>> Mike Terry <news.dead.p...@darjeeling.plus.com> writes:
>>>>>>>>>
>>>>>>>>>> On 09/07/2022 21:26, Richard Damon wrote:
>>>>>>>>>>> On 7/9/22 4:14 PM, André G. Isaak wrote:
>>>>>>>>>>>> On 2022-07-09 14:11, Richard Damon wrote:
>>>>>>>>>>>>
>>>>>>>>>>>>> H is REQUIRED (to be correct) to give the answer that D will
>>>>>>>>>>>>> give if D will give an answer,
>>>>>>>>>>>>
>>>>>>>>>>>> No, H is required to answer "true" if D will give an answer,
>>>>>>>>>>>> regardless of what that answer might be.
>>>>>>>>>>> I though in Sipser, H was supposed to be a decider where H
>>>>>>>>>>> accepts D,x if D will accept x, and
>>>>>>>>>>> reject if D doesn't accept x (either reject or not-answer).
>>>>>>>>>>> D is then defined to accept if T rejects and rejects if T
>>>>>>>>>>> accepts.
>>>>>>>>>>
>>>>>>>>>> Yes, this is what PO is talking about in Sipser.  (You use T
>>>>>>>>>> above,
>>>>>>>>>> but Sipser uses H as the proposed decider, and D as the
>>>>>>>>>> derived test
>>>>>>>>>> TM for H, which reveals the contradiction.)  H is supposed to be
>>>>>>>>>> deciding
>>>>>>>>>>
>>>>>>>>>>      A_TM = {<M,w)> : M is a TM and M accepts w}.
>>>>>>>>>>
>>>>>>>>>> H is not PO's normal proposed Halting decider, which has
>>>>>>>>>> caused some
>>>>>>>>>> confusion.
>>>>>>>>>
>>>>>>>>> Can I add a plea?  Given the mess that PO has made by ignoring
>>>>>>>>> encoding,
>>>>>>>>> I don't think he should be allowed to get away with ignoring it
>>>>>>>>> for
>>>>>>>>> this
>>>>>>>>> new, closely related, problem.  H (in Sipser) is a function of
>>>>>>>>> /strings/
>>>>>>>>> so the translation into C should be a function with const char *
>>>>>>>>> parameters.  That way PO must explain how to write the string the
>>>>>>>>> represents a computation -- the obvious one being C source code.
>>>>>>>>
>>>>>>>> As I have told you every time that you keep bringing this up the
>>>>>>>> input to H <is> a pointer to finite string of machine-code bytes.
>>>>>>>>
>>>>>>>> As you already know (yet disingenuously pretend to not know) there
>>>>>>>> are no strings in C besides pointers to sequences of bytes.
>>>>>>>
>>>>>>> Of course there are strings in C. A string and a pointer to a string
>>>>>>> are two different types.
>>>>>>>
>>>>>>> Yes, conventionally functions dealing with strings are passed
>>>>>>> pointers to the strings rather than the strings themselves,
>>>>>>
>>>>>> And Ben keeps pretending to not know this:
>>>>>
>>>>> No. He doesn't.
>>>>>
>>>>>> any little trick to stay focused on rebuttal mode.
>>>>>>
>>>>>> Ben and David may still fail to comprehend that x86 machine language
>>>>>> (having ready-made indexed directed graphs of all control flow) are
>>>>>> much easier for a halt decider to process than C source code.
>>>>>
>>>>> There is no 'ready-made indexed directed graph of all control flow'
>>>>> provided by x86 machine code.
>>>> *Sure there is this is it*
>>>> address call address
>>>> address jmp address
>>>> address jmp-condition address
>>>>
>>>> The first address is the current node
>>>> The second address is the next node on the directed path
>>>>> You can work out such a directed graph
>>>>> just as one can work out such a directed graph from C source code
>>>>> using
>>>>> a more-or-less identical procedure.
>>>>>
>>>>> Despite what you may believe, a program trace is not a directed graph,
>>>>> nor does it represent the control flow of a program.
>>>>
>>> Suppose I am given a program in assembly form. What exactly do I do to
>>> understand the control structure?
>>>
>>
>> The machine has to understand the control flow structure. This is
>> simplest with the ready-made directed graph that machine-code provides.
>
> The machine understands the x86 instructions. But it doesn't see any
> sort of 'control flow structure' in those instructions, nor does it
> generate any sort of graph.

The halt decider generates the graph

> It simply executes instructions one at a
> time. For a given input there may be many instructions which the machine
> may never even see since they lie on branches not taken for that input.
>
> To generate a directed-graph showing flow control would involve writing
> a program which analyzes the x86 instructions to create such a graph by
> considering *all* possible branches, not just the ones taken for some
> input.

The halt decider need not examine all the branches. It only needs to
examine the possibly branches from the current location. It is not even
aware that dead code exists because it never gets there.

> This isn't something your machine does automagically, nor is it
> something present in the x86 assembly listing. And such a program is no
> easier to write than one which analyzes C instructions to create such a
> graph.
>
> André
>
>

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer