I'm reading Introduction to Artificial Intelligence by Ertel.
This line has me stumped from the textbook (page 102):
For decidable problems such as the 8-puzzle this means that the whole search tree must be traversed up to a maximal depth whether a heuristic is being used or not.
And decidable ca be defined thus:
an algorithm that can and will return a Boolean true or false value (instead of looping indefinitely)
Why can't the program return if it encounters the goal state before it has traversed the entire tree? What am I missing?
In case context is important, this is the preceding sentence:
In closing, it remains to note that heuristics have no performance advantage for unsolvable problems because the unsolvability of a problem can only be established when the complete tree has been searched through.
See page 102.
It says elsewhere in the book that heuristics often reduce computation dramatically for “solvable problems”! Is there a difference between “decidable” and “solvable” problems that's relevant here? It's not explained why heuristics are good for “solvable” problems and bad for “decidable” ones.