https://www.liarparadox.org/Sipser_165_167.pdf

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("D(D) = ", 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 7/9/22 2:08 PM, olcott wrote:
> https://www.liarparadox.org/Sipser_165_167.pdf
>
> 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("D(D) = ", D(D));
> }
>
>

Mostly right, you want to print both H(D,D) and D(D) (probably H(D,D)
first as that is REQUIRED to answer in finite time, but D(D) isn;t, but
will if H(D,D) answers), and you will find that H(D,D) won't match D(D)
so H is wrong (or your H fails to answer and thus is wrong).

Note, H is REQUIRED to answer in finite time, both accepting and rejecting.

D is required to answer only ACCEPT in finite time, as it is just a
recognizer, not a decider. It CAN reject in finite time, or just not accept.

Basically, H needs to convert non-halting resutls to reject.

The problem is that if H decides that D(D) is non-halting, and thus
would reject, the fact that H does this in finite time, means that D
WILL accept in finite time, and thus makes H wrong.

Again H(D,D) MUST be compared to D(D) as that is the DEFINITION of what
that call means (or your definition of D is incorrect).

On 7/9/2022 1:08 PM, olcott wrote:
> https://www.liarparadox.org/Sipser_165_167.pdf
>
> 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("D(D) = ", D(D));
> }
>
>

If the above encoding of Sipser is correct then all that D does is
incorrectly report what H(D,D) correctly reports.

This causes the diagonal argument of the halting theorem to be trivially
incorrect.

_D()
[00001343](01) 55 push ebp
[00001344](02) 8bec mov ebp,esp
[00001346](03) 8b4508 mov eax,[ebp+08]
[00001349](01) 50 push eax
[0000134a](03) 8b4d08 mov ecx,[ebp+08]
[0000134d](01) 51 push ecx
[0000134e](05) e890fdffff call 000010e3
[00001353](03) 83c408 add esp,+08
[00001356](02) 85c0 test eax,eax
[00001358](02) 7509 jnz 00001363
[0000135a](05) b801000000 mov eax,00000001
[0000135f](02) eb04 jmp 00001365
[00001361](02) eb02 jmp 00001365
[00001363](02) 33c0 xor eax,eax
[00001365](01) 5d pop ebp
[00001366](01) c3 ret
Size in bytes:(0036) [00001366]

_main()
[00001373](01) 55 push ebp
[00001374](02) 8bec mov ebp,esp
[00001376](05) 6843130000 push 00001343
[0000137b](05) e8c3ffffff call 00001343
[00001380](03) 83c404 add esp,+04
[00001383](01) 50 push eax
[00001384](05) 681b050000 push 0000051b
[00001389](05) e8d5f1ffff call 00000563
[0000138e](03) 83c408 add esp,+08
[00001391](02) 33c0 xor eax,eax
[00001393](01) 5d pop ebp
[00001394](01) c3 ret
Size in bytes:(0034) [00001394]

machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
[00001373][00102264][00000000] 55 push ebp
[00001374][00102264][00000000] 8bec mov ebp,esp
[00001376][00102260][00001343] 6843130000 push 00001343
[0000137b][0010225c][00001380] e8c3ffffff call 00001343
[00001343][00102258][00102264] 55 push ebp
[00001344][00102258][00102264] 8bec mov ebp,esp
[00001346][00102258][00102264] 8b4508 mov eax,[ebp+08]
[00001349][00102254][00001343] 50 push eax
[0000134a][00102254][00001343] 8b4d08 mov ecx,[ebp+08]
[0000134d][00102250][00001343] 51 push ecx
[0000134e][0010224c][00001353] e890fdffff call 000010e3

H: Begin Simulation Execution Trace Stored at:112310
Address_of_H:10e3
[00001343][001122fc][00112300] 55 push ebp
[00001344][001122fc][00112300] 8bec mov ebp,esp
[00001346][001122fc][00112300] 8b4508 mov eax,[ebp+08]
[00001349][001122f8][00001343] 50 push eax
[0000134a][001122f8][00001343] 8b4d08 mov ecx,[ebp+08]
[0000134d][001122f4][00001343] 51 push ecx
[0000134e][001122f0][00001353] e890fdffff call 000010e3
H: Infinitely Recursive Simulation Detected Simulation Stopped

[00001353][00102258][00102264] 83c408 add esp,+08
[00001356][00102258][00102264] 85c0 test eax,eax
[00001358][00102258][00102264] 7509 jnz 00001363
[0000135a][00102258][00102264] b801000000 mov eax,00000001
[0000135f][00102258][00102264] eb04 jmp 00001365
[00001365][0010225c][00001380] 5d pop ebp
[00001366][00102260][00001343] c3 ret
[00001380][00102264][00000000] 83c404 add esp,+04
[00001383][00102260][00000001] 50 push eax
[00001384][0010225c][0000051b] 681b050000 push 0000051b
[00001389][0010225c][0000051b] e8d5f1ffff call 00000563
D(D) = 1
[0000138e][00102264][00000000] 83c408 add esp,+08
[00001391][00102264][00000000] 33c0 xor eax,eax
[00001393][00102268][00000018] 5d pop ebp
[00001394][0010226c][00000000] c3 ret
Number of Instructions Executed(893) == 13 Pages

--
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 13:26, olcott wrote:
> On 7/9/2022 1:08 PM, olcott wrote:
>> https://www.liarparadox.org/Sipser_165_167.pdf
>>
>> 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("D(D) = ", D(D));
>> }
>>

Why is your main() calling D(D) rather than H(D, D)? No one cares what
D(D) reports. At issue is whether H() can correctly report on the
halting status of D(D).

>
> If the above encoding of Sipser is correct then all that D does is
> incorrectly report what H(D,D) correctly reports.
>
> This causes the diagonal argument of the halting theorem to be trivially
> incorrect.

Only because you do not understand it.

André

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

On 7/9/2022 2:45 PM, André G. Isaak wrote:
> On 2022-07-09 13:26, olcott wrote:
>> On 7/9/2022 1:08 PM, olcott wrote:
>>> https://www.liarparadox.org/Sipser_165_167.pdf
>>>
>>> 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("D(D) = ", D(D));
>>> }
>>>
>
> Why is your main() calling D(D) rather than H(D, D)? No one cares what
> D(D) reports. At issue is whether H() can correctly report on the
> halting status of D(D).

Page 165 of Sipser indicates that D(D) derives the contradiction.
Page 165 of Sisper also indicates that D calls its subroutine H.
The best that I can tell my code exactly matches its spec on page 165.
D merely contradicts the correct answer provided by H.

>
>>
>> If the above encoding of Sipser is correct then all that D does is
>> incorrectly report what H(D,D) correctly reports.
>>
>> This causes the diagonal argument of the halting theorem to be
>> trivially incorrect.
>
> Only because you do not understand it.
>
> 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 2:45 PM, André G. Isaak wrote:
> On 2022-07-09 13:26, olcott wrote:
>> On 7/9/2022 1:08 PM, olcott wrote:
>>> https://www.liarparadox.org/Sipser_165_167.pdf
>>>
>>> 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("D(D) = ", D(D));
>>> }
>>>
>
> Why is your main() calling D(D) rather than H(D, D)? No one cares what
> D(D) reports. At issue is whether H() can correctly report on the
> halting status of D(D).
>

Here it is your way:

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

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

_D()
[0000134a](01) 55 push ebp
[0000134b](02) 8bec mov ebp,esp
[0000134d](03) 8b4508 mov eax,[ebp+08]
[00001350](01) 50 push eax
[00001351](03) 8b4d08 mov ecx,[ebp+08]
[00001354](01) 51 push ecx
[00001355](05) e890fdffff call 000010ea
[0000135a](03) 83c408 add esp,+08
[0000135d](02) 85c0 test eax,eax
[0000135f](02) 7509 jnz 0000136a
[00001361](05) b801000000 mov eax,00000001
[00001366](02) eb04 jmp 0000136c
[00001368](02) eb02 jmp 0000136c
[0000136a](02) 33c0 xor eax,eax
[0000136c](01) 5d pop ebp
[0000136d](01) c3 ret
Size in bytes:(0036) [0000136d]

_main()
[0000137a](01) 55 push ebp
[0000137b](02) 8bec mov ebp,esp
[0000137d](05) 684a130000 push 0000134a
[00001382](05) 684a130000 push 0000134a
[00001387](05) e85efdffff call 000010ea
[0000138c](03) 83c408 add esp,+08
[0000138f](01) 50 push eax
[00001390](05) 681b050000 push 0000051b
[00001395](05) e8d0f1ffff call 0000056a
[0000139a](03) 83c408 add esp,+08
[0000139d](02) 33c0 xor eax,eax
[0000139f](01) 5d pop ebp
[000013a0](01) c3 ret
Size in bytes:(0039) [000013a0]

machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
[0000137a][0010227a][00000000] 55 push ebp
[0000137b][0010227a][00000000] 8bec mov ebp,esp
[0000137d][00102276][0000134a] 684a130000 push 0000134a
[00001382][00102272][0000134a] 684a130000 push 0000134a
[00001387][0010226e][0000138c] e85efdffff call 000010ea

H: Begin Simulation Execution Trace Stored at:112326
Address_of_H:10ea
[0000134a][00112312][00112316] 55 push ebp
[0000134b][00112312][00112316] 8bec mov ebp,esp
[0000134d][00112312][00112316] 8b4508 mov eax,[ebp+08]
[00001350][0011230e][0000134a] 50 push eax
[00001351][0011230e][0000134a] 8b4d08 mov ecx,[ebp+08]
[00001354][0011230a][0000134a] 51 push ecx
[00001355][00112306][0000135a] e890fdffff call 000010ea
H: Infinitely Recursive Simulation Detected Simulation Stopped

[0000138c][0010227a][00000000] 83c408 add esp,+08
[0000138f][00102276][00000000] 50 push eax
[00001390][00102272][0000051b] 681b050000 push 0000051b
[00001395][00102272][0000051b] e8d0f1ffff call 0000056a
Input_Halts = 0
[0000139a][0010227a][00000000] 83c408 add esp,+08
[0000139d][0010227a][00000000] 33c0 xor eax,eax
[0000139f][0010227e][00000018] 5d pop ebp
[000013a0][00102282][00000000] c3 ret
Number of Instructions Executed(880) == 13 Pages

--
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 13:51, olcott wrote:
> On 7/9/2022 2:45 PM, André G. Isaak wrote:
>> On 2022-07-09 13:26, olcott wrote:
>>> On 7/9/2022 1:08 PM, olcott wrote:
>>>> https://www.liarparadox.org/Sipser_165_167.pdf
>>>>
>>>> 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("D(D) = ", D(D));
>>>> }
>>>>
>>
>> Why is your main() calling D(D) rather than H(D, D)? No one cares what
>> D(D) reports. At issue is whether H() can correctly report on the
>> halting status of D(D).
>
> Page 165 of Sipser indicates that D(D) derives the contradiction.
> Page 165 of Sisper also indicates that D calls its subroutine H.
> The best that I can tell my code exactly matches its spec on page 165.
> D merely contradicts the correct answer provided by H.

You're completely misreading sipser. The sipser proof is *identical* to
the Linz proof. He does not say that D *returns* the opposite value that
H does but rather that it *does* the opposite of what H claims it will
do. i.e. it halts if H claims it doesn't and it doesn't halt if H claims
it does. D(D) derives a contradiction when passed as an input to H().

All you've done above is flipped the return values.

André

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

On 7/9/22 3:51 PM, olcott wrote:
> On 7/9/2022 2:45 PM, André G. Isaak wrote:
>> On 2022-07-09 13:26, olcott wrote:
>>> On 7/9/2022 1:08 PM, olcott wrote:
>>>> https://www.liarparadox.org/Sipser_165_167.pdf
>>>>
>>>> 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("D(D) = ", D(D));
>>>> }
>>>>
>>
>> Why is your main() calling D(D) rather than H(D, D)? No one cares what
>> D(D) reports. At issue is whether H() can correctly report on the
>> halting status of D(D).
>
> Page 165 of Sipser indicates that D(D) derives the contradiction.
> Page 165 of Sisper also indicates that D calls its subroutine H.
> The best that I can tell my code exactly matches its spec on page 165.
> D merely contradicts the correct answer provided by H.
>

No, D DEFINES the correct answer for H, the job of H is to predict if D
will accept its input or not.

H is REQUIRED (to be correct) to give the answer that D will give if D
will give an answer, and 0 if D will NEVER give an answer (as
recognizers are allowed to be non-halting for inputs they do not accept).

Since D will always give an answer if H gives an answer, D can NEVER be
non-halting for an H that meets its requirements.

H calling D non-halting is just pointing out that H doesn't meet the
requirements of H.

>>
>>>
>>> If the above encoding of Sipser is correct then all that D does is
>>> incorrectly report what H(D,D) correctly reports.
>>>
>>> This causes the diagonal argument of the halting theorem to be
>>> trivially incorrect.
>>
>> Only because you do not understand it.
>>
>> André
>>
>>
>
>

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.

André

> and 0 if D will NEVER give an answer (as
> recognizers are allowed to be non-halting for inputs they do not accept).

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

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.

If T just accepts if D answers then there is a correct answer of accept,
as D was defined to always either immediately accept of reject.

Unless you want to define "reject" as not answering, in which case H can
just reject by not halting, in other words H just needs to call D.

The only other option is to make "reject" a context-sensitive word where
Deciders reject by going to a reject state but Recognizers can only
reject by not answering, thus making Deciders not a special case of
Recognizers that always answer, but a completely different class of
machines.

>
> André
>
>> and 0 if D will NEVER give an answer (as recognizers are allowed to be
>> non-halting for inputs they do not accept).
>

On 7/9/2022 3:03 PM, André G. Isaak wrote:
> On 2022-07-09 13:51, olcott wrote:
>> On 7/9/2022 2:45 PM, André G. Isaak wrote:
>>> On 2022-07-09 13:26, olcott wrote:
>>>> On 7/9/2022 1:08 PM, olcott wrote:
>>>>> https://www.liarparadox.org/Sipser_165_167.pdf
>>>>>
>>>>> 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("D(D) = ", D(D));
>>>>> }
>>>>>
>>>
>>> Why is your main() calling D(D) rather than H(D, D)? No one cares
>>> what D(D) reports. At issue is whether H() can correctly report on
>>> the halting status of D(D).
>>
>> Page 165 of Sipser indicates that D(D) derives the contradiction.
>> Page 165 of Sisper also indicates that D calls its subroutine H.
>> The best that I can tell my code exactly matches its spec on page 165.
>> D merely contradicts the correct answer provided by H.
>
> You're completely misreading sipser. The sipser proof is *identical* to
> the Linz proof. He does not say that D *returns* the opposite value that
> H does but rather that it *does* the opposite of what H claims it will
> do. i.e. it halts if H claims it doesn't and it doesn't halt if H claims
> it does. D(D) derives a contradiction when passed as an input to H().
>
> All you've done above is flipped the return values.
>
> André
>
>

Now we construct a new Turing machine D with H as a subroutine. This new
TM calls H to determine what M does when the input to M is its own
description ⟨M⟩. Once D has determined this information, it does the
opposite. That is, it rejects if M accepts and accepts if M does not
accept. The following is a description of D.

D = "On input ⟨M⟩, where M is a TM:
1. Run H on input ⟨M, ⟨M⟩⟩.
2. Output the opposite of what H outputs; that is if H accepts
reject and if H rejects, accept."

Because you missed this in the original text I will repeat it:
Output the opposite of what H outputs;
Output the opposite of what H outputs;
Output the opposite of what H outputs;

--
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 3: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.
>

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("D(D) = ", D(D));
}

Ah that proves my H is correct. D is stuck in infinitely recursive
emulation unable to provide any answer.

> André
>
>> and 0 if D will NEVER give an answer (as recognizers are allowed to be
>> non-halting for inputs they do not accept).
>

--
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 3: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.
>
> André
>
>> and 0 if D will NEVER give an answer (as recognizers are allowed to be
>> non-halting for inputs they do not accept).
>

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));
}

Ah that proves my H is correct. D is stuck in infinitely recursive
emulation unable to provide any answer.

--
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 14:44, olcott wrote:
> On 7/9/2022 3:03 PM, André G. Isaak wrote:
>> On 2022-07-09 13:51, olcott wrote:
>>> On 7/9/2022 2:45 PM, André G. Isaak wrote:
>>>> On 2022-07-09 13:26, olcott wrote:
>>>>> On 7/9/2022 1:08 PM, olcott wrote:
>>>>>> https://www.liarparadox.org/Sipser_165_167.pdf
>>>>>>
>>>>>> 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("D(D) = ", D(D));
>>>>>> }
>>>>>>
>>>>
>>>> Why is your main() calling D(D) rather than H(D, D)? No one cares
>>>> what D(D) reports. At issue is whether H() can correctly report on
>>>> the halting status of D(D).
>>>
>>> Page 165 of Sipser indicates that D(D) derives the contradiction.
>>> Page 165 of Sisper also indicates that D calls its subroutine H.
>>> The best that I can tell my code exactly matches its spec on page 165.
>>> D merely contradicts the correct answer provided by H.
>>
>> You're completely misreading sipser. The sipser proof is *identical*
>> to the Linz proof. He does not say that D *returns* the opposite value
>> that H does but rather that it *does* the opposite of what H claims it
>> will do. i.e. it halts if H claims it doesn't and it doesn't halt if H
>> claims it does. D(D) derives a contradiction when passed as an input
>> to H().
>>
>> All you've done above is flipped the return values.
>>
>> André
>>
>>
>
>
> Now we construct a new Turing machine D with H as a subroutine. This new
> TM calls H to determine what M does when the input to M is its own
> description ⟨M⟩. Once D has determined this information, it does the
> opposite. That is, it rejects if M accepts and accepts if M does not
> accept. The following is a description of D.
>
> D = "On input ⟨M⟩, where M is a TM:
>     1. Run H on input ⟨M, ⟨M⟩⟩.
>     2. Output the opposite of what H outputs; that is if H accepts
> reject and if H rejects, accept."
>
>
> Because you missed this in the original text I will repeat it:
> Output the opposite of what H outputs;
> Output the opposite of what H outputs;
> Output the opposite of what H outputs;

OK. You're dealing with a different proof than the one I thought. My bad
for not reading the .pdf which you linked to.

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é

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

On 7/9/2022 4:03 PM, André G. Isaak wrote:
> On 2022-07-09 14:44, olcott wrote:
>> On 7/9/2022 3:03 PM, André G. Isaak wrote:
>>> On 2022-07-09 13:51, olcott wrote:
>>>> On 7/9/2022 2:45 PM, André G. Isaak wrote:
>>>>> On 2022-07-09 13:26, olcott wrote:
>>>>>> On 7/9/2022 1:08 PM, olcott wrote:
>>>>>>> https://www.liarparadox.org/Sipser_165_167.pdf
>>>>>>>
>>>>>>> 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("D(D) = ", D(D));
>>>>>>> }
>>>>>>>
>>>>>
>>>>> Why is your main() calling D(D) rather than H(D, D)? No one cares
>>>>> what D(D) reports. At issue is whether H() can correctly report on
>>>>> the halting status of D(D).
>>>>
>>>> Page 165 of Sipser indicates that D(D) derives the contradiction.
>>>> Page 165 of Sisper also indicates that D calls its subroutine H.
>>>> The best that I can tell my code exactly matches its spec on page 165.
>>>> D merely contradicts the correct answer provided by H.
>>>
>>> You're completely misreading sipser. The sipser proof is *identical*
>>> to the Linz proof. He does not say that D *returns* the opposite
>>> value that H does but rather that it *does* the opposite of what H
>>> claims it will do. i.e. it halts if H claims it doesn't and it
>>> doesn't halt if H claims it does. D(D) derives a contradiction when
>>> passed as an input to H().
>>>
>>> All you've done above is flipped the return values.
>>>
>>> André
>>>
>>>
>>
>>
>> Now we construct a new Turing machine D with H as a subroutine. This
>> new TM calls H to determine what M does when the input to M is its own
>> description ⟨M⟩. Once D has determined this information, it does the
>> opposite. That is, it rejects if M accepts and accepts if M does not
>> accept. The following is a description of D.
>>
>> D = "On input ⟨M⟩, where M is a TM:
>>      1. Run H on input ⟨M, ⟨M⟩⟩.
>>      2. Output the opposite of what H outputs; that is if H accepts
>> reject and if H rejects, accept."
>>
>>
>> Because you missed this in the original text I will repeat it:
>> Output the opposite of what H outputs;
>> Output the opposite of what H outputs;
>> Output the opposite of what H outputs;
>
> OK. You're dealing with a different proof than the one I thought. My bad
> for not reading the .pdf which you linked to.
>
> 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?

I still need an answer to this question.

--
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 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.

It was perfectly reasonably of me to assume you meant 'Sipser's proof of
the halting theorem' given your obsession with halt deciders and the
fact that you referred to it as the "diagonal argument of the halting
theorem". (Sipser doesn't refers to it as such since that is an
inaccurate description).

André

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

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

> you meant 'Sipser's proof of
> the halting theorem' given your obsession with halt deciders and the
> fact that you referred to it as the "diagonal argument of the halting
> theorem". (Sipser doesn't refers to it as such since that is an
> inaccurate description).
>
> 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 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.
>
> It was perfectly reasonably of me to assume you meant 'Sipser's proof of
> the halting theorem' given your obsession with halt deciders and the
> fact that you referred to it as the "diagonal argument of the halting
> theorem". (Sipser doesn't refers to it as such since that is an
> inaccurate description).
>
> André
>

So far no one has come in the ballpark of any correct rebuttal to this:

typedef void (*ptr)();
// rec routine P
// §L :if T[P] go to L
// Return §
// https://academic.oup.com/comjnl/article/7/4/313/354243
void Strachey_P()
{ L: if (T(Strachey_P)) goto L;
return;
}

int main()
{ Output("Input_Halts = ", T(Strachey_P));
}

The execution trace of simulating halt decider T(Strachey_P) proves that
T correctly predicts that its correct and complete x86 emulation of its
input would never reach the "ret" instruction (final state) of this
input. Thus T correctly rejects its input as non-halting.

Hypothesizing that the above is correct would seem to logically entail
that there must be some error in the diagonalization proof.

--
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 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é

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

On 7/9/22 4:51 PM, olcott wrote:
> On 7/9/2022 3: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.
>>
>
> 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("D(D) = ", D(D));
> }
>
> Ah that proves my H is correct. D is stuck in infinitely recursive
> emulation unable to provide any answer.

D isn't required to give an answer, but H is. (If D will never answer, H
needs to return 0, as D never accepted the input).

Note, if H determines that D(D) won't answer and returns 0, then by
simple observation D(&D) will return 1, so either H was wrong about its
decision that D(D) never answers, or H isn't actually a pure function
and has differing behavior for the exact same input.

Note, for this to be a correct encoding of D, H(&D, &D) must refer to
the computation D(&D), and not something else.

>
>> André
>>
>>> and 0 if D will NEVER give an answer (as recognizers are allowed to
>>> be non-halting for inputs they do not accept).
>>
>
>

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?

--
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 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é
>
>

Are you claiming that this is a false statement:
L15: Proof by Diagonalization that ATM (Halting Problem) is Not Decidable

--
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 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.

Mike.

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é

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

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é

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