Turing machine  polynomial time expressionby xeon123 Tags: expression, machine, polynomial, time, turing 

#1
Apr2612, 02:22 PM

P: 81

In the Turing Machine, the machine accepts a word if the computation terminates in the accepting state. The language accepted by the machine, L(M), has associated an alphabet Δ and is defined by
L(M) = {w [itex]\in[/itex] [itex]\Delta[/itex]} This means that the machine understands the word w if w belongs to the language. We denote by Tm(w) the number of steps in the computation of M on the input w. If the computation never halts, then Tm(w)=infinity. Also, we denote the worst case run time of M as Tm(n) = max{Tm(w)} which means the biggest words in the dictionary (I suppose). But, we say that M runs in polynomial time if there exists k such that for all n, T(n)[itex]\leq[/itex] n^k + k. I don't understand what n^k+k means. Can anyone explain me the last expression? Thanks, 



#2
Apr2612, 02:51 PM

Mentor
P: 20,939

If you do a search for "polynomial time" this is one of the links that you'll see: http://www.wordiq.com/definition/Polynomial_time. 


Register to reply 
Related Discussions  
Polynomial expression of Pendulum period... with respect to angle (large)  Introductory Physics Homework  1  
Evalute expression of associated Legendre's polynomial  Calculus  2  
Is it true that the derivative of 1/(random polynomial expression) is 0?  Calculus & Beyond Homework  3  
Black Hole Time Machine (time dilation)  Special & General Relativity  13  
Touring Grad Schools  Academic Guidance  3 