Tehetséggondozás az informatikában
Konklúzió…
…csak félig van.
Beláttuk, hogy a MIU-nyelv
rekurzív felsorolható: ez azt jelenti,
hogy számítógéppel (szakszerűbben fogalmazva Turing-géppel) felsorolhatóak a
szavai (abban az értelemben, ahogyan a természetes számok felsorolhatóak:
véges idő után
bármelyiket megkapjuk, miközben a felsorolás
soha nem ér véget: soha nem kapjuk meg
mindegyiket).
Nyitva maradt a kérdés, hogy a nyelv
rekurzív-e: van-e olyan
program (van-e olyan Turing-gép), amely tetszőleges karaktersorozatról véges
idő alatt eldönti, hogy az a nyelvnek szava-e?
S hogy a nyájas olvasó számára is maradjon (megválaszolható) kérdés: miért
nem elegendő a nyelv szavainak felsorolása ahhoz, hogy eldöntsük egy adott
jelsorozatról, hogy az szava-e nyelvnek?
Hiszen elegendőnek tűnik csupán
(A szerző szándékosan hagyta félbe az utolsó mondatot.)
(Mely persze így már)