The halting problem is the problem of looking at the structure of a program and using it to determine whether or not the program would halt if you ran it. There is a proof by contradiction that you can’t have such a program (from the wikipedia page for the halting problem):
def g() → None:
if halts(g):
loop_forever()
This is a contradiction because if halts returns true then it shouldn’t have, because g will loop forever based on halts returning true, but if halts returns false then g will return None and halt, and so halts should have returned true.
But learning about this annoyed me, because it’s obvious what’s going on, halts is being forced into self reference, and a contradiction is only forced if halts is forced to return true or false. If it instead returned “I am embedded in a program with a 2 state logical contradiction” then that would be a better answer.
I think this is also Russell’s paradox in set theory, and might be related to Godel’s incompleteness. Basically the thing seems to be “self referential statements break our languages” and my feeling is just “create your languages so they talk about the nature of self reference! You’re creating a problem where there does not need to be a problem”… but obviously I haven’t fully understood the ideas or thought through all the implications, so it would be rash for me to make such a statement, but it is a feeling that I get.
I see, this is something I’ve wondered about… If the set is allowed to ‘half contain’ itself, or contain half of itself, then the paradox is kind of resolved. On your point about languages, I remember reading about the ‘Santa claus sentence’ which states: ” If this sentence is true, then Santa Claus exists”. Clearly, if the sentence were true, then Santa Claus would exist. But this is what the statement says, so Santa Claus must exist. Of course, if we instead ask what would happen if the statement is false, then we are not drawn to conclude that Santa Claus exists, merely that he wouldn’t even if the sentence were true...
When thinking about this I realized that the problem might just be that the way language is structured is inherently linear, so that to expand the statement fully would require it to be an infinitely long sentence of the form: “If ” If ” If “If ” ….infinitely deep ….” is true, then Santa Claus exists.” is true, then Santa Claus exists. ” is true, then Santa Claus exists. ” is true, then Santa Claus exists.” . This is the only way to parse the sentence using linear language, and clearly it depends on what the text ‘infinitely deep’ that I’ve used to signify the ‘rock bottom’ actually means. This is indeterminate, similar to how the equation (φ+1)/φ=φ can be expanded out into an infinite expression which converges to two possible values when you iterate upon it starting from a particular number. One of them is what’s commonly called the golden ratio, the other is the negative reciprocal of the (what’s commonly called) golden ratio.
I might think of more to say about this but don’t currently have the time to do so, or to reply to your other comment. Hopefully I will soon.
The halting problem is the problem of looking at the structure of a program and using it to determine whether or not the program would halt if you ran it. There is a proof by contradiction that you can’t have such a program (from the wikipedia page for the halting problem):
This is a contradiction because if halts returns true then it shouldn’t have, because g will loop forever based on halts returning true, but if halts returns false then g will return None and halt, and so halts should have returned true.
But learning about this annoyed me, because it’s obvious what’s going on, halts is being forced into self reference, and a contradiction is only forced if halts is forced to return true or false. If it instead returned “I am embedded in a program with a 2 state logical contradiction” then that would be a better answer.
I think this is also Russell’s paradox in set theory, and might be related to Godel’s incompleteness. Basically the thing seems to be “self referential statements break our languages” and my feeling is just “create your languages so they talk about the nature of self reference! You’re creating a problem where there does not need to be a problem”… but obviously I haven’t fully understood the ideas or thought through all the implications, so it would be rash for me to make such a statement, but it is a feeling that I get.
I see, this is something I’ve wondered about… If the set is allowed to ‘half contain’ itself, or contain half of itself, then the paradox is kind of resolved. On your point about languages, I remember reading about the ‘Santa claus sentence’ which states: ” If this sentence is true, then Santa Claus exists”. Clearly, if the sentence were true, then Santa Claus would exist. But this is what the statement says, so Santa Claus must exist. Of course, if we instead ask what would happen if the statement is false, then we are not drawn to conclude that Santa Claus exists, merely that he wouldn’t even if the sentence were true...
When thinking about this I realized that the problem might just be that the way language is structured is inherently linear, so that to expand the statement fully would require it to be an infinitely long sentence of the form: “If ” If ” If “If ” ….infinitely deep ….” is true, then Santa Claus exists.” is true, then Santa Claus exists. ” is true, then Santa Claus exists. ” is true, then Santa Claus exists.” . This is the only way to parse the sentence using linear language, and clearly it depends on what the text ‘infinitely deep’ that I’ve used to signify the ‘rock bottom’ actually means. This is indeterminate, similar to how the equation (φ+1)/φ=φ can be expanded out into an infinite expression which converges to two possible values when you iterate upon it starting from a particular number. One of them is what’s commonly called the golden ratio, the other is the negative reciprocal of the (what’s commonly called) golden ratio.
I might think of more to say about this but don’t currently have the time to do so, or to reply to your other comment. Hopefully I will soon.