151 Complexity — DTIME

151.1 Overview

This module defines what it means for a finite multi-tape Turing machine over the binary alphabet to decide a language within a time bound, introduces the deterministic time classes \(\mathrm{DTIME}(T)\) of languages decidable in time \(c \cdot T\) for some constant \(c\), and proves two basic structural facts: monotonicity of \(\mathrm{DTIME}\) in the time bound, and emptiness of the class when the bound vanishes at some input length.

151.2 Declarations

Definition 151.1 Deciding a language within a time bound

✓

Let \(M\) be a finite multi-tape Turing machine over the binary alphabet, let \(L\) be a language over \(\{ 0,1\} \) (a set of finite binary strings), and let \(T : \mathbb {N} \to \mathbb {N}\) be a time bound. We say that \(M\) decides \(L\) within time \(T\) if on every input string \(x\) the machine halts within \(T(|x|)\) steps and produces the single-symbol output \(1\) when \(x \in L\) and \(0\) when \(x \notin L\).

Definition 151.2 The deterministic time class \(\mathrm{DTIME}(T)\)

✓

For a time bound \(T : \mathbb {N} \to \mathbb {N}\), the class \(\mathrm{DTIME}(T)\) consists of all languages \(L\) over the binary alphabet for which there exist a constant \(c \in \mathbb {N}\) and a finite multi-tape Turing machine \(M\) over the binary alphabet such that on every input \(x\) the machine \(M\) halts within \(c \cdot T(|x|)\) steps and outputs \(1\) if \(x \in L\) and \(0\) otherwise.

Theorem 151.3 Monotonicity of \(\mathrm{DTIME}\) in the time bound

✓

Let \(T_1, T_2 : \mathbb {N} \to \mathbb {N}\) be time bounds with \(T_1(n) \le T_2(n)\) for every \(n\). Then \(\mathrm{DTIME}(T_1) \subseteq \mathrm{DTIME}(T_2)\): every language over the binary alphabet decided by some finite multi-tape machine within \(c \cdot T_1(n)\) steps on inputs of length \(n\), for some constant \(c\), is also decided by such a machine within \(c \cdot T_2(n)\) steps.

Theorem 151.4 Vanishing time bounds give the empty class

✓

Let \(T : \mathbb {N} \to \mathbb {N}\) be a time bound with \(T(n) = 0\) for at least one input length \(n\). Then \(\mathrm{DTIME}(T) = \emptyset \): no language over the binary alphabet is decidable by a finite multi-tape machine within \(c \cdot T\) steps for any constant \(c\), because on an input of length \(n\) the allotted budget is \(c \cdot T(n) = 0\) and no machine halts in zero steps.