[AlgEnComp] Vragen bij hfst 2 van algo

[Beatles]

Vraag 1:
Kan er mij nog eens iemand uitleggen wat reflexieve sluiting is. Dit is terug te vinden op p26 onderaan. (Bij da tering gedoe :-p)

Vraag 2:
Leg uitvoeriger uit waarom er O(T(n)*log(T(n))) komt voor het logaritmisch kost criterium. In het bijzonder : de opmerking over "het grootste getal".
p29

[Quintus Maximus]

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)))