Az állapottér fogalmának segítségével könnyen megfogalmazhatjuk, hogy mit értünk feladaton. Azt kell megfogalmaznunk, hogy egy adott állapotból (azaz az állapottér egy eleméből, pontjából) milyen állapotba (azaz az állapottér mely pontjába) akarunk eljutni.

A feladat fenti definíciója természetes módon adódik, abból, hogy a feladatot egy leképezésnek tekintjük az állapottéren, és az állapottér minden pontjára megmondjuk, hogy hova kell belőle eljutni, ha egyáltalán el kell jutni belőle valahova.

Az, hogy egy feladatnak mi lesz az állapottere, természetesen magától a feladattól függ, ám még a feladat ismeretében sem egyértelmű. Például egy pont síkbeli koordinátáit megadhatjuk derékszögűgű koordináta-rendszerben, de megadhatjuk polárkoordinátákkal is.

Mégis, az, hogy mit választunk állapottérnek, nagyon fontos, hiszen meghatározza, hogy a továbbiakban mit, és hogyan tudunk leírni. Ha túl kevés jellemzőt vizsgálunk – azaz az állapottér túl kevés komponensből áll – akkor lehetnek olyan fogalmak, amiket nem tudunk benne leírni, ha túl sok a komponens, akkor fölöslegesen túl bonyolult lesz a modell.

Tekintsük azt az egyszerű feladatot, hogy össze kelladni két természetes számot. Az állapotteret elég kézenfekvő módon három komponensűnek választhatjuk. A három komponens a két összeadandó és az összeg. Tehát , s a feladat

vagy

A két feladat nem azonos bár mindkettő két természetes szám összegéről szól. A különbség köztük az, hogy az feladat nem mond semmit arról, hogy mi legyen az összeadandókkal, a pedig kiköti, hogy maradjanak változatlanok.

Felvetődik, hogy nem lenne elég a két komponensű állapottér is? Legyen és

Ezt a feladatot azonban nem úgy interpretálnánk, hogy "adjunk össze két természetes számot", hanem úgy, hogynöveljünknk meg egy természetes számot egy természetes számmal".

Megjegyezzük, gyakran fogalmaznak meg feladatot úgynevezett "input-output" modellben is, azaz milyen bemenő adatokhoz milyen kimenő adatokat rendelünk. Ez a szétválasztás az és a feladat esetében nem okozna gondot, de a -hoz hasonló feladatok esetében már problémás lehetne, nem is beszélve a bevezetőben említett autós feladatról. Az állapotér modell igazi előnyeit a későbbiekben még tapasztalni fogjuk.

Felhíjuk a figyelmet arra, hogy a definíció szerint a feladat reláció, azaz általában nem determinisztikus, például és . A nem determinisztikusság azonban még "érdemibb" is lehet. Legyen a feladat a következő: határozzuk meg egy természetes szám egy valódi osztóját( a szám megváltoztatása nélkül)! Ebben az esetben és

Például pont szerinti képe . A -nak is, meg is valódi osztója, azaz .

Nagyon fontos, hogy pontosan lássuk a különbséget az előző feladat és a következő között: határozzuk meg egy természetes szám összes valódosztójátát! Ebben az esetben az állapottér is más lesz, hiszen egy természetes szám összes valódosztójaja nem egy szám, hanem egy halmaz. Tehát , ahol az véges részhalmazainak halmaza.

Most és .

Megjegyezzük még, hogy , például , de , például és .