Some problem can't be solved by a computer no matter how much power you throw at them. Some problems can, but not always efficiently.

We are learning...


So that we can...



Problems that you can solve using an algorithm are computable / solvable. Some problems are non-computable / unsolvable even with infinite resources because they are non-algorithmic.


The number of solvable problems is infinitesimally small compared with the full set of all problems.




A decision problem is one which has a yes / no answer. For instance...



If a decision problem has an algorithmic solution, then it is essentially decidable / solvable / computable. Conversely, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that will always lead to a correct yes / no answer.




The Tiling Problem

"Using any (finite) set of three different types of tiles, is it possible to construct an algorithm which will tile a floor of any size such that edges of the tiles that touch have the same colour, if we are not allowed to rotate the tiles?"




So, we can solve some particular instances of the tiling problem easily, but it is impossible to devise an algorithm to solve all instances of the problem. It's not simply impossible in practice (eg, because today’s computers are not powerful enough) but, impossible even in theory!

This particular tiling problem has a brute force solution which is within the factorial time complexity band where the time taken to check for a suitable solution increases super rapidly as the number of tiles increases.


Even checking one combination every microsecond, finding that there is no solution to a particular 5x5 tiling problem would take 491,520,585,955 years! What a waste of time!



Even if a problem is solvable, we might not be able to find a solution in a reasonable time. Remember BigO? Read the following information and then complete the task which follows.




Optional, proper hard bit (which you don't have to do)


Just to reiterate - you don't really need to do this bit but some of the more mathematically (and financially) minded amongst you might want to have a 'butchers hook' at the world of P, NP and NP-Complete problems ...


Complexity class P contains all tractable, solvable problems which have known polynomial time (or less) complexity solutions. Complexity class NP contain all tractable and intractable solvable problems whose potential solutions can be checked with a polynomial time (or less) complexity algorithm. Research has identified a subset of problems which are the hardest NP problems – these are called NP-complete problems.


It can be shown that P is a subset of NP (which is good). At the moment, there is an open question...

Does P = NP?

In fact, the answer to this question is so important that the the Clay Mathematics Institute will award $1,000,000 dollars to the first person or group of people to answer this question! There are 6 so-called Millenium Problems which are so hard that no-one has ever solved them yet so important that solving them will potentially change the course of history - yes, really that important ...



The Halting Problem was theorised by Alan Turing and so is, not surprisingly, hard to understand. It works on the basic premise that when you run a computer program, it can do one of two things...


Alan wondered (for a Turing Machine because proper computers hadn't been invented) whether ...

“Given any arbitrary Turing Machine and any arbitrary input for the machine, will the given machine ever halt on the given input?”

In modern terms, this would be like working out whether a computer program would stop without actually running it and just be inspecting the structure of the code and predicting how it would respond on a given input.




What's next?

Before you hand your book in for checking, make sure you have completed all the work required and that your book is tidy and organised. Your book will be checked to make sure it is complete and you will be given a spicy grade for effort.