Algorithms For Dummies

  Ten Algorithmic Problems Yet to Solve 

     401

Determining Whether an  

Application Will End

One of the problems that Alan Turing proposed in 1936 is the issue of whether an 

algorithm, given a description of a program and an input, could determine whether 

the program would eventually halt (the halting problem). When working with a 

simple application, it’s easy to determine in many cases whether the program will 

halt or continue running in an endless loop. However, as program complexity 

increases, determining the result of running the program with any given input 

becomes harder. A Turing machine can’t make this determination; the result is 

buggy code with infinite loops. No amount of testing that uses current technology 

can solve this issue.

A hypercomputer is a computing model that goes beyond the Turing machine to 

solve problems such as the halting problem. However, such machines aren’t pos-

sible using current technology. If they were possible, you would be able to ask 

them all kinds of imponderables that computers can’t currently answer. The arti-

cle at 

https://www.newscientist.com/article/mg22329781-500-what-will- 

hypercomputers-let-us-do-good-question/

 provides you with a good idea of 

what would happen if someone were able to solve this problem.