0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Your input is a sequence of words of $a,b$ spaced with a few blanks. Your algorithm works on each word one by one $\endgroup$
    – reuns
    Apr 27, 2019 at 17:56
  • $\begingroup$ reuns, can you say, what is working time O(f(n)) ? $\endgroup$ Apr 27, 2019 at 19:27
  • $\begingroup$ I assume you need the running time estimate as a function of the length of the input word. If that is the case, here's a hint. Follow the machine step by step for a few short input words and think about how many times you visit each $a$ or $b$. (Of course the problem would be the same if you just used $a$ and the character #.) $\endgroup$ Apr 28, 2019 at 20:59

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.