What is the Halting Problem?

In this video we'll explore a little corner of a very interesting topic, the topic is computability.

Today we'll look at a particularly famous question, known as The Halting Problem.

Support What's a Creel? on Patreon:

FaceBook:

Music Channel:

Another channel with random things:

[Sully]

I've watched half a dozen videos on this topic, all using 'machines' or 'black boxes' and none of them made sense when at the end they arbitrarily used inverting outputs or other tricks and declared the problem unsolvable. This is the only video to explain *why* you're inverting the output and the repercussions. Also, the function perspective made more sense to me anyway. Thanks!

[PvblivsAelivs]

The solution you gave to the linked list problem does not meet all the conditions you applied.  Specifically, an element may be visited more than 3 times.  Suppose you have 1000 elements in a chain followed by a 5-cycle.  Pointer B will go aroung the cycle 200 times as it waits for pointer A to catch up.  (It's still linear time though.)