olcott <NoOne@NoWhere.com> writes:

> On 8/19/2021 8:14 AM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 8/18/2021 8:42 PM, Ben Bacarisse wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 8/18/2021 8:16 PM, Ben Bacarisse wrote:
>>
>>>>>> Yes. I cut them because they are not the specification of the function
>>>>>> that I will challenge you to write.
>>>>>
>>>>> That is out-of-scope and you know it.
>>>>
>>>> Not in my opinion, no. A function that that shows there are undecidable
>>>> sets should worry you, but for some reason you prefer to stick with
>>>> talking about your H that does something entirely unsurprising and
>>>> uninteresting.
>>>
>>> So when I correctly refute the halting problem proofs you say no I did
>>> not refute every proof in the universe and the halting problem proof
>>> is one of these proofs therefore I did not refute the halting problem
>>> proof.
>>
>> No, I'm not saying that.
>>
>> Anyway, in case you are interested, here is the specification of the
>> function you can't write:
>> The computational model is C code with no memory restrictions. Of
>> course, if you don't actually hit the memory limits of a C
>> implementation it's just actual C code. I'd be happy to say more about
>> this model of computation if you think the details will matter to your
>> solution.
>>
>> The problem is that of deciding if a function would return if called
>> from main. A "return decider" (in this model) is a C function returning
>> _Bool that always returns a value to the expression in which it was
>> called. A return decider always returns the same value for any
>> arguments that represnet the same function call expression.
>>
>> Your mission, should you chose to accept it, is to write a return
>> decider B with this prototype
>>
>> typedef uintptr_t data;
>> typedef void (*function)(data);
>> extern _Bool B(function, data);
>>
>> such that B(f, d) returns true if and only if a call of f from main with
>> argument d returns to main. The two arguments, f and d, are said to
>> represenet the call expression f(d).
>>
>> If, rather than just thinking you can do this, you have actual C code,
>> you should provide either source or a compiled translation unit that can
>> be linked with this one:
>>
>> #include <stdint.h>
>> #include <stdio.h>
>>
>> typedef uintptr_t data;
>> typedef void (*function)(data);
>>
>> extern _Bool B(function, data);
>> void B_hat(data x) { if (B((function)x, x)) while (1); }
>> int main(void)
>> {
>> printf("%d\n", B(B_hat, (data)B_hat));
>> fflush(stdout);
>> B_hat((data)B_hat);
>> puts("returned");
>> }
>>
>> The output should be either
>>
>> 1
>> returned
>>
>> or
>>
>> 0
>>
>> with no further output. Of course you could always just agree that no
>> such function B can be written.
>
> The x86utm operating system cannot call any C functions.

Hmm... Not sure why I should care about that. Do claim to have a
C function that meets this spec? If so post it (or a linkable object
module) so we can test it.

If not, do you claim you will be able to write such a function?

> Good job on the use of C. My own use of unsigned integers as function
> pointers is unconventional and not as portable. I did this on purpose
> so that x86utm would have a single standard tape element type.
>
> #include <stdint.h>
> #include <stdio.h>
>
> typedef uintptr_t data;
> typedef void (*function)(data);
>
> extern _Bool B(function, data);
>
> void B_hat(data x) { if (H((u32)x, (u32)x)) while (1); }
>
> int main2()
> {
> OutputHex(H((u32)B_hat, (u32)B_hat));
> B_hat((u32)B_hat);
> OutputString("returned");
> }

This shows no function B. And it's not even valid C. How does it help
meet the challenge?

> _B_hat()
> [00000efc](01) 55 push ebp
> [00000efd](02) 8bec mov ebp,esp
> [00000eff](03) 8b4508 mov eax,[ebp+08]
> [00000f02](01) 50 push eax
> [00000f03](03) 8b4d08 mov ecx,[ebp+08]
> [00000f06](01) 51 push ecx
> [00000f07](05) e850feffff call 00000d5c
> [00000f0c](03) 83c408 add esp,+08
> [00000f0f](02) 85c0 test eax,eax
> [00000f11](02) 740b jz 00000f1e
> [00000f13](05) ba01000000 mov edx,00000001
> [00000f18](02) 85d2 test edx,edx
> [00000f1a](02) 7402 jz 00000f1e
> [00000f1c](02) ebf5 jmp 00000f13
> [00000f1e](01) 5d pop ebp
> [00000f1f](01) c3 ret
> Size in bytes:(0036) [00000f1f]
>
> _main2()
> [00000f2c](01) 55 push ebp
> [00000f2d](02) 8bec mov ebp,esp
> [00000f2f](05) 68fc0e0000 push 00000efc
> [00000f34](05) 68fc0e0000 push 00000efc
> [00000f39](05) e81efeffff call 00000d5c
> [00000f3e](03) 83c408 add esp,+08
> [00000f41](01) 50 push eax
> [00000f42](05) e8e5f3ffff call 0000032c
> [00000f47](03) 83c404 add esp,+04
> [00000f4a](05) 68fc0e0000 push 00000efc
> [00000f4f](05) e8a8ffffff call 00000efc
> [00000f54](03) 83c404 add esp,+04
> [00000f57](05) 6823030000 push 00000323
> [00000f5c](05) e8dbf3ffff call 0000033c
> [00000f61](03) 83c404 add esp,+04
> [00000f64](01) 5d pop ebp
> [00000f65](01) c3 ret
> Size in bytes:(0058) [00000f65]
>
> _main()
> [00000f6c](01) 55 push ebp
> [00000f6d](02) 8bec mov ebp,esp
> [00000f6f](05) e8b8ffffff call 00000f2c
> [00000f74](02) 33c0 xor eax,eax
> [00000f76](01) 5d pop ebp
> [00000f77](01) c3 ret
> Size in bytes:(0012) [00000f77]

I can compile the code I posted. What I can't do is write the function
you are not showing the code for. This partial listing does not advance
your case one bit.

> machine stack stack machine assembly
> address address data code language
> ======== ======== ======== ========= =============
> ...[00000f6c][00101c0a][00000000] 55 push ebp
> ...[00000f6d][00101c0a][00000000] 8bec mov ebp,esp
> ...[00000f6f][00101c06][00000f74] e8b8ffffff call 00000f2c
> ...[00000f2c][00101c02][00101c0a] 55 push ebp
> ...[00000f2d][00101c02][00101c0a] 8bec mov ebp,esp
> ...[00000f2f][00101bfe][00000efc] 68fc0e0000 push 00000efc
> ...[00000f34][00101bfa][00000efc] 68fc0e0000 push 00000efc
> ...[00000f39][00101bf6][00000f3e] e81efeffff call 00000d5c
>
> Begin Local Halt Decider Simulation at Machine Address:efc
> ...[00000efc][00211caa][00211cae] 55 push ebp
> ...[00000efd][00211caa][00211cae] 8bec mov ebp,esp
> ...[00000eff][00211caa][00211cae] 8b4508 mov eax,[ebp+08]
> ...[00000f02][00211ca6][00000efc] 50 push eax
> ...[00000f03][00211ca6][00000efc] 8b4d08 mov ecx,[ebp+08]
> ...[00000f06][00211ca2][00000efc] 51 push ecx
> ...[00000f07][00211c9e][00000f0c] e850feffff call 00000d5c
> ...[00000efc][0025c6d2][0025c6d6] 55 push ebp
> ...[00000efd][0025c6d2][0025c6d6] 8bec mov ebp,esp
> ...[00000eff][0025c6d2][0025c6d6] 8b4508 mov eax,[ebp+08]
> ...[00000f02][0025c6ce][00000efc] 50 push eax
> ...[00000f03][0025c6ce][00000efc] 8b4d08 mov ecx,[ebp+08]
> ...[00000f06][0025c6ca][00000efc] 51 push ecx
> ...[00000f07][0025c6c6][00000f0c] e850feffff call 00000d5c
> Local Halt Decider: Infinite Recursion Detected Simulation Stopped
> ...[00000f3e][00101c02][00101c0a] 83c408 add esp,+08
> ...[00000f41][00101bfe][00000000] 50 push eax
> ---[00000f42][00101bfe][00000000] e8e5f3ffff call 0000032c
> 0
> ...[00000f47][00101c02][00101c0a] 83c404 add esp,+04
> ...[00000f4a][00101bfe][00000efc] 68fc0e0000 push 00000efc
> ...[00000f4f][00101bfa][00000f54] e8a8ffffff call 00000efc
> ...[00000efc][00101bf6][00101c02] 55 push ebp
> ...[00000efd][00101bf6][00101c02] 8bec mov ebp,esp
> ...[00000eff][00101bf6][00101c02] 8b4508 mov eax,[ebp+08]
> ...[00000f02][00101bf2][00000efc] 50 push eax
> ...[00000f03][00101bf2][00000efc] 8b4d08 mov ecx,[ebp+08]
> ...[00000f06][00101bee][00000efc] 51 push ecx
> ...[00000f07][00101bea][00000f0c] e850feffff call 00000d5c
>
> Begin Local Halt Decider Simulation at Machine Address:efc
> ...[00000efc][0026c772][0026c776] 55 push ebp
> ...[00000efd][0026c772][0026c776] 8bec mov ebp,esp
> ...[00000eff][0026c772][0026c776] 8b4508 mov eax,[ebp+08]
> ...[00000f02][0026c76e][00000efc] 50 push eax
> ...[00000f03][0026c76e][00000efc] 8b4d08 mov ecx,[ebp+08]
> ...[00000f06][0026c76a][00000efc] 51 push ecx
> ...[00000f07][0026c766][00000f0c] e850feffff call 00000d5c
> ...[00000efc][002b719a][002b719e] 55 push ebp
> ...[00000efd][002b719a][002b719e] 8bec mov ebp,esp
> ...[00000eff][002b719a][002b719e] 8b4508 mov eax,[ebp+08]
> ...[00000f02][002b7196][00000efc] 50 push eax
> ...[00000f03][002b7196][00000efc] 8b4d08 mov ecx,[ebp+08]
> ...[00000f06][002b7192][00000efc] 51 push ecx
> ...[00000f07][002b718e][00000f0c] e850feffff call 00000d5c
> Local Halt Decider: Infinite Recursion Detected Simulation Stopped
> ...[00000f0c][00101bf6][00101c02] 83c408 add esp,+08
> ...[00000f0f][00101bf6][00101c02] 85c0 test eax,eax
> ...[00000f11][00101bf6][00101c02] 740b jz 00000f1e
> ...[00000f1e][00101bfa][00000f54] 5d pop ebp
> ...[00000f1f][00101bfe][00000efc] c3 ret
> ...[00000f54][00101c02][00101c0a] 83c404 add esp,+04
> ...[00000f57][00101bfe][00000323] 6823030000 push 00000323
> ---[00000f5c][00101bfe][00000323] e8dbf3ffff call 0000033c
> returned
> ...[00000f61][00101c02][00101c0a] 83c404 add esp,+04
> ...[00000f64][00101c06][00000f74] 5d pop ebp
> ...[00000f65][00101c0a][00000000] c3 ret
> ...[00000f74][00101c0a][00000000] 33c0 xor eax,eax
> ...[00000f76][00101c0e][00100000] 5d pop ebp
> ...[00000f77][00101c12][00000008] c3 ret
> Number_of_User_Instructions(2)
> Number of Instructions Executed(47451)

What's the point of showing a trace of a run that does not meet the
requirements?

B does not do what is required of it to meet my specification. I am
sure it meets yours but that was not the challenge. You really don't
need to waste any more time telling me why /you/ are happy with it.

By the way, you could just say that you don't /currently/ have a
function that fits the bill, and pretend that you could write one if you
chose to do so. That way you could save face.

--
Ben.