I try to evaluate working time of Turing machine. I understand, I have to calculate number of steps used in every stage. My problem is: how can I know, how many steps used in every stage, for example, n, n/2, n^2...
Computational problem L: L(x)=1, if input date x is in the form y#z, where y and z are strings of the same length. The strings consist of the symbols a and b.
This Turing machine works as follows:
Repeats the sequence of actions:
i. If first symbol is #, then move one symbol to the right. If there is blank, then accepts word, else reject word.
ii. If first symbol is blank, reject word.
iii. If first symbol is a or b, then:
a. clears this symbol and replaces it by blank;
b. move to the right until reach blank after end of the word;
c. move one symbol to the left. If there is a or b, clear it, replacing by blank;
d. move to the left until reach blank symbol;
e. move one step to the right (thus reaching the first non-cleared symbol of the word).
I have to estimate working time of Turing machine. It is enough with evaluation “Time is O(f(n)”, where f(n) is a function of some complexity (for example f(n)=n or n^2), but it must be justified.
I think, estimate of working time is this:
i.machine scans across the tape to verify if first symbol is #. Performing this scan, machine uses n steps. Accepting or rejecting, machine uses another n steps. So total number of steps used in this stage is 2n
ii.Step scans input. In the “worst case”, the input word satisfies the requirements and the machine has to scan all the way to the first blank symbol to find out. Thus, if the length of the input word is n, this takes O(n) steps
a.Clearing the symbol and replacing it with a blank, machine uses n steps, this takes O(n) steps.
b.Step scans input. In the “worst case”, the input word satisfies the requirements and the machine has to scan all the way to the first blank symbol to find out. Thus, if the length of the input word is n, this takes O(n) steps
c.machine scans across the tape to verify if there is a or b. Performing this scan, machine uses n steps. Clearing the symbol and replacing it with a blank, machine uses another n steps. So total number of steps used in this stage is 2n
d.The number of steps performed on the input word; in the worst case, all characters have been crossed out before, and the number of steps is n. We can bound all possible cases by O(n)
e.The number of steps is n. We can bound all possible cases by O(n)
Note how many times the cycle will be repeated where n at the beginning of each cycle is reduced by 1, t.i., n-1.
Thus the total steps of M on an input of length n are 2n + O(n) + O(n) +O(n)+2n+O(n)+O(n)= O(n). f(n)=n