,THE HALTING PROBLEM IS THE QUESTION ,ALAN ,TURING PROVED UNANSWERABLE IN #AICF3 GIVEN AN ARBITRARY PROGRAM AND ITS INPUT1 DOES THE PROGRAM EVENTUALLY HALT1 OR RUN FOREVER8 ,TURING SHOWED NO GENERAL ALGORITHM CAN DECIDE THIS NOT 8WE HAVEN'T FOUND ONE YET10 BUT A PROOF THAT NONE CAN EXIST4 ,THE PROOF IN ONE BREATH ,SUPPOSE A MAGIC ORACLE HALTS" EXISTED THAT ALWAYS ANSWERED CORRECTLY4 ,BUILD A PROGRAM TWIST THAT ASKS THE ORACLE ABOUT ITSELF AND DOES THE OPPOSITE3 IF THE ORACLE SAYS 8TWIST HALTS10 TWIST LOOPS FOREVER2 IF IT SAYS 8TWIST LOOPS10 TWIST HALTS INSTANTLY4 ,NOW FEED TWIST ITSELF TO THE ORACLE4 ,WHATEVER THE ORACLE ANSWERS1 TWIST MAKES IT WRONG SO THE ORACLE CANNOT EXIST4 ,WHY IT MATTERS "9 ,COMPILERS CAN'T PERFECTLY DETECT INFINITE LOOPS THEY CAN ONLY WARN ABOUT PATTERNS4 "9 ,ANTIVIRUS CAN'T PERFECTLY DETECT MALICIOUS PROGRAMS DETECTION IS BOUNDED BY DECIDABILITY4 "9 ,BUSY ,BEAVER " IS UNCOMPUTABLE PRECISELY BECAUSE SOLVING IT WOULD SOLVE HALTING4 "9 ,IT DEFINED THE BOUNDARY OF COMPUTATION ITSELF THE FOUNDING RESULT OF THEORETICAL COMPUTER SCIENCE1 ALONGSIDE ;,GDEL'S INCOMPLETENESS THEOREMS4 ,SEE ALSO "9 BIGGEST NUMBERS "9 FAMOUS SOFTWARE BUGS "9 HISTORY OF PROGRAMMING "9 ,ALAN ,TURING