gistfile1.txt

Betragt følgende omskrivningsregler over strenge i alfabetet {I, U}

    (1)    X  -->  XX
    (2)   YI  -->  YIU
    (3)  III  -->  U
    (4)   UU  -->  

hvor reglerne (1) og (2) opererer på hele strengen, og reglerne (3) og (4) kan operere
et vilkårligt sted inde i strengen.

Vi ønsker nu at vise, at man ikke kan omskrive strengen I til strengen U med dette system.

Vi definerer #I(S) til at betegne antallet af I'er i strengen S.  Da vil følgende lemma gælde:

Lemma:
    Lad S være en streng i alfabetet {I, U}, og T være resultatet af et antal omskrivninger
    med reglerne (1)-(4) på S.

    Da vil der gælde, at hvis 3 ikke går op i #I(S), da vil 3 ej heller gå op i #I(T)

Bevis:
    Vi beviser dette induktivt på antallet af omskrivninger.

    Ved 0 omskrivninger gælder sætningen trivielt.

    Antag at omskrivningen fulgte kæden: S -> S(1) -> S(2) -> ... -> S(n) -> T
    Per induktionsantagelsen ved vi, at 3 ej går op i #I( S(n) ).

    Ønsker derfor at vise, at ligegyldig hvilken af reglerne (1)-(4) vi vælger,
    så omskrives S(n) til en streng T, hvor 3 ej går op i #I(T).

    Reglerne 2 og 4 påvirker ej antallet af I'er, hvorfor kravet er opfyldt.

    Ved brug af regel 1 gælder der, at

        #I(T) = 2 #I( S(n) )

    Men da 3 ej går op i #I( S(n) ), vil 3 ej heller gå op i 2 #I( S(n) ),
    hvorfor kravet er opfyldt.

    Ved brug af regel 3 gælder der, at

        #I(T) = #I( S(n) ) - 3

    Men da 3 ej går op i #I( S(n) ), og vi trækker et multiplum af 3 fra, da vil
    3 ej heller gå op i #I( S(n) ) - 3, hvorfor kravet er opfyldt.

Det ønskede resultat følger lemmaet samt følgende observationer.

    3 går ikke op i #I(I) = 1
    3 går op i #I(U) = 0