XPost: comp.theory, sci.logic, sci.math

On 11/12/2021 8:50 AM, Mr Flibble wrote:

You CANNOT solve the halting problem through simulation as simulation

My excellent carefully crafted reply simply didn't show up.
As I have told you many many times I am not trying to make an
omniscient (all-knowing) program that solves the halting problem.
I am only forming a correct rebuttal to the halting theorem:

#include <stdint.h>
typedef void (*ptr)();

int H(ptr x, ptr y)
{
x(y);
return 1;
}

// Minimal essence of Linz(1990) Ĥ
// and Strachey(1965) P
void P(ptr x)
{
H(x, x);
}

int main(void)
{
H(P, P);
}

It is obvious that whether or not the above code is directly executed or
H performs a pure simulation of its input that the above code specifies infinite recursion.

If H simulates its input in debug step mode it can correctly abort the simulation of this input as soon as H sees its simulated P call itself
with the same parameters that it was called with. When it does this it correctly returns 0 for not halting.



Strachey, C 1965. An impossible program The Computer Journal, Volume 7,
Issue 4, January 1965, Page 313, https://doi.org/10.1093/comjnl/7.4.313

Linz, Peter 1990. An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company. (318-320)




Halting problem undecidability and infinitely nested simulation (V2)
November 2021 PL Olcott

https://www.researchgate.net/publication/356105750_Halting_problem_undecidability_and_infinitely_nested_simulation_V2

simply isn't practical: each branch DOUBLES the number of paths which
have to be analyzed and you soon get to a very large number of paths
with any non-trivial program that cannot be solved within the lifetime
of the universe by a classical computer.

/Flibble

--
This message is a troll.

--
Copyright 2021 Pete Olcott "Great spirits have always encountered
violent opposition from mediocre minds." Einstein

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)