CSC180: The Halting Problem: a 7 minute proof

[arberg]

Nice and simple presentation of the proof, excellent. Love your function names.

[josephgutierrez]

I am taking automata right now and have a final in 10 hours. You sir, are saving me! Great video!

[titanicloverable]

What’s stopping one from adding an if statement that says “if f = confused, don’t do the opposite”

[banook]

Thank you for a concise and understandable proof.

[benzanol]

Does this mean there is hypothetically a function that can neither be proven to have an infinite loop nor proven not to have an infinite loop?

[joshuascholar]

What if halt is three valued? What if it returns "true, false or undecidable" Can you prove that version of halt doesn't exist? Ie, it punts on self-referential programs.

[ddstar]

This is a demonstration of "context dropping" in logic. When you run confused(confused) you are no longer asking if it terminates, you are simply dropping the context (and the premise) of termination and forcing an infinite loop if it does in fact terminate. This is very common in logic when you drop the context of the premise. All this has demonstrated is that context-dropping is in fact, true. If you kept the premise, the code would have been halt(confused, confused) which returns false because if you DO actually execute confused(confused) it doesn't halt. Both statements are now validated, the context is kept and the premise is kept. In philosophy this context dropping is very common in platonic views all the way up to Kant; which I'm sure Turing was heavily influenced by, whether he knew it or not.

[ytpah]

halt(confused, confused) returns false. halt analyzes the given function and data, it doesn't run it. Don't execute confused() because you might hit an endless loop and if not the result is incorrect. pull request rejected

[leosousa]

(f, f) seems to be impossible, it would be like one defining x = x * 10

[ZeroG]

This makes no sensr. You cannot call confused(confused) because confused requires an argument for each invocation. You would have to call confused(confused(x)) for thus to even compile.

[ciarantaaffe]

This is bullshit. I have been convinced that this is wrong since I heard of it a couple years ago.
In mathematics there exists the idea of predicativity, invented by the great mathematicians around the time of Russell and Whitehead. It was central to their book "Principia Mathematica". Predicativity is the idea that we cannot define an object dependant on a totality which already contains it. In other words the definition of an object cannot depend on itself. For example we cannot define the number a=a+1-1 . This equation certainly holds, but is not a valid definition of a.
In this scenario, we cannot take halt and then compose functions in the manner shown above. confuse(confuse) expands to Thus we have an infinite membership chain, meaning that the definition of confuse(confuse) is not predicative. Even worse, we are defining it contrary to itself.
We can do this with simple functions too:
X:
"Run X
Print 0"
This machine is defined contrary to itself. However, it is not correct to conclude that machines which be ised to compose contrafictory machines do not exist. Consider:
Y:
"Run Z
Print 0"
This machine alone is legal. But if we define Z as follows:
Z:
"Run Y"
Well, now we have composed an illgal machine, because Y results in an infinite membership chain. Also, we can now see that the definition of Y depends on itself, meaning it is not predicative.