On Thursday, September 23, 2021 at 7:30:30 PM UTC+1, olcott wrote:
> #include <stdint.h>
> #define ptr uintptr_t
>
> int H(ptr p, ptr i)
> {
> // Determine infinitely nested x86 emulation
> }
>
> void P(ptr x)
> {
> H(x, x);
> }
>
> int main()
> {
> printf("H is called in infinitely nested emulation = ", H(P, P));
> }
>
> H would use an x86 emulator to emulate its input in debug step mode.
>
> Since people are telling me that my solution is incorrect I am giving
> them an opportunity to either correct my errors or failing that show
> that their software engineering skills are insufficient to analyze the
> problem as presented.
I think your problem here is that you are trying to see if a program runs forever simply by emulating its running. Obviously if the emulation stops then that shows that the program terminates. But if it has been running for a bit, you still don't know whether it will run forever or if it will stop at some later point.
Although the problem of whether a computer program halts or not looks trivial, bear in mind that the technique could be used for other problems as well. For instance, imagine a program that tested whether a^n + b^n = c^n (where ^ means "to the power of") with a and b non-zero and n at least three. Such a program could pick a maximum value for a, b, c and n, test all values up to this max, then increase the max by one and repeat, only stopping when the equation is met. To determine whether such a program halted would be equivalent to solving Fermat's Last Theorem.