I try to evaluate working time of Tjuring machine, but I really don't know how to do it. 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 Tjuring 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 Tjuring 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), bet it must be justified.
I think, estimate of working time is this:
we have to understand how many times we you going from the front of the string to the end and back to the front. If the string y#z is length 2n+1, then we check the front of the string, then do 2n+1 steps to get to the end of the string, then 2n steps back, then 2n-1 steps to get to the end, then 2n-2 steps back, etc. This is the sum of all integers from 1 to 2n+1, which is a quadratic value: (2n+1)*(2n+2)/2 = 2n^2 + 3n + 1. So the total number of steps is O(n^2)
I am really not sure is my idea correct
