-4
$\begingroup$

Is the halting problem theorem really proven

The following is the verbatim original answer and nothing more. It directly executes the verbatim code of the original question and answers this original question by showing the actual behavior of this original code.

Here is the actual code of the original post actually executed in the x86utm operating system that has a halt decider based on an x86 emulator. The answer to the original question is both provided and proven below on the basis of the semantics of the x86 language.
x86 Instruction Set Reference

The technical computer science term "halt" means that a program will reach its last instruction technically called its final state.

computation that halts … the Turing machine will halt whenever it enters a final state. (Linz:1990:234)

A halt decider must compute the mapping from its inputs to an accept or reject state on the basis of the actual behavior that is actually specified by these inputs. The behavior of the input to h(c,c) that h correctly emulates with an x86 emulator and the behavior of the executed c(c) are shown below. One of these reaches its "ret" instruction final state and the other cannot.

#define TRUE 1
typedef int (*ptr)();

int c(ptr x) {
  if (h(x, x) != 0) {
    while(TRUE) {
       ;
    }
  }
  return 0;
 }
 
int main() {
   h(c, c);
   c(c);
}

_c()
[000011c0](01)  55         push ebp
[000011c1](02)  8bec       mov ebp,esp
[000011c3](03)  8b4508     mov eax,[ebp+08]
[000011c6](01)  50         push eax
[000011c7](03)  8b4d08     mov ecx,[ebp+08]
[000011ca](01)  51         push ecx
[000011cb](05)  e890fdffff call 00000f60
[000011d0](03)  83c408     add esp,+08
[000011d3](02)  85c0       test eax,eax
[000011d5](02)  740b       jz 000011e2
[000011d7](05)  ba01000000 mov edx,00000001
[000011dc](02)  85d2       test edx,edx
[000011de](02)  7402       jz 000011e2
[000011e0](02)  ebf5       jmp 000011d7
[000011e2](02)  33c0       xor eax,eax
[000011e4](01)  5d         pop ebp
[000011e5](01)  c3         ret
Size in bytes:(0038) [000011e5]

_main()
[000011f0](01)  55         push ebp
[000011f1](02)  8bec       mov ebp,esp
[000011f3](05)  68c0110000 push 000011c0
[000011f8](05)  68c0110000 push 000011c0
[000011fd](05)  e85efdffff call 00000f60
[00001202](03)  83c408     add esp,+08
[00001205](05)  68c0110000 push 000011c0
[0000120a](05)  e8b1ffffff call 000011c0
[0000120f](03)  83c404     add esp,+04
[00001212](02)  33c0       xor eax,eax
[00001214](01)  5d         pop ebp
[00001215](01)  c3         ret
Size in bytes:(0038) [00001215]

 machine   stack     stack     machine    assembly
 address   address   data      code       language
 ========  ========  ========  =========  =============
[000011f0][00101fa6][00000000] 55         push ebp
[000011f1][00101fa6][00000000] 8bec       mov ebp,esp
[000011f3][00101fa2][000011c0] 68c0110000 push 000011c0
[000011f8][00101f9e][000011c0] 68c0110000 push 000011c0
[000011fd][00101f9a][00001202] e85efdffff call 00000f60

h: Begin Simulation   Execution Trace Stored at:112052
Address_of_H:f60
[000011c0][0011203e][00112042] 55         push ebp
[000011c1][0011203e][00112042] 8bec       mov ebp,esp
[000011c3][0011203e][00112042] 8b4508     mov eax,[ebp+08]
[000011c6][0011203a][000011c0] 50         push eax
[000011c7][0011203a][000011c0] 8b4d08     mov ecx,[ebp+08]
[000011ca][00112036][000011c0] 51         push ecx
[000011cb][00112032][000011d0] e890fdffff call 00000f60
h: Infinitely Recursive Simulation Detected Simulation Stopped

[00001202][00101fa6][00000000] 83c408     add esp,+08
[00001205][00101fa2][000011c0] 68c0110000 push 000011c0
[0000120a][00101f9e][0000120f] e8b1ffffff call 000011c0
[000011c0][00101f9a][00101fa6] 55         push ebp
[000011c1][00101f9a][00101fa6] 8bec       mov ebp,esp
[000011c3][00101f9a][00101fa6] 8b4508     mov eax,[ebp+08]
[000011c6][00101f96][000011c0] 50         push eax
[000011c7][00101f96][000011c0] 8b4d08     mov ecx,[ebp+08]
[000011ca][00101f92][000011c0] 51         push ecx
[000011cb][00101f8e][000011d0] e890fdffff call 00000f60

h: Begin Simulation   Execution Trace Stored at:127eba
Address_of_H:f60
[000011c0][00127ea6][00127eaa] 55         push ebp
[000011c1][00127ea6][00127eaa] 8bec       mov ebp,esp
[000011c3][00127ea6][00127eaa] 8b4508     mov eax,[ebp+08]
[000011c6][00127ea2][000011c0] 50         push eax
[000011c7][00127ea2][000011c0] 8b4d08     mov ecx,[ebp+08]
[000011ca][00127e9e][000011c0] 51         push ecx
[000011cb][00127e9a][000011d0] e890fdffff call 00000f60
h: Infinitely Recursive Simulation Detected Simulation Stopped

[000011d0][00101f9a][00101fa6] 83c408     add esp,+08
[000011d3][00101f9a][00101fa6] 85c0       test eax,eax
[000011d5][00101f9a][00101fa6] 740b       jz 000011e2
[000011e2][00101f9a][00101fa6] 33c0       xor eax,eax
[000011e4][00101f9e][0000120f] 5d         pop ebp
[000011e5][00101fa2][000011c0] c3         ret
[0000120f][00101fa6][00000000] 83c404     add esp,+04
[00001212][00101fa6][00000000] 33c0       xor eax,eax
[00001214][00101faa][00000018] 5d         pop ebp
[00001215][00101fae][00000000] c3         ret
Number of Instructions Executed(1761) == 26 Pages

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

$\endgroup$
9
  • $\begingroup$ CS Meta is for questions or discussions about the software hosting this website or this community's policies. Technical questions are off-topic on Meta. It is not clear what you are asking or how it is in-scope for Meta. $\endgroup$
    – D.W. Mod
    Commented Jul 6, 2022 at 15:18
  • $\begingroup$ If you're asking why your answer was deleted, please remove all of the technical material and focus on asking that. Please identify what answer you are talking about. (Meta is not a place to post your technical ideas and get attention for them, so your post is likely to be poorly received if it most of its content is posting of technical material that doesn't seem relevant to Meta or that others have seen before and don't wish to see again here on Meta.) $\endgroup$
    – D.W. Mod
    Commented Jul 6, 2022 at 15:19
  • $\begingroup$ @D.W. The technical details are the original answer that was deleted. I would have posted a link to this answer yet could not because it was deleted. $\endgroup$
    – polcott
    Commented Jul 6, 2022 at 15:21
  • $\begingroup$ Please read cs.stackexchange.com/help/deleted-answers first. I suggest you make sure you understand what the requirements for answers are and explain why you think your answer meets those requirements, and in particular, show that you know what question was being asked and articulate how your answer answers that specific question. $\endgroup$
    – D.W. Mod
    Commented Jul 6, 2022 at 15:21
  • $\begingroup$ You can post a screenshot of your deleted answer, or include the text of the latest version of your answer in a quotation block and clearly indicate that you are showing the deleted content for those who cannot see it, but just a title of "why was my answer deleted?" and the text of a deleted answer is likely to be poorly received. I suggest that you follow the advice in my prior comment, and focus more on understanding community expectations. $\endgroup$
    – D.W. Mod
    Commented Jul 6, 2022 at 15:23
  • $\begingroup$ @D.W. I executed the code of the original question and showed its full behavior thus providing a 100% complete answer to the original question. $\endgroup$
    – polcott
    Commented Jul 6, 2022 at 15:23
  • $\begingroup$ If you want to know the answer to why your question was deleted, then you're more likely to have success if you articulate a clear question following the approach I outlined above, show that you are willing to learn and follow community expectations, be responsive to feedback, and listen without arguing. People are more likely to be willing to spend their time to explain something to you if they believe you will listen, take it in without arguing or contradicting them, and adjust your participation based on that feedback. $\endgroup$
    – D.W. Mod
    Commented Jul 6, 2022 at 15:26
  • $\begingroup$ @D.W. The above material is exactly my original answer with nothing added besides the link to the original question. This answer proves that it directly executes the verbatim code provided in the original question. Furthermore it answers the original question by showing the exact behavior of this original code. I have spent the last five years working full time on this and thus will not accept rejecting my work out-of-hand without review. $\endgroup$
    – polcott
    Commented Jul 6, 2022 at 15:35
  • $\begingroup$ @D.W. "If you're asking why your answer was deleted, please remove all of the technical material and focus on asking that." That you did not recognize that these technical details are the original answer proves that you deleted this answer without review. $\endgroup$
    – polcott
    Commented Jul 6, 2022 at 16:06

2 Answers 2

Reset to default
5
$\begingroup$

I deleted this answer, in response to multiple flags from community members. I deleted it because, in my judgement, the post did not comply with community rules. In particular, as far as I could tell, it did not answer the question that was asked.

We have certain rules and expectations on this site. One rule is that the answer must answer the question that was asked. (It is not sufficient to provide some related material, or something else that you think others might be interested in, or your own thoughts that you are hoping for feedback on, or an answer to some other related question that wasn't asked.) These rules exist for a reason, because generally we think it helps us best advance the mission of this site.

As a reminder, the question that was posted is "does [this] well known proof really proves the halting problem theorem?" It was asking for feedback on a specific proof and raised some specific doubts on that particular proof. In my opinion, your post did not answer that question. It did not explain whether that particular proof really does prove the halting theorem. It did not address the specific points that were raised in the question or where feedback was requested. Posting an execution trace or a big block of code is not considered sufficient to constitute an answer on its own; it could be used to support an answer, but we are looking for explanation and ideas and justification. Instead, the answer appears to be text on the halting problem with your ideas on the halting problem. As such, it does not meet our community standards. (In addition, I notice that you have already posted those ideas here before and they have not been well received. I suspect the repeated re-posting of those ideas might be causing some frustration among some members of this site. And, this question was an old question that already seems to have good answers.)

We generally don't delete an answer because it is wrong. But we frequently do delete an answer if it does not clearly answer the question that was asked.

Our site works differently than others you might be used to. We are not a discussion forum. We have strict quality standards and a specific format that we enforce. This probably has its positives and its negatives, but it's how our site works, and we expect participants here to comply with those norms and expectations and policies.

Others have given you a great deal of feedback before, and I see little point in repeating it.

My impression of your participation on this site is that you have specific ideas you are seeking attention for, but that the members of this site have not shown much interest in those ideas. The site has a specific mission and purpose, and my sense is that repeatedly posting those ideas is not contributing to that mission, and is somewhat disruptive to that mission. As such, my prediction is that continuing this behavior is not likely to be well received.

I want to give you an analogy. Suppose there was a weekly quilting group, and a newcomer showed up to the group one week and wanted to give a speech about why everyone should vote for one specific political candidate. I think we would all expect that the newcomer might be asked to stop or to leave, as that is not part of the purpose of the group, and is disruptive to the group's purpose. Now imagine that the newcomer had done this several times before on previous weeks; and other newcomers had done similar things in the past. It's likely that such a group would take various steps to defend itself from such disruption. Even if the newcomer protests "but my points are important and correct!", even if they really are right that their preferred candidate is better, they still would not be likely to be welcome -- because such a rejoinder is missing the point. I realize the analogy is imperfect, but I'm hoping it might give you pause for thought.

I recommend that you take a break from posting here about the halting problem. My impression is that it is not being positively received and members of the community may have lost their patience with it. Members of the community are complaining to the moderators that you are re-posting the same material (or similar material) repeatedly, and that this is not appreciated. I recommend you focus on something that others will find useful. Even if you believe it is technically correct, if others do not find it useful, then it is probably not contributing to the site's mission.

I expect that you may continue to find your experience here unsatisfactory as long as you continue with your current approach to participation on this site. Others have given you extensive feedback and advice on how to fit into this site's expectations better, e.g., at https://cs.meta.stackexchange.com/a/1768/755, Why was my answer deleted when it is in fact correct?, in private messages from the moderators that I am not at liberty to share, and in other places. I encourage you to take those to heart if you plan to continue participating here.

$\endgroup$
4
  • $\begingroup$ "the question that was posted is "does [this] well known proof really proves the halting problem theorem?" 97.5% of the words of the post were about a specific concrete example, not about the halting problem in general. I conclusively proved that h(c,c) correctly predicts that its input never reaches its final state, thus is non-halting. Thus my answer directly applies to 97.5% of the post. $\endgroup$
    – polcott
    Commented Jul 7, 2022 at 18:22
  • $\begingroup$ Because this same answer equally applies to all of the halting problem counter-example inputs: (including the Peter Linz proof) This general principle refutes conventional halting problem proofs: Every simulating halt decider that correctly simulates its input until it correctly predicts that this simulated input would never reach its final state, correctly rejects this input as non-halting. My answer equally applies to the general case thus my answer is 100% relevant to the post. It answers both the specific example question and the general question about the halting theorem. $\endgroup$
    – polcott
    Commented Jul 7, 2022 at 18:46
  • 2
    $\begingroup$ Others have given you extensive feedback and advice on how to fit into this site's expectations better - I think one (of many other) problems is that there is no way to fit this into the site expectations. If this somehow becomes a coherent analysis, then it'll take an entire (and potentially huge) paper to rigorously explain the details. Definitely not what is expected on this site. $\endgroup$
    – Dmitry
    Commented Jul 8, 2022 at 0:04
  • $\begingroup$ @Dmitry My original answer proves the h(c,c) does correctly predict that its correct and complete simulation of its input never reaches the "ret" instruction (final state) of this input thus is correctly decided as non-halting. and no one can possibly show otherwise. Since this input exactly matches the conventional halting problem pathological input template this same reasoning applies to all of the conventional proofs including the Peter Linz proof. $\endgroup$
    – polcott
    Commented Jul 8, 2022 at 0:18
-2
$\begingroup$

Why was following verbatim answer deleted when it is correct and directly applies to the original question?

Reviewer's assumed that my answer did not apply to the original question without actually looking at anything that I said.

My original answer proves that the h(c,c) code example provided in the original post (comprising 97.5% of the original question) does correctly predict that its complete and correct simulation of its input would never reach the "ret" instruction (final state) of this input, thus is correctly decided as non-halting by h.

Because this code sample correctly implements the conventional pathological relationship of the halting problem proofs its decidability also applies to these conventional proofs. Thus my answer directly applies to 100% of the original question.

This is another example comparable to the sample code: An impossible program: Strachey(1965) The Computer Journal, Volume 7, Issue 4, January 1965, Page 313,

$\endgroup$
11
  • 2
    $\begingroup$ without looking at anything that I actually said. - that's rich, coming from you. Anyway, as D.W. said, just stop posting about halting problem, please. You won't get the feedback you seek. $\endgroup$
    – Dmitry
    Commented Jul 7, 2022 at 19:15
  • $\begingroup$ @Dmitry In my reply to the other answer I did prove that my answer does apply to 100% of the entire question. $\endgroup$
    – polcott
    Commented Jul 7, 2022 at 19:18
  • $\begingroup$ @Dmitry I will get the feedback that I seek when my work is reviewed honestly and not simply dismissed-out-of-hand without review. It is an objective fact that I am correct and it cannot be shown otherwise. h(c,c) does correctly predict that its correct and complete simulation of its input would never reach the "ret" instruction of this input. $\endgroup$
    – polcott
    Commented Jul 7, 2022 at 19:20
  • 2
    $\begingroup$ I wish I had a fraction of your self-confidence. $\endgroup$
    – Dmitry
    Commented Jul 7, 2022 at 19:21
  • $\begingroup$ @Dmitry It is not mere confidence thousands of reviews failed to correctly find a single mistake. h(c,c) does correctly predict that its correct and complete simulation of its input would never reach the "ret" instruction of this input. Because this is a proven fact no rebuttals have been presented. $\endgroup$
    – polcott
    Commented Jul 7, 2022 at 19:23
  • $\begingroup$ I know it's pointless (see my first comment) (especially given that people did already point out the mistake), but let me give you another (very close) analogy: if your answer is written in Chinese, we also won't find a single mistake. $\endgroup$
    – Dmitry
    Commented Jul 7, 2022 at 19:25
  • $\begingroup$ @Dmitry Find a mistake in this: h(c,c) does correctly predict that its correct and complete simulation of its input would never reach the "ret" instruction of this input. $\endgroup$
    – polcott
    Commented Jul 7, 2022 at 19:27
  • $\begingroup$ I believe I said that I won't review any of your crap unless you satisfy basic conditions I've specified. The conditions are basic, because anything without them can't be called rigorous reasoning (and could as well be written in Chinese). (And again, people already found the mistake. Not that you actually read any of their feedback) $\endgroup$
    – Dmitry
    Commented Jul 7, 2022 at 19:30
  • $\begingroup$ @Dmitry In other words you dodge my challenge because you already know that what I said irrefutably true. If this is true then h(c,c) would correctly decide that its input does not halt. If h(c,c) correctly decides that its input does not halt then all the (isomorphic) counter-examples to the halting theorem are equally decided as non-halting. $\endgroup$
    – polcott
    Commented Jul 7, 2022 at 19:34
  • $\begingroup$ @Dmitry every "mistake" that was found was beside the point that h(c,c) does correctly predict that its correct and complete simulation of its input would never reach the "ret" instruction (final state) of this input (thus is correctly determined to be non-halting) thus no actual rebuttal what-so-ever. $\endgroup$
    – polcott
    Commented Jul 7, 2022 at 20:23
  • $\begingroup$ @Dmitry A Complete Formal Semantics of x86-64 User-Level Instruction Set Architecture $\endgroup$
    – polcott
    Commented Jul 7, 2022 at 22:25

You must log in to answer this question.

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