1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook