Az előző fejezetekben bevezetük a program és a feladatat fogalmát, és definiáltuk az azonos állapottéren levő feladat–program párok között a megoldás fogalmát. A gyakorlatban általában azonban a feladat és a program különböző állapottéren van: példaként megemlíthetjük azt az esetet, amikor egy feladat megoldására a programban további változókat kell bevezetni, azaz a feladat állapotterét újabb komponensekkel kell bővíteni.

A továbbiakban megvizsgáljuk, hogy mit tudunk mondani a különböző állapottéren adott programok és feladatok viszonyáról a megoldás szempontjából és ennek alapján általánosítjuk (kiterjesztjük) a megoldás fogalmát erre az esetre is.

4.1A feladat kiterjesztése

Ha egy feladat állapotterét kibővítjük újabb komponensekkel, mit jelentsen ez a feladat vonatkozásában? Elég kézenfekvő, hogy ebben az esetben a feladat ne tartalmazzon semmiféle kikötést az új komponensekre.

4.1. Definíció (FELADAT KITERJESZTéSE).

Legyen a állapottér altere az állapottérnek. Az relációt az feladat kiterjesztésének nevezzük, ha

A definíciót úgy is fogalmazhatjuk, hogy a feladat kiterjesztése az összes olyan -beli pontot tartalmazza, aminek B-re vett projekciója benne van -ben. semmilyen megszorítást.