A-level Computing/AQA/Paper 1/Theory of computation/Halting problem

Computable and non-computable problems Turing machine Halting Problem Very early on in modern computing, a British academic named Alan Turing devised the halting problem. This problem is to do with whether we can determine if a program will ever come to a halt or run for ever, for example: console.writeline("hello") Would write hello to the screen then stop. However, take a look at: dim x as integer = 9 while x > 8 console.writeline("hello") end while This would never finish, it would never come to a halt as x will always be larger than 8 and never get any smaller. This means the while loop will continue for ever, constantly printing out "hello". In the two cases shown it is easy to tell if a program will halt or not, but it isn't so easy for all programs. Imagine we get a more complex piece of code: dim x as integer = 9 dim total as integer = 0 while total < 100 total = total + x x = x / 2 end while This is harder but still solvable taking a little more thinking and a little time on the processor. We could get a piece of code that takes weeks, years or even thousands of years to finish. But how can we know that all programs will end or not? To determine whether the program halts we: run a program with a given input, if it stops we know it stops BUT if it keeps running beyond a reasonable amount of time we cannot conclude that it will loop for ever (maybe we need to wait a little longer...) Surely we create a mathematical proof to determine whether code will end or not I hear you say. Well let's prove just the opposite: thumb|centre|The halting solution H takes an input program A and a set of inputs X, it then determines whether the program will finish executing or not thumb|centre|You can replace the Input X with a copy of the program A. As the program A is made from code, this can be transformed into 1s and 0s, giving H a data input Let us create a program K that will loop forever if the result of H is to halt, and halt if the result of H is to loop for ever: function K(i): if H(i,i) = halt then loop forever else halt thumb|centre|If H says halt, K will loop. If H says loop K will halt, thus the Halting Solution H will be undecidable We can therefore see that there are examples of programs such as K that we cannot determine whether they are ever going to halt. Read more on the halting problem