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

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.