Most visszatérünk a fejezet elején szereplő autós példához. A feladat az volt, hogy készítsük fel az autót egy hosszabb útra. Attól függően, hogy az autó milyen állapotban van, azaz a jellemzői milyen értékekkel rendelkeznek: mennyi benne amekkoran, mekora a nyomás a kerműködik, műkődik-e az irányjeltevékenységekékenségek sorozatát hajtjuk végre, felpumpáljuk a kerekeket, kicserélünk egy izzót és így tovább, lépésről lépésre változik az állapot, működik a program. Ha végül olyan állapotba jut az autó, hogy most már nyugodtan el lehet vele indulni egy hosszabb útra, akkor a program megoldotta a feladatot

Ahhoz, hogy egy program és egy feladat viszonyát megvizsgáljuk, elegendő, ha a programról tudjuk, hogy az állapottér egy adott pontjából kiindulva, az állapottér mely pontjába jut, mert a megoldás szempontjából a közbülső állapotok lényegtelenek. Természetesen vannak olyan – a programok minőségére vonatkozó – további kritériumok, amelyek szempontjából egyáltalán nem mindegy, hogy a program hogyan oldja meg a feladatot (ilyen lehet például a hatékonyság, a program idő- és tárigénye), de a továbbiakban ezekkel egyelőre nem foglalkozunk.

Ezért vezetjük be a programfüggvény fogalmát, amely a program futásának eredményét jellemzi.

Az első követelmény azt fogalmazza meg, hogy csak azokban a pontokban van értelme azt vizsgálni, hogy hova jut egy program, ahonnét kiindulva a program nem "száll el". A második pont értelemszerűen azt írja le, hogy ahova a program eljut, az a sorozat utolsó eleme.

Ha két program programfüggvénye megegyezik, az azt jelenti, hogy a két program működésének eredménye ugyanaz. Ezért mondjuk ebben az esetben azt, hogy a két program ekvivalens.

A programfüggvény elnevezés megtévesztő lehet, hiszen egy program programfüggvénye nem feltétlenül függvény, sőt az sem biztos, hogy determinisztikus reláció (parciális függvény). Jobban kifejezi a fogalom tartalmát a hatásreláció elnevezés. Mindkettőt használni fogjuk.