DEV Community

David Haley
David Haley

Posted on

One Byte Explainer: the Halting Problem

This is a submission for DEV Computer Science Challenge v24.06.12: One Byte Explainer.

Explainer

Is this loop actually infinite, or will it eventually finish? In 1936, Alan Turing used his Machine to show we can’t know. Consider a program that checks if it stops and if true: loops forever. A paradox! Some problems are literally impossible: avoid them.

Additional Context

For interest, here is the paradox:

  • If the halting check is true, then the program loops forever… even though the check says it halts.

  • If the halting check is false, then the program stops… even though the check says it never halts.

TEAM MEMBERS: @dchaley @lynnlangit

Top comments (0)

Heroku

Build apps, not infrastructure.

Dealing with servers, hardware, and infrastructure can take up your valuable time. Discover the benefits of Heroku, the PaaS of choice for developers since 2007.

Visit Site

👋 Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay