Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Turing machine - polynomial time expression

  1. Apr 26, 2012 #1
    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?

    Last edited by a moderator: Apr 26, 2012
  2. jcsd
  3. Apr 26, 2012 #2


    Staff: Mentor

    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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Turing machine - polynomial time expression
  1. MAX - expression (Replies: 1)

  2. Simplify this expression (Replies: 10)

  3. Expressions in English (Replies: 3)

  4. Expressing sets (Replies: 2)