Fontos, hogy a programfüggvény ugyanolyan típusú reláció mint a feladat volt. Így tehát a programfüggvény fogalmának bevezetésével lehetőségünk nyílik arra, hogy kapcsolatot teremtsünk egy adott feladat és egy adott program között. Természetesen ennek a kapcsolatnak azt kell leírnia, hogy mikor mondjuk egy programról azt, hogy megold egy adott feladatot.

Ezzel a definícióval végül is azt kívánjuk meg, hogy az állapottér olyan pontjaihoz, ahol a feladat értelmezve van, a program csak véges sorozatokat rendeljen (termináljon) és a sorozatok végpontjait a feladat hozzárendelje a kezdőponthoz.

Néha gondot okoz ennek a definíciónak a megértése. Miért a programfüggvény szerinti kép része a feladat szerinti képnek? "Így nem kapunk meg minden megoldást!" Pedig elég csak az autós példára gondolni. Például a fékfolyadék szintjének a minimum és a maximum szint jelzés között kell lenni. Ezt a karbantartás eredményeképpen teljesítjük, de egyáltalán nem egyételmű, hogy mi lesz a beállított szint. Annak meg nincs is értelme, hogy "minden lehetséges szintet" beállítsunk.

Sokszor felmerül a kérdés, hogy van-e összefüggés két feladat között a megoldás szempontjából? Ezzel kapcsolatos a következő definíció.

A szigorítás defiösszevetvesszevetve a megoldás definíciójával könnyen adódik a következő egyszerű, de fontos tétel: 2.1. állítás: Ha szigorúbb mint és megoldása -nek, akkor megoldása -nek is.