Post#2 » Thu Jun 15, 2006 2:25 pm
Vraag 1:
|--* Is de transitieve en reflexieve sluiting.
Dit wil zeggen dat zij C1, C2 en C3 configuraties van de Turing machine.
Dan is als C1 |--* C2 en C2 |--* C3 dan geldt ook C1 |--* C3 (transitief)
dan is ook C1 |--* C1 (reflexief)
Basically komt het er op neer dat |--* een aantal stap relaties na elkaar is.
Een stap relatie zegt hoe je van een configuratie overgaat naar een volgende configuratie.
|--* zegt dat je van een configuratie in een aantal stappen naar een andere configuratie geraakt.
Vraag2:
De registers in de RAM zijn c+k*i+j
Aangezien de tijdscomplexiteit van de TM T(n) is, kan in 1 band hoogstens T(n) stappen opzij gegaan worden. Dus het grootste getal dat c+k*i+j kan zijn is dus c+k*T(n)+j
In de berekening van de kost van 1 bewerking wordt dit met het logaritmisch kost kriterium log(T(n))
En dan zijn er om te beginnen O(T(n)) stappen nodig om de TM te lezen en te simuleren dus in totaal is dit iets van O(T(n) * log(T(n)))
[img]http://users.skynet.be/quintensoetens/sigG4.jpg[/img]