A program kiterjesztésének definíciójában az új komponensekre azt a kikötést tesszük, hogy azok nem változnak meg a kiterjesztett programban. Ezzel azt a gyakorlati követelményt írjuk le, hogy azok a változók, amelyeket a program nem használ, nem változnak meg a program futása során.
4.2. Definíció (PROGRAM KITERJESZTéSE).
Legyen a
állapottér altere az
állapottérnek, és jelölje
a
kiegészítő alterét
-ra. Legyen továbbá
program a
állapottéren. Ekkor az
-beli relációt az S program kiterjesztésének nevezzük, ha
A fenti definíció alapján a kiterjesztett program értékkészletében csak olyan sorozatok vannak, amelyek „párhuzamosak” valamely sorozattal az eredeti program értékkészletéből.
Vajon a kiterjesztés megtartja a program-tulajdonságot? Erre a kérdésre válaszol az
alábbi állítás.
4.1. állítás: Legyen a 
állapottér altere az 
állapottérnek, és jelölje 
a 
kiegészítő alterét 
-ra. Legyen továbbá 
program a 
állapottéren, és 
az 
kiterjesztése 
-ra. Ekkor 
program.
A tétel bizonyítása rendkívül egyszerű, a feladatok között szerepel.
A program kiterjesztése lehetőséget ad az ekvivales programok fogalmának kiterjesztésére is.
4.3. Definíció (PROGRAMOK EKVIVALENCIáJA).
Legyenek
,
programok,
altere mind
-nek, mind
-nek. Azt mondjuk, hogy
ekvivalens
-vel
-n,
A definíciónak egyszerű következménye az is, hogy a két ekvivalens program a közös altéren pontosan ugyanazokat a feladatokat oldja meg.
Valójában attól, hogy két program ekvivalens – azaz megegyezik a programfüggvényük – egyéb tulajdonságaik nagyon eltérők lehetnek. Ilyen – nem elhanyalgolható – különbség lehet például a hatékonyságukban. Egyáltalán nem mindegy, hogy egy program mennyi ideig fut és mekkora memóriára van szüksége. A program ezen jellemzőinek vizsgálatával azonban itt nem foglalkozunk.
A definíciókból közvetlenül adódik a következő állítás: 4.2. állítás: Egy program kiterjesztése és az eredeti program az eredeti állapottéren ekvivalens.