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)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay