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.
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.