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)