Correctness of MICRO-HILLARY

A problem solver is complete if it terminates with a solution when one exists [29, p. 75]. If, when starting from a solvable state, we never reach unsolvable states, and if the range of the heuristic function is finite, then a complete set of macros yields a complete problem solver.

Let S be a set of states and O a set of basic operators. Let $P \subseteq S \times S$ be a set of solvable problems with the following property:

$$\forall \left \langle s_i , s_g \right \rangle \in P, \foral... ... \left [ solvable(s_i,s) \rightarrow solvable(s,s_g) \right ].$$

Let h be a well-behaved heuristic function with a finite range, R_h, over S ( $R_h=\vert\{h(s) \vert s \in S \}\vert < \infty$). Let M be a complete set of macros. Then, SolveProblem using M is a complete problem solver with respect to P. Furthermore, the number of operator applications is bounded by (|O|+B_m) R_h where B_m is the total length of macros in M.
Proof:
In every step of the hill-climbing procedure we are guaranteed (by the completeness of M) to find a state with a heuristic value which is lower than the value of the current state. Since h is well-behaved, and since it has a finite number of values, R_h, we can make at most R_h steps before reaching a goal state with h(s)=0. At every step, in the worst case, we try all the basic operators and all the macros before finding the one that makes progress. Therefore the total number of operator applications is bounded by (|O|+B_m) R_h. $\Box$