#computing #mathematic #computer-science # [[Epistemic status]] #shower-thought Last modified date: 2022-05-08 13:23 Commit: 3 # Related - [[Computing/Intelligence/Can AI solve Godel s paradox]] - [[Mathematic/Hilbert]] - [[Philosophy/Rationality/Problems]] - [[Computing/Computing]] - [[Universal quantum computer]] - [[Chiara Marletto]] # Halting problem ![a piece of toast is in the style of a circuit diagram, product patent, labels, detailed technical drawing ](https://lexica-serve-encoded-images.sharif.workers.dev/md/03138047-9825-4125-bbd0-0e0b836ad082) The Halting Problem is an important concept in computer science that deals with the question of whether a program will ever finish running. It states that it is impossible to determine, in general, whether a program will ever finish running or will keep running forever. The Halting Problem is an important concept in computer science because it is used to prove the impossibility of certain problems and to prove the limits of computation. It is also used as a tool for analyzing algorithms and determining their complexity. Ultimately, the Halting Problem highlights the fact that some problems, despite our best efforts, can never be solved. ![medium: chalk on whiteboard, Notation, Symbols, Lines, Sequences, Interpretation, Instructions, Communication, Visuality, Process, form, line, character, surface, space, material, immaterial, sensual, symbolic, conceptual, Series, Variations, Temporalization, Processualization, Notation, Instruction, Form, Sign, Symbol, Movement, Parallel, Sequential, Disordered, Unconnected, Static, Visual, Mental, Iconic, Imaginative. Creative, large-scale, multi-part, process, drawing, repetition, variation, order, chaos, improvisation](https://lexica-serve-encoded-images.sharif.workers.dev/md/09e6901c-a5c4-4334-bbcd-73a46b1389e6) The halting problem emerged after [[Turing]] proposed a solution to the [[Entscheidungsproblem]] using [[Turing machine]]s. A [[Turing machine]] either halt or doesn’t while processing an [[Algorithm]], and neither a human or a [[Turing machine]] can solve the problem of knowing whether all algorithms will halt or not. I emphasise the “all”, sure, I can notice if my code will run in an infinite time if it looks like this ```py while True: print(“hello”) ``` # To consume [On the Learnability of the Uncomputable](https://www.ics.uci.edu/~rickl/publications/1996-icml.pdf) [[Godel Theorem|Godel]] [[Lambda calculus|Church calculus]]