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 t…


This content originally appeared on DEV Community and was authored by David Haley

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


This content originally appeared on DEV Community and was authored by David Haley


Print Share Comment Cite Upload Translate Updates
APA

David Haley | Sciencx (2024-06-23T02:57:11+00:00) One Byte Explainer: the Halting Problem. Retrieved from https://www.scien.cx/2024/06/23/one-byte-explainer-the-halting-problem/

MLA
" » One Byte Explainer: the Halting Problem." David Haley | Sciencx - Sunday June 23, 2024, https://www.scien.cx/2024/06/23/one-byte-explainer-the-halting-problem/
HARVARD
David Haley | Sciencx Sunday June 23, 2024 » One Byte Explainer: the Halting Problem., viewed ,<https://www.scien.cx/2024/06/23/one-byte-explainer-the-halting-problem/>
VANCOUVER
David Haley | Sciencx - » One Byte Explainer: the Halting Problem. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2024/06/23/one-byte-explainer-the-halting-problem/
CHICAGO
" » One Byte Explainer: the Halting Problem." David Haley | Sciencx - Accessed . https://www.scien.cx/2024/06/23/one-byte-explainer-the-halting-problem/
IEEE
" » One Byte Explainer: the Halting Problem." David Haley | Sciencx [Online]. Available: https://www.scien.cx/2024/06/23/one-byte-explainer-the-halting-problem/. [Accessed: ]
rf:citation
» One Byte Explainer: the Halting Problem | David Haley | Sciencx | https://www.scien.cx/2024/06/23/one-byte-explainer-the-halting-problem/ |

Please log in to upload a file.



There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.

Related Posts