The Halting Problem

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

Explainer

The halting problem asks whether there can be a machine that determines whether a program will halt or continue indefinitely. It cannot exist; …


This content originally appeared on DEV Community and was authored by Danny Sebastián Díaz Padilla

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

Explainer

The halting problem asks whether there can be a machine that determines whether a program will halt or continue indefinitely. It cannot exist; if we add a negation to this machine and evaluate it on itself, it will always fail because of its contradiction.

Additional Context

Solved by Alan Turing. Explaining this concept is complicated, since it requires the use of several compound functions:

  1. Extended Explanation:

    • "H" which can determine whether any program 𝑃 stops or continues given an input.
    • We use "H" to create a program "D" that takes as input the code of a program "P".
    • "D(P)" calls "H(P, P)", evaluating "P" with its own code as input.
    • If "H(P, P)" says "yes" (P stops at P), "D(P)" enters an infinite loop.
    • If "H(P, P)" says "no" (P does not stop at P), "D(P)" stops.

  2. Paradox:

    • Passing "D" to itself as input: "D(D)":
      • If "H(D, D)" says that "D(D)" stops, "D(D)" enters an infinite loop (contradiction).
      • If "H(D, D)" says that "D(D)" does not stop, "D(D)" stops (another contradiction).


This content originally appeared on DEV Community and was authored by Danny Sebastián Díaz Padilla


Print Share Comment Cite Upload Translate Updates
APA

Danny Sebastián Díaz Padilla | Sciencx (2024-06-16T19:06:52+00:00) The Halting Problem. Retrieved from https://www.scien.cx/2024/06/16/the-halting-problem/

MLA
" » The Halting Problem." Danny Sebastián Díaz Padilla | Sciencx - Sunday June 16, 2024, https://www.scien.cx/2024/06/16/the-halting-problem/
HARVARD
Danny Sebastián Díaz Padilla | Sciencx Sunday June 16, 2024 » The Halting Problem., viewed ,<https://www.scien.cx/2024/06/16/the-halting-problem/>
VANCOUVER
Danny Sebastián Díaz Padilla | Sciencx - » The Halting Problem. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2024/06/16/the-halting-problem/
CHICAGO
" » The Halting Problem." Danny Sebastián Díaz Padilla | Sciencx - Accessed . https://www.scien.cx/2024/06/16/the-halting-problem/
IEEE
" » The Halting Problem." Danny Sebastián Díaz Padilla | Sciencx [Online]. Available: https://www.scien.cx/2024/06/16/the-halting-problem/. [Accessed: ]
rf:citation
» The Halting Problem | Danny Sebastián Díaz Padilla | Sciencx | https://www.scien.cx/2024/06/16/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