# Turing machine - polynomial time expression

by xeon123
Tags: expression, machine, polynomial, time, turing
 P: 80 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 $\in$ $\Delta$} 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)$\leq$ n^k + k. I don't understand what n^k+k means. Can anyone explain me the last expression? Thanks,
Mentor
P: 20,409
 Quote by xeon123 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 $\in$ $\Delta$} 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)$\leq$ n^k + k. I don't understand what n^k+k means. Can anyone explain me the last expression? Thanks,
Your definition for polynomial time seems to be a little off. It's usually defined as T(n) ≤ nk, without the additional k term that you showed.

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.

 Related Discussions Introductory Physics Homework 1 Calculus 2 Calculus & Beyond Homework 3 Special & General Relativity 13 Academic Guidance 3