# How do you know a problems is non-computable?

I am currently looking at intractable problems and N/NP etc but am a little confused about one term used in the book I am reading. It says in this book that a non computable problem is one which admits no algorithm exists for solving it. The book then goes on to use an adaption of Wangs Tile's as an example of this - stating that no algorithm exists which will output yes or no when a solution is/is not found.

Although I haven't proved it I would have thought that this could be done via a backtracking algorithm (yes it would be inefficient but surely doable)? Or am I looking at the meaning of non-computable the wrong way? Or maybe just not understanding that Wangs Tiles cannot be done full stop.

• Is your algorithm guaranteed to eventually stop? Commented Apr 27, 2016 at 11:48
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! Commented Apr 27, 2016 at 12:08
• You need to check a basic source on computability. What you probably have in mind is a semi-decider: if there is a solution, you can find one in finite time. But what if there is none? Commented Apr 27, 2016 at 12:09
• Hmm, I would have thought any algorithm which was a back tracking algorithm would eventually stop? Once it has exhausted all possibilities of course - thought I suppose it could get jammed in a loop. Commented Apr 27, 2016 at 14:28
• The problem is that there is an infinite number of possibilities in the Wang tiles problem. You cannot exhaust them all. Commented Apr 27, 2016 at 14:29

"Non-Computable" is very broad. Do you mean a problem that has no solution or a problem that is running seemingly infinitely? Also I'd like to note that non-computable doesn't mean has no answer.

If you mean a problem that seemingly runs forever, those problems do have solutions, but we're never going to see them. For example, Ackermann recursion for large numbers is a problem with "no solution" because after 3 recursions it takes days for the next answer, the 5th takes weeks and it grows exponentially after that. That's "non-computable" but it does have an answer, but we'll never know it.

Any algorithm or process that never stops also is also non-computable since it will never give you an answer to a problem. This is different than ackermann recursion in the fact that ackermann has an answer, but counting the number of molecules in the universe has no answer as the universe is infinitely expanding and the number is growing. That problem would just go on forever as there is no answer since the inputs grow infinitely. This is similar to the example you give as there are infinite possibilities to check.

• This isn't quite right. There's a big difference between n/0, which is undefined, and the Hatling problem, which has no algorithm to solve it, even though the problem is perfectly well defined. Commented Apr 28, 2016 at 6:40
• I edited my post and got rid of that example and added another one. Commented Apr 28, 2016 at 6:44