Understanding the Halting Problem

Подписаться 195 тыс.

Просмотров 79 тыс.

50% 1

The halting problem is an important problem in computer science that asks whether we can construct an algorithm to determine whether a computer program will run forever. It turns out that the halting problem can't be solved, and in this video, we look at the proof to understand why.
***
Spanning Tree is an educational video series about computer science and mathematics. See more at spanningtree.me
To be notified when a new video is released, sign up for the Spanning Tree mailing list at spanningtree.substack.com/
Spanning Tree is created by Brian Yu. brianyu.me/
Email me at brian@spanningtree.me to suggest a future topic.

Опубликовано:

6 май 2023

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 558

@fredoverflow Год назад

I love how the green robot is still running when the video ends 😂

@camerontangen2957 Год назад

Technically, if the input is -1, the program will eventually halt. This is because once you reach max integer size, it will revert to min integer size and eventually increase to -1.

@dancer2234 Год назад

But is it possible to make an algorithm that can determine whether a program will run forever in all cases EXCEPT when evaluating a program which contains itself? That seems essentially equally practically useful

@hihoktf

We are using OPPOSITE as a program, and also as an input; but the "OPPOSITE as an input" needs an input, and none is supplied to it in this scenario.

@Rocket-Pirate Год назад

This proves that you can’t write a program that solves the halting problem in ALL cases, not that you can’t write a program in any case

@lightning_11 Год назад

It feels like we should still be able to make programs that solve the haunting problems in certain, restricted scenarios.

@Wonders_of_Reality Год назад

Note: that we might make a program that can IN SOME CASES predict whether an algorithm stops or runs indefinitely. In all cases-no, it’s proven. But in some cases-possible.

@duckpilot962 Год назад

tf is goin on here

@Trank933 Год назад

I wonder if it's your channel being recommended to people recently that inspired you to continue making more videos or something else. Either way I am glad that you do it, keep up the good work!

@Dark_Slayer3000 Год назад

Luckily we can easily write a halting program for any specific program, just not for every program.

@GuitarSlayer136 Год назад

Watching this dude's content I feel like he deserves a play button specifically for college professors and tech school instructors using the video without giving credit/compensation because it's better than anything they could do.