2
$\begingroup$

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|)?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ What is a restricted turing machine? $\endgroup$
    – nir shahar
    Commented May 2, 2021 at 10:37
  • $\begingroup$ @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). $\endgroup$
    – cibercitizen1
    Commented May 2, 2021 at 10:49
  • $\begingroup$ 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. $\endgroup$
    – cibercitizen1
    Commented May 3, 2021 at 9:46

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – cibercitizen1
    Commented May 2, 2021 at 17:24
  • $\begingroup$ 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. $\endgroup$
    – cibercitizen1
    Commented May 2, 2021 at 17:33
  • $\begingroup$ 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$. $\endgroup$
    – Yuval Filmus
    Commented May 2, 2021 at 17:37
  • $\begingroup$ So the answer to the question title is YES. Right? $\endgroup$
    – cibercitizen1
    Commented May 3, 2021 at 9:18
  • $\begingroup$ Your "restricted Turing machine" is just a Turing machine which halts on every input. $\endgroup$
    – Yuval Filmus
    Commented May 3, 2021 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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