Tehetséggondozás az informatikában
REális célkitűzések és irReális álmok
Úgy is fogalmazhatunk, hogy a MIU-játékban előállítható szavak egy nyelvet
alkotnak (nyelv alatt most pusztán szavak egy jól definiált halmazát értve).
E nyelv legalábbis egy vonatkozásban látványosan eltér például a magyar vagy
az angol nyelvtől
1 (most utóbbiak alatt is
csupán szavak egy halmazát értve): elfogadva azt a plauzibilis feltevést,
hogy a beszélt nyelvek minden szava korlátozott hosszúságú (teljesen
önkényesen például 1024 betűt választva felső korlátnak), kijelenthetjük,
hogy a magyar vagy az angol nyelvnek véges sok szava van, a MIU-nyelvnek
végtelen sok (elég arra gondolni, hogy már csak a D szabály is végtelen
sokat állít elő).
Nyilvánvaló az, hogy bizonyos jelsorozatok a nyelvhez tartozó szavak:
például a D szabály mechanikus alkalmazásával előállítható az M után 2, 4,
8, 16, … I betűt tartalmazó szó. Hasonlóképpen az U szabály után duplázva
megkaphatjuk a MIUIU, MIUIUIUIU, … szavakat.
Ugyancsak nyilvánvaló az, hogy az ábécével előállítható jelsorozatok
jelentős része nem lesz a nyelvnek szava: biztosan nem kaphatunk olyan szót,
amely nem M-mel kezdődik, illetve olyat, amelyben az M az első helyen kívül
is szerepel.
Az előző szakasz feladatai után kézenfekvő a kérdés: hogyan tudjuk eldönteni
azt, hogy egy jelsorozat eleme-e a nyelvnek? Tudunk-e olyan programot írni,
amely segít egy ilyen kérdés megválaszolásában?
Azt könnyű lehet igazolni, hogy egy jelsorozat a nyelvhez tartozik:
egyszerűen meg kell adni, hogy milyen lépésekkel vezethető le az MI szóból.
De hogyan igazolható az, hogy egy jelsorozat
nem állítható elő?
Hogyan igazolható az, hogy
soha, senki nem fog levezetést találni
hozzá?
Az angol (vagy a magyar) nyelv esetén éppen a szavak halmazának végessége
garantálja, hogy algoritmikusan
eldönthető legyen egy
jelsorozatról: szónak tekintjük-e. Elég ehhez abban megállapodni, hogy
melyik szótárt tartjuk ügydöntőnek (esetleg abban, hogy milyen toldalékolási
szabályokat engedünk meg): eztán már csak a szavakat (illetve a szabályokat)
kell számítógéppel tárolni, s adott jelsorozat esetén a megfelelő program
eldönti, hogy az szónak számít-e.
Végtelen sok szó esetén azonban a fentihez hasonló eljárás nem működik.
REményünk csupán arra van, hogy
felsoroljuk a nyelv szavait – már ha
felsorolásnak tekintjük azt az ígéretet, hogy egy végtelen hosszú ideig
működő számítógép előbb-utóbb a nyelv minden szavát ki fogja írni a
képernyőre…
1Az angol nyelv említésének egyetlen
kézenfekvő oka van: mivel ott –szemben a magyarral– igen korlátozottak a
toldalékolás lehetőségei, egyszerűbbnek tűnik annak eldöntése, hogy egy
betűsorozat szónak számít-e.