# What's the differences between "A language is computable by a TM" and "A language can be decided by a TM"? [closed]

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?

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

• 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$? Sep 26, 2017 at 16:04
• 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. Sep 26, 2017 at 16:14
• 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$ Sep 26, 2017 at 16:22
• I expressed it wrong, I mean the time is just only up to the size of $x$, it not depends on $L$? Sep 26, 2017 at 16:29
• 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 Sep 26, 2017 at 17:10