Halting Problem in Python - Computerphile

No need to understand Turing machines to comprehend the halting problem. Professor Thorsten Altenkirch has a way of using Python to demonstrate the issue.

This video was filmed and edited by Sean Riley.

[ThorstenAltenkirch]

I forgot to say that the impossibility of writing a function that decides the Halting problem shows that many other problems are unsolvable too. For example we cannot write a program that decides wether a logical formula (in predicate logic) is true. We can write a program that translates the halting problem for any program into a logical formula that is true exactly if the program holds. Hence if we had a program that decides logic we could also decide the halting problem. Which we can’t and hence we can’t decide predicate logic either.

[xetera]

Technically, that code terminates with "NameError: name 'true' is not defined"
Capitalization: 1
Halting problem: 0

[azertyQ]

"Is logic inconsistent?"

Gödel: hold my beer

[lawrencedoliveiro]

1:16 Space before colon, but not after comma. *‌twitch‌*

[tnb]

The title should say "the wierd holding problem"

[Shibzzeg]

I had to watch this twice, but I understand it now, it's a beautiful way to explain it from a different angle. Thank you, professor Altenkirch! :)

[allmhuran]

I can't get enough of Prof Altenkirch.

[hetulbhatt]

Weird has to have a 'wierd' spelling.

[TheSienn]

In German, if you want to make the "e" sound in English, you usually have "ie". If you want to make the "i" vowel sound, you use "ei", like in Leibniz. I imagine English is his second language and he is defaulting to that Germanic "ie" e sound. Just to clear up where his "wierd" spelling is probably coming from.

[CaptainWumbo]

proof by contradiction huh. how dare you bring math into my sweet sweet world of making the computer do the math for me.

[youtoobfarmer]

the more important typo is "holds" instead of "halts"

[mrcake]

Pinocchio: "My nose grows now"

[XoNasX]

Wow, very nice video. This was a very enjoyable ride explained at the exact correct level of depth to understand and still enjoy it.

[casperes]

I genuinely thought it was easier with Turin machines...

[Flackon]

That was a pretty elegant explanation. Very nice

[MrMelon]

Finally a Computerphile video I can follow! - Data Scientist

[unvergebeneid]

People are commenting on his spelling of "weird" but nobody realised that when he mixed up "halts" and "holds" because he pronounces them the same way.

[unperrier]

*QUESTION* : are there other classes of functions for which it's not possible to write *holds()* other than those functions that do call *holds()* (just like *weird()* does)? thanks.

[aayushf]

have you tried pip install does-halt?
There's a Python package for everything

[whuzzzup]

Took me way too long to realize he said "true" and not "two".