1
$\begingroup$

From Ullman and Hopcroft's Introduction to automata theory, languages, and computation

Consider the off-line Turing machine M of Fig. 12.1. M has a read-only input tape with endmarkers and k semi-infinite storage tapes. If for every input word of length n, M scans at most S(n) cells on any storage tape, then M is said to be an S(n) space-bounded Turing machine, or of space complexity S(n). The language recognized by M is also said to be of space complexity S(n).

Consider the multitape TM M of Fig. 12.2. The TM has k two-way infinite tapes, one of which contains the input. All tapes, including the input tape, may be written upon. If for every input word of length n, M makes at most T{n) moves before halting, then M is said to be a T{n) time-bounded Turing machine, or of time complexity T(n). The language recognized by M is said to be of time complexity T(n).

If I am correct, a language can be the one recognized by several Turing machines.

Do the last sentences in the two paragraphs assume that for a language, all of its recognizer TMs have the same time complexity and the same space complexity?

  • Is the assumption true?

  • If the assumption is not true, do the sentences imply taking supremum of the complexities over all of the recognizer TMs of the language?

Thanks.

|cite|improve this question|||||
$\endgroup$
2
$\begingroup$

Yes, you are correct. I applaud your careful reading.

This reading is most obvious if we view a TM as an algorithm (which they are). Clearly, for any computational problem, some algorithms are more efficient than others. Compare bubble sort to merge sort, for example.

But their definition is not wrong, just perhaps a little misleading. Any algorithm can provide a time-bound on a decision problem; but only one of them will be the lowest bound.

|cite|improve this answer|||||
$\endgroup$
  • $\begingroup$ thanks. (1) do you mean to take the lowest time or space over all TMs as the time or space complexity of a language? (2) If yes, does a TM which achieves the lowest time or space at one input string size n also achieves the lowest at other input string sizes, so that this TM can achieve the lowest at every input string size and be chosen to define the time or space complexity of the function at all input string sizes? $\endgroup$ – Tim Oct 2 '16 at 5:03
  • $\begingroup$ @Tim We usually don't use such notions as time or space complexity in regards to a language, only to an algorithm. So I actually find the terminology that you quoted a bit odd. Typically, we instead put languages into complexity classes instead. This higher-level view allows us to abstract away from the particular computational model used, since e.g. a RAM machine will always be faster than a Turing machine even with the same algorithm. The answer to your second question is "no". For example, we could always modify the current "fastest" algorithm to hardcode the answer to a specific input. $\endgroup$ – gardenhead Oct 2 '16 at 6:02
  • $\begingroup$ Thanks. "we could always modify the current "fastest" algorithm to hardcode the answer to a specific input." Do you mean that for a problem, the fastest algorithm doesn't exist? Can we hardcode the answers to each input in one algorithm, so that this algorithm will be the fastest one? $\endgroup$ – Tim Oct 4 '16 at 7:22
  • $\begingroup$ @Tim I mean only for any specific input we could always hard-code an answer. We obviously cannot do this for an infinite language. Moreover, hard-coding an answer will slow down the algorithm on other inputs, because then we always have to check for that input before running the generic algorithm. Also, see Blum speed-up theorem. There is in general no optimal algorithm for a problem. $\endgroup$ – gardenhead Oct 4 '16 at 13:55
  • $\begingroup$ (1) "hard-coding an answer will slow down the algorithm on other inputs, because then we always have to check for that input before running the generic algorithm." Do it mean the same as the no-free lunch theorem? (2) Does Blue speed-up theorem describe cases which contradict the quote in (1)? $\endgroup$ – Tim Oct 4 '16 at 17:04

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.