I am reading two books about the Turing Machine.

  1. "Computational Complexity" by Christos H. Papadimitriou.
  2. "Computational Complexity: A Modern Approach" by Sanjeev Arora and Boaz Barak.

However, the definitions in these books have a little differences and I do not figure out the relationship between the following concepts:

  1. A language is computable by a TM.
  2. A language can be decided by a TM.

What does the "language" exactly mean? A function or a set?

What is the relationship between them?

Is there a kind of containment relationship between them?


1 Answer 1


Given a finite alphabet $\Sigma$. We define the set of all words of finite length to be $\Sigma^*$ (including the empty word $epsilon$).

A language $L$, w.r.t $\Sigma$, is defined to be a subset of $\Sigma^*$.

Now, when TMs run on their input (a word). One of the following holds:

1- the run halts (in this case, the TM accepts the input word or rejects it)

2- the run does not halt.

For the answer: A language $L$ is decidable iff there is a TM $M$ such that $M$ halts on every input word $x$. And $x$ is accepted iff $x \in L$.

However, a function $f: \Sigma^* \longrightarrow \Sigma^*$ is computable iff there is a TM $M$. such that for every input word $x$. The run of $M$ on $x$ halts with $f(x)$ written on its tape.

Note: when I write TM, I refer to deterministic turing machines

  • $\begingroup$ The class $\mathrm{\textbf{DTIME}}$ is defined as following: "Let $T : \mathbb{N} \rightarrow \mathbb{N}$ be some function. A language $L$ is in $ \mathrm{\mathbf{DTIME}}(T(n))$ iff there is a TM that runs in time $c \cdot T(n)$ for some constant $c > 0$ and decides $L$." So, $L$ is just a set, how can we define the running time of $L$? $\endgroup$
    – Blanco
    Sep 26, 2017 at 16:04
  • $\begingroup$ As you mentioned, time is defined for a TM, not a language. We say that a language L is decided in time T(n) (or L is in DTIME(T(n))) iff it is $decidable$ by a TM M s.t. M runs in time T(n), where n is the length of the input word. Meaning that the number of steps (the transitions) that M makes in its run on a word of length n is T(n) (up to a constant). All in all, we can talk about the time in which a language can be decided in by a TM. $\endgroup$ Sep 26, 2017 at 16:14
  • $\begingroup$ So, given a TM, the time it runs in on every words is fixed? But this definition says that the TM runs in $T(n)$ on every $x$ not the $x \in L$ $\endgroup$
    – Blanco
    Sep 26, 2017 at 16:22
  • $\begingroup$ I expressed it wrong, I mean the time is just only up to the size of $x$, it not depends on $L$? $\endgroup$
    – Blanco
    Sep 26, 2017 at 16:29
  • 1
    $\begingroup$ Some of your questions are answered in your books, e.g. the relationship between search problems (like finding a hamiltonian path) and decision problems (like deciding if a hamiltonian path exists). Be more patient with your reading. Also your questions are not appropriate for this site, because they are not research level. Try cs.stackexchange.com $\endgroup$ Sep 26, 2017 at 17:10

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