-4

https://softwareengineering.stackexchange.com/questions/439054/does-this-design-of-a-simulating-halt-decider-meet-the-requirement-that-hp-p-c

Software engineers competent in C and the x86 language will verify that when H(P,P) correctly emulates its input with an x86 emulator that this emulation would never stop running. This provides the basis for H(P,P) to correctly reject its input as non-halting.

For any program H that might determine if programs halt, a "pathological" program P, called with some input, can pass its own source and its input to H and then specifically do the opposite of what H predicts P will do. No H can exist that handles this case. https://en.wikipedia.org/wiki/Halting_problem

H determines the halt status of its input by watching the behavior of this input when it is correctly simulated by H using an x86 emulator. When H correctly matches an infinite behavior pattern it aborts the emulation of this input and returns 0.

#include <stdint.h> 
#define u32 uint32_t 

void P(u32 x) 
{
  if (H(x, x)) 
    HERE: goto HERE; 
  return; 
} 

int main() 
{ 
  Output("Input_Halts = ", H((u32)P, (u32)P)); 
}

_P()
[00001352](01)  55              push ebp
[00001353](02)  8bec            mov ebp,esp
[00001355](03)  8b4508          mov eax,[ebp+08]
[00001358](01)  50              push eax      // push P
[00001359](03)  8b4d08          mov ecx,[ebp+08]
[0000135c](01)  51              push ecx      // push P
[0000135d](05)  e840feffff      call 000011a2 // call H
[00001362](03)  83c408          add esp,+08
[00001365](02)  85c0            test eax,eax
[00001367](02)  7402            jz 0000136b
[00001369](02)  ebfe            jmp 00001369
[0000136b](01)  5d              pop ebp
[0000136c](01)  c3              ret
Size in bytes:(0027) [0000136c]

It is completely obvious that when H(P,P) correctly emulates its input that it must emulate the first seven instructions of P. Because the seventh instruction repeats this process we can know with complete certainty that the emulated P never reaches its final “ret” instruction, thus never halts.

You say that H(P,P) = 0. But then P(P) will never enter the infinite loop and will in fact halt, so that H(P,P) should return 1 @amon

(1) Deciders(computer science) compute the mapping from their inputs to an accept or reject state.

(2) The actual behavior of the actual input to H(P,P) is proven to never halt.

(3) P(P) is not an input to H, thus out-of-scope for H.

The actual behavior of the correctly simulated input to H(P,P) is not the same as the actual behavior of P(P) because the specified sequence of instructions is not the same.

Because halt deciders must report on the actual behavior of their actual inputs H(P,P)==0 is correct even though P(P) halts.

int sum(int x, int y)
{
  return x + y;
}

Expecting H(P,P) to report on the behavior of an entirely different sequence of instructions than its input actually specifies is exactly the same as expecting sum(3,4) to return the sum of 5 + 7, quite nuts.

2
  • 1
    I am pretty sure you won't convince enough community members here to accept this question, but maybe the community at Computer Science SE has more experts for this kind of questions.
    – Doc Brown
    Jun 6 at 15:59
  • @DocBrown If you look at the most recent rewrite of this question that I posted as a new answer below you will find that I have translated the whole thing into ordinary software engineering that has a very obvious answer.
    – polcott
    Jun 6 at 16:04

1 Answer 1

4

The post is inherently off-topic. It is not likely that it can be improved to fit the scope of this site.

As outlined in my comment to the now-deleted post, there are two issues at hand:

  • the post is not a question
  • the subject matter of the post is theoretical computer science, not software engineering

Questions must be answerable questions

Stack Exchange sites including this Software Engineering site are for Q&A. Whether something is a question doesn't depend on whether your title contains a question mark. Instead, the best questions have the following characteristics:

  • The question is about a real-world (non-hypothetical) problem you are facing, and that others are also likely to face.
  • Typical software engineers are able to write an answer that provides a potential solution to the problem. The answerer can draw from general knowledge or experience.
  • The problem statement allows answers to be objectively scored (whether the answer likely solves the problem). After all, answers are just as much for other people that might have a similar problem as for the original asker.

Your post does not seem to be an answerable question in this sense. It seems you are looking for a review of your “proof”, and are not trying to solve a software engineering problem you are facing. Even if it were a software engineering problem, it would be unusual for software engineers to have sufficiently in-depth background knowledge of the halting problem to write a good answer and to vote on other answers.

More practically, I'm also concerned that you would not accept any answer as valid. The true purpose of your posts likely is that you are looking for validation of your crank theories. That is not an answerable question. Whether an answer would address your problem (lack of validation) would depend on your subjective opinion, and cannot be determined objectively. In the past, you have also been very argumentative when constructive criticism was provided. This site is for a straightforward question → answer structure, not for extended discussion. If extensive discussion ensues, this is often an indication that the problem statement in the question was not sufficiently precise.

Even if there was a question about your execution traces, it would be unanswerable because the software in question (your x86utm system) is not generally available. In contrast, if someone asks about, say, a design question involving C# generics, then that question is answerable through experience, reading the documentation, and experimentation with the open source reference implementation.

Questions must be about software engineering

Your post is about a purported proof regarding the halting problem. The halting problem has relevance for software engineering issues such as compiler construction and security mitigations, but the problem itself is clearly from theoretical computer science. *Posts about halting problem proofs are out of scope on this software engineering site.

In a comment to the now-deleted question, you told me that

this question is about: Requirements, architecture, and design (thus software engineering) of a fully operational software system that is implemented in C, thus characterizing is as crank science is woefully inaccurate disparagement.

I disagree. A question is not on-topic merely because it involves software engineering. To be on-topic, the question must be about software engineering.

In the past, this site had issues with questions that involved programmers in the widest sense, but weren't actually about software engineering. A famous example (though from Stack Overflow) was the boat programming question which was entirely about naval matters. There is now clear consensus that such questions are not acceptable. Similarly, questions about people management or Arduino hardware are off topic, even if they are raised in the context of software development. Code-level questions are also considered to be out of scope. Analogously, computer science issues that go beyond typical software engineering are off-topic here.

12
  • Because my question can be (very easily) correctly answered on the basis of software engineering design / requirements it is a software engineering question and not a theoretical computer science question. Because it is based on a fully operational software system it was extremely rude for you to call this crank science. That would seem to prove that your review is woefully biased and thus incorrect.
    – polcott
    Jun 5 at 10:47
  • 2
    @polcott Your posts are not off-topic because they involve crank science. But the same thought patterns that lead you down the crank science path probably also make it difficult for you to ask good, on-topic questions. For example, your comment here re-interprets concepts like “software engineering” to suit you. Instead of trying to understand other people and using shared concepts to facilitate communication, you are defending your non-standard interpretation.
    – amon
    Jun 5 at 11:33
  • 1
    (And personally, as a scientist, I find it super rude to make scientific claims without using standard terminology, without comprehensible and convincing explanation, without engaging with prior work, and without using reproducible methods. A lot of crank science – yours probably included – is “not even wrong” and wastes experts' time.)
    – amon
    Jun 5 at 11:33
  • The key thing that you make sure to ignore is that I am very obviously correct. That is what is most intolerably rude. It is very very easy to see that H(P,P)==0 is correct. You are apparently merely a very rude person. I want another different reviewer.
    – polcott
    Jun 5 at 15:53
  • It is correct that H(P,P)==0. It is true that the relationship between H and P is the same relationship specified by the halting problem proofs. That you simply ignored these easily verifiable key facts proves that you did not even bother to look at what I said before passing judgment. Since my post was written for software engineers it employed software engineering terminology.
    – polcott
    Jun 5 at 20:26
  • That you are being dishonest in your assessment is proven on the basis that all of the above is mere rhetoric and points to no software engineering error because there is none. It is a verified fact that H(P,P)==0 is correct.
    – polcott
    Jun 5 at 23:44
  • 1
    @polcott Whether your proof is correct is irrelevant for determining whether your post is an on-topic question. You continue to insist that you are correct, but that doesn't make it an answerable question. And regardless of which terminology you use, your issue is essentially a theoretical computer science problem that is out of scope for the Software Engineering site.
    – amon
    Jun 6 at 9:17
  • Anyone that knows software engineering in C and the x86 language can easily verify that when H(P,P) emulates its input with an x86 emulator that this emulated input would never reach its "ret" instruction (thus never halt). Are you saying that you lack these technical skills? That would mean that you are unqualified to review my question.
    – polcott
    Jun 6 at 14:23
  • 1
    @polcott (1) I do not have to understand the specifics of your question in order to know whether it is on-topic for this site. (2) I happen to be reasonably knowledgeable with C and x86 assembly. And you are of course correct that your specific program recurses (assuming that H(a, b) unconditionally emulates/runs a(b)). But that observation doesn't allow any inferences about the halting problem, as you have not shown that the halting problem reduces to your specific emulation problem.
    – amon
    Jun 6 at 15:37
  • Ah great we are finally making some progress. Peter Linz defines halting as reaching a final state. It is clear that a complete and correct x86 emulation of the input to H(P,P) would never reach its "ret" instruction, thus never halt. It is shown below (in my new answer) that H and P do match the halting problem counter-example pattern.
    – polcott
    Jun 6 at 15:44
  • H(P,P) determines that halt status of its input based on the actual behavior of the actual input. Deciders in computer science compute the mapping from their inputs to an accept or reject state. Because P(P) is not an input to H it is incorrect to expect H to compute the halt status of P(P).
    – polcott
    Jun 7 at 2:45
  • "But that observation doesn't allow any inferences about the halting problem, as you have not shown that the halting problem reduces to your specific emulation problem." That is false and you know it. I have shown that H and P match the required halting problem counter-example pattern. Why do you say that I did not do this when you know that I have done this?
    – polcott
    Jun 7 at 14:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .