Can you please verify that the analysis of these C functions is correct?

[polcott]

To understand this analysis requires a sufficient knowledge of
the C programming language and what an x86 emulator does.

typedef void (*ptr)();
int H0(ptr P);

void Infinite_Loop()
{
  HERE: goto HERE;
}

void Infinite_Recursion()
{
  Infinite_Recursion();
}

void DDD()
{
  H0(DDD);
}

int main()
{
  H0(Infinite_Loop);
  H0(Infinite_Recursion);
  H0(DDD);
}

Every C programmer that knows what an x86 emulator is knows that when H0
emulates the machine language of Infinite_Loop, Infinite_Recursion, and
DDD that it must abort these emulations so that itself can terminate normally.

When this is construed as non-halting criteria then simulating termination
analyzer H0 is correct to reject these inputs as non-halting.

 

[BlackCube]

This again.

Self reference causes problems, nothing new there.

Determining whether a program halts or not by emulation? I'm not swallowing that one.

Just my opinion, everything I type is wrong.

 

[polcott]

This again.

Self reference causes problems, nothing new there.

Determining whether a program halts or not by emulation? I'm not swallowing that one.

Just my opinion, everything I type is wrong.

It has been fully operational software since 2021.

GitHub - plolcott/x86utm: Universal Turing Machine (UTM) having the x86 language as its Machine description language.

Universal Turing Machine (UTM) having the x86 language as its Machine description language. - GitHub - plolcott/x86utm: Universal Turing Machine (UTM) having the x86 language as its Machine descri...

github.com

 

[BlackCube]

The problem I have, is the analyzer concludes the program does not halt because the simulation will never finish.

By not making any decision, it avoids the next line in that classic program. The one that produces the paradox. The interesting part.

 

[polcott]

The problem I have, is the analyzer concludes the program does not halt because the simulation will never finish.

By not making any decision, it avoids the next line in that classic program. The one that produces the paradox. The interesting part.

I initially provide only some of the key details because I have found that providing more than the bare essence overwhelms people.

I asked a more complicated version of this question in this forum previously and got a good yet incomplete response. I am asking in a C forum because the key elements of all of my key points can be fully expressed in C. Also with C there are no subjective judgements calls involved. The code does what it actually does.

When H0 sees the repeating state of its inputs it aborts its simulation and returns 0 indicating that these inputs do not halt. This makes the next line in the classic program unreachable thus bypassing the otherwise paradox.

This has all been fully operational code for three years. A leading expert in the field of the theory of computation has approved my basic algorithm that is sketched above:

Introduction to the Theory of Computation, by Michael Sipser
Amazon.com

<MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022>
If simulating halt decider H correctly simulates its input D
until H correctly determines that its simulated D would never
stop running unless aborted then

H can abort its simulation of D and correctly report that D
specifies a non-halting sequence of configurations.
</MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022>

 

[polcott]

The problem I have, is the analyzer concludes the program does not halt because the simulation will never finish.

By not making any decision, it avoids the next line in that classic program. The one that produces the paradox. The interesting part.

I wrote this whole paper all over again from scratch to make it most easily understood by C/C++ software engineers like myself. It also has some key technical details for computer scientists.

Updated 2024-07-11 so that the key point (on the first page) only requires knowledge of C.

Termination Analyzer H is Not Fooled by Pathological Input D

https://www.researchgate.net/public...lyzer_H_is_Not_Fooled_by_Pathological_Input_D

 

[polcott]

The problem I have, is the analyzer concludes the program does not halt because the simulation will never finish.

By not making any decision, it avoids the next line in that classic program. The one that produces the paradox. The interesting part.

When a simulating termination analyzer reports on the behavior specified by its input finite string of C code (or its underlying x86 machine code the way that HHH actually does it) it computes the mapping from this finite string to the non-halting behavior of that this finite string specifies because the paradoxical part is made unreachable code.

typedef void (*ptr)();
int HHH(ptr P);

int DD()
{
  int Halt_Status = HHH(DD);
  if (Halt_Status)
    HERE: goto HERE;
  return Halt_Status;
}

int main()
{
  HHH(DD);
}

DD correctly simulated by HHH cannot possibly reach its own
"return" instruction halt state.

 

[BlackCube]

DD cannot reach its own return instruction because HHH is using simulation.

HHH is non halting, the jury is still out about DD.

 

[polcott]

DD cannot reach its own return instruction because HHH is using simulation.

HHH is non halting, the jury is still out about DD.

This has been fully operational code for three years.
x86utm/Halt7.c at master · plolcott/x86utm

He is the best selling author of theory of computation textbooks
BEGIN-MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022

If simulating halt decider H correctly simulates its input D​

until H correctly determines that its simulated D would never​

stop running unless aborted then​

​

H can abort its simulation of D and correctly report that D​

specifies a non-halting sequence of configurations.​

END-MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022

The above is the essence of my algorithm.

 

[BlackCube]

Here's my problem with detecting an infinite loop by simulation...

A program loops until it finds a counter example for Fermat's last theorem, we know it will not halt, but a simulator could not, because the loop is conditional, and the variables never repeat.

Another program calculates a sum we know exists, but does so in an extremely inefficient manner, we know it will halt, but a simulator would need billions of years to figure that out.

The basic approach has a flaw, so how it handles your special case is not important to me personally.

Just my opinion.

Does anyone else want to chip in?

 

[polcott]

Here's my problem with detecting an infinite loop by simulation...

A program loops until it finds a counter example for Fermat's last theorem, we know it will not halt, but a simulator could not, because the loop is conditional, and the variables never repeat.

int DD()
{
  int Halt_Status = HHH(DD);
  if (Halt_Status)
    HERE: goto HERE;
  return Halt_Status;
}

All of my work for the last twenty years has only dealt with
(programs / Turing Machine descriptions) that are isomorphic to the above example.

Just to show the scope of my work: (not appropriate for a C forum)
Here is the Peter Linz Turing Machine based Halting Problem proof.
https://www.liarparadox.org/Linz_Proof.pdf
It is essentially isomorphic to the above C code.

I am not solving the Halting Problem. I am refuting the conventional
proofs of the Halting Problem. By refuting all of the conventional
proofs the Halting Problem is no longer proven. This provides a key
basis for others to actually solve the Halting Problem.

The above code presents recursive simulation that is essentially the
same sort of thing as infinite recursion to any simulating termination
analyzer HHH that is based on an x86 emulator.
Termination analysis - Wikipedia

This is fully operational C code right here:

x86utm/Halt7.c at master · plolcott/x86utm

Universal Turing Machine (UTM) having the x86 language as its Machine description language. - plolcott/x86utm

github.com

It depends on the x86utm operating system written in C++
and the libx86emu x86 emulator library written in C.

 

[polcott]

A program loops until it finds a counter example for Fermat's last theorem, we know it will not halt, but a simulator could not, because the loop is conditional, and the variables never repeat.

Another program calculates a sum we know exists, but does so in an extremely inefficient manner, we know it will halt, but a simulator would need billions of years to figure that out.

Those examples are not provably impossible. They are merely very difficult. The halting problem counter-example is framed to require a yes/no answer to a self-contradictory question.

Professor Hehner sums it up like this:
Can Carol correctly answer “no” to this (yes/no) question?
https://cs.toronto.edu/~hehner/OSS.pdf
Carol cannot correctly answer that question because for Carol it is a self-contradictory question.

Professor Hehner agrees with this verbatim summation of his paper:
"the halting problem cannot be solved because there is something wrong with it."