2.1. példa: Legyen .  ? Hány olyan pontja van az állapottérnek, amelyekhez a feladat ugyanazt rendeli, mint az -hez?

Megoldás:

Mivel a feladat hozzárendelése nem függ az állapottér harmadik komponensétől, a feladat ugyanezeket a pontokat rendeli az összes alakú ponthoz. Más pontokhoz viszont nem rendelheti ugyanezeket a pontokat, mert akkor az összeg nem lehetne ! Tehát öt olyan pontja van az állapottérnek amelyhez a feladat ugyanazt rendeli, mint az -hez.

2.2. példa: Legyen .

.

Megoldás:

2.3. példa: Fejezzük ki a programok uniójának programfüggvényét a programok programfüggvényeivel!

Megoldás: Legyenek programok. Ekkor a programfüggvény értelmezési tartományának definíciójából kiindulva:

Legyen . Ekkor

2.4. példa: Legyen és egy-egy feladat ugyanazon az állapottéren! Igaz-e, hogy ha minden program, ami megoldása -nek, az megoldása -nek is, és minden program, ami megoldása -nek, az megoldása -nek is, akkor és megegyeznek?

Megoldás: A leggyakoribb hiba, amit ennek a feladatnak a megoldásakor el szoktak követni, az az, hogy összekeverik az állítás feltételrendszerét magával a bizonyítandó állítással, és azt próbálják bebizonyítani, hogy valamelyik feladatnak minden program megoldása. Természetesen általában ez nem igaz, de nem is ez a feladat! Abból kell tehát kiindulnunk, hogy pontosan ugyanazok a programok oldják meg mindkét feladatot, és meg kell vizsgálnunk, hogy következik-e ebből az, hogy a két feladat megegyezik.

Induljunk ki abból, hogy minden program, ami megoldása -nek, az megoldása -nek, és válasszunk egy olyan programot, amelynek programfüggvénye megegyezik az relációval. Ekkor a választott program triviálisan megoldja az feladatot, tehát meg kell oldania -t is, azaz:

Most felhasználva, hogy minden program, ami megoldása -nek, az megoldása -nek is, és egy olyan program választásával, amelynek programfüggvénye megegyezik -vel, az előzőekkel analóg módon adódnak a fordított irányú állítások:

Az és állításokból következik, hogy a két feladat értelmezési tartománya megegyezik, míg az és állítások garantálják, hogy ezen közös értelmezési tartomány egyes pontjaihoz mindkét feladat ugyanazokat a pontokat rendeli, azaz .

2.5. példa:  . Az program megoldja -t. Igaz-e, hogy megoldja -et is?

Megoldás: Próbáljuk meg bebizonyítani az állítást. Ehhez a megoldás definíciója két pontját kell belátnunk.

Az pont teljesülése könnyen látható, ugyanis megoldása -nek, tehát

Az pont bizonyításánál azonban gond van, hiszen az alábbi két állítás áll rendelkezésünkre:

és ezekből a kívánt állítás nem bizonyítható. Elakadtunk a bizonyításban, lehet, hogy nem igaz az állítás? Készítsünk ellenpéldát felhasználva azt, hogy hol akadtunk el a bizonyításban!

Legyen , , és egyezzen meg az feladattal. Ekkor triviálisan megoldja -t, de nem megoldása -nek, ugyanis

Tehát az állítás nem igaz.

2.6. példa: Legyenek és programok, pedig Tegyükadat. Teggyük fel továbbá, hogy és megoldja az feladatot. Igaz-e, hogy megoldja -et?

Megoldás:Ha , akkor mit tudunk a programfüggvényüelőszörNézzük előszö az értelmezési tartományokat! A definíció szerint minden állapottérbeli ponthoz minden program hozzárendel legalább egy sorozatot, így és is. Mivel ezért csak az fordulhat elő, hogy egy adott ponthoz olyan sorozatokat is rendel, amit nem. Ha ezek a sorozatok mind végesek, akkor az adott pont vagy benne van mindkét program programfüggvényének az értelmezési tartományában, vagy egyikében sem, ha van közöttük végtelen is, az adott pont biztosan nem eleme értelmezési tartományának, de eleme lehet -nek. Tehát és .

Mivel megoldása -nek, ezért és . A fentiek miatt is és is teljesül, vagyis is megoldása -nek.