Skip to main content
Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

5
  • 14
    $\begingroup$ Just a nitpick: "Then there is some definition of do_something that will fool any algorithm attempting to determine X" should be "For any algorithm attempting to determine X, there is some definition of do_something that will fool it". Essentially, the halting problem doesn't say there is some magical (machine, word) pair that no machine can tell whether it halts; but rather that you can't make any machine that works on all pairs. $\endgroup$ Commented Aug 18, 2023 at 8:01
  • 1
    $\begingroup$ @gnarrithas That was what I meant, but I reworded for clarity. $\endgroup$ Commented Aug 19, 2023 at 1:14
  • $\begingroup$ While this answer is correct and technically does answer the actual question asked by the OP, that actual answer is only given in the offhand remark that "whether a program has undefined behavior is decidable for a Turing-complete language that completely defines the behavior of every program" in the middle of lots of other tangential discussion. I feel like this answer would be greatly improved if that specific sentence was given a lot more prominence. $\endgroup$ Commented Aug 20, 2023 at 10:21
  • $\begingroup$ I neither understand what Rice's theorem, nor what the example with the main() function has to do with undefined behaviour: As the OP already wrote, "undefined behavior" means that it depends on the compiler and/or the hardware how a (part of a) program is executed. This is not the case in your example. $\endgroup$ Commented Aug 20, 2023 at 17:53
  • 2
    $\begingroup$ @MartinRosenau OP asked how undefined behavior is related to undecidability in the sense of Rice's theorem (though it wasn't mentioned by name). The answer is that they're unrelated. Talking about specific properties of UB would be confusing since it would suggest that those properties are relevant when they aren't. The only statement with UB in my answer is "42"[42];, and that was just meant to be an example easily recognizable as undefined. Pseudonym's answer would be a fine answer to a different question, or perhaps to this question if you deleted everything but the title. $\endgroup$ Commented Aug 20, 2023 at 19:47