# Is every decidable language recognizable by a Turing Machine space-bounded by some f(|w|)?

The negative answer to decidable = non-contracting grammar? suggests the following question:

Is there a decidable language that can be recognized only by a space unrestricted Turing Machine (i.e. with infinite tape but in finite time)?

This is, are there words, w, in a decidable language for which cannot be determined a bound f(|w|)?

• What is a restricted turing machine? May 2 at 10:37
• @nirshahar It is a Turing machine with an upper bound on the amount of tape it can use, related to length of its input. For instance, languages by type-1 grammars, can be recognized by a linear bounded Turing Machine (they don't need more thant k |w| space to accept word w). May 2 at 10:49
• As Yuval has pointed, for a decidable language L, f() can always computed. If $M_L$ is the deciding TM for L, then f() can be calculated for a given length n just by taking the longest time/space used for $M_L(w)$ where |w| = n. May 3 at 9:46

## 1 Answer

Consider a Turing machine which reads its input and then immediately stops. This Turing machine always halts on every input, but the running time is unbounded: the machine runs for $$n$$ steps on an input of length $$n$$.

In fact, most halting Turing machines have unbounded running time: if the running time of a Turing machine is bounded by $$T$$, then the language it decides can only depend on the first $$T$$ symbols of the input.

If a Turing machine always halts on any input, then there is a function $$f(n)$$ such that the Turing machine always halts within $$f(n)$$ steps on an input of length $$n$$. You can take as $$f(n)$$ the maximal time it takes the Turing machine to halt on an input of length $$n$$. Since there are only finitely many words of length $$n$$ (recall that the input alphabet is fixed), this is well-defined.

Furthermore, if a Turing machine always halts on any input, the function $$f(n)$$ defined in the preceding paragraph is always computable. You can compute it by simulating the machine on all possible inputs of length $$n$$.

Space works exactly the same way.

• Mmmm, sorry now I'm confused. Just to clarify: are your saying that for any decidable language there is a stoping Turing Machine with space bounded by some suitable function f(n) where n is the length of the input? May 2 at 17:24
• For your sentence "This Turing machine always halts on every input, but the running time is unbounded: the machine runs for n steps on an input of length n" I would say that the running time is bounded O(n), thus not really unbounded. Thus, what I'm trying to ask if every stoping Turing Machine has a O(f(n)) space (or time). Maybe I'm asking a nonsense. Sorry. May 2 at 17:33
• If a language is decidable, then by definition there is a Turing machine that decides it. This Turing machine runs in time $f(n)$, where $f(n)$ is defined in my answer. Similarly, it uses space $g(n)$, where $g(n)$ is the maximum space it uses on all (finitely many) words of length $n$. May 2 at 17:37
• So the answer to the question title is YES. Right? May 3 at 9:18
• Your "restricted Turing machine" is just a Turing machine which halts on every input. May 3 at 9:22