Note on Computational Complexity - 1.1 Models of computation-Turing Machines

[!NOTE] This work is licensed under a Creative Commons Attribution 4.0 International License. Read more

Chapter 1. Models of computation

1.1 Turing Machines

1.1.1 Definitions

A Turing Machine (we will use TM in short) is a theoretical computational model introduced by Alan Turing in 1936. It is used to define the limits of what can be computed and serves as a foundation for theoretical computer science.

---

Definition: A TM, $M$, is a tuple $(\Gamma, Q, \delta)$ which is defined as

• A set $\Gamma$ of the symbols that $M$’s tapes can contain. We assume that $\Gamma$ contains a designated “blank” symbol, denoted $\square$, a designated “start” symbol, denoted $\triangleright$ and the numbers 0 and 1. We call $\Gamma$ the alphabet of $M$.
• A set $Q$ of possible states $M$’s register can be in. We assume that $Q$ contains a designated start state, denoted $q_{\text{start}}$ and a designated halting state, denoted $q_{\text{halt}}$. Note: the states in this definition refers to the state of the whole machine. Sometimes, we may also use the word configuration to mean the same thing.
• A function $\delta: Q \times \Gamma^k \to Q \times \Gamma^k \times \{\text{L, S, R}\}^k$ describing the rule $M$ uses in performing each step. This function is called the transition function of $M$.

---

All tapes except for the input are initialized in their first location to the start symbol $\triangleright$ and in all other locations to the blank symbol $\square$. The input tape contains initially the start symbol $\triangleright$, a finite non-blank string (``the input’’), and the rest of its cells are initialized with the blank symbol $\square$. All heads start at the left ends of the tapes and the machine is in the special starting state $q_{\text{start}}$. This is called the start configuration of $M$ on input $x$. Each step of the computation is performed by applying the function $\delta$ as described above. The special halting state $q_{\text{halt}}$ has the property that once the machine is in $q_{\text{halt}}$, the transition function $\delta$ does not allow it to further modify the tape or change states. Clearly, if the machine enters $q_{\text{halt}}$ then it has halted. In complexity theory we are typically only interested in machines that halt for every input in a finite number of steps.

For calculation part, if $M$ now is in state $q$ with $\Alpha=(\alpha_i)_{i\in[1,k]}$ are the current letters be read on $k$ tapes and $\delta(q,\Alpha)=\delta(q',\Beta, t)$ where $\Beta=(\beta_i)_{i\in[1,k]}$ and $t\in\{\text{L, S, R}\}^k$, then in next step $M$ will enter a new state $q'$ from $q$ where each word $\alpha_i$ on the tape is replaced by $\beta_i$ and the state of the i-th head is changed to $z_i$, namely to Left, Stay or to Right.

Some definitions of a Turing machine add additional details to the tuple, like having a limited input alphatable $\Sigma\supseteq\Gamma$ or an explicit set of accepting state $A\subseteq Q$. We will include these details as needed.

For the definition of $Q$, if we allow the Turing machine to do nothing, we do not necessarily need to include an explicit halting state. Instead, we can define the machine to halt if it reaches a state where it does not move its heads, change states or any symbols on the tape. But, it is often convenient to include an explicit halting state $q_{\text{halt}}$ (with the convention that the machine will not do anything once it reaches this state), or, for machines that accept or reject their input, explicit accepting and rejecting states $q_{acc}$ and $q_{rej}$.

1.1.2 Complexity

After having the definition of TM, we now can formalize the notion of running time. As every non-trivial algorithm needs to at leastread its entire input, by “quickly” we mean that the number of basic steps we use is small when considered as a function of the input length.

---

Definition:

    Let $f : \{0,1\}^* \to \{0,1\}^*$ and let $T : \mathbb{N} \to \mathbb{N}$ be some functions, and let $M$ be a Turing machine. We say that $M$ \textit{computes} $f$ in $T(n)$-time if for every $x \in \{0,1\}^*$, if $M$ is initialized to the start configuration on input $x$, then after at most $T(|x|)$ steps it halts with $f(x)$ written on its output tape.

    We say that $M$ computes $f$ if it computes $f$ in $T(n)$ time for some function $T : \mathbb{N} \to \mathbb{N}$.

---

---

Remark: As a convention, we require $T(n)\geqslant n$ for $n$ large enough(since we always need time to read the input) and if that computes the function $x\to\llcorner(T(n))\lrcorner$ in time $T(n)$ (As usual, $\llcorner(T(n))\lrcorner$ denotes the binary representation of the number $T(|x|)$.), we call it time-constructable.

---

1.1.3 Robustness

Using this Complexity concept, we may prove our TM with $k$ heads and tapes is same as simplest TM(i.e. has only 1 head and a tape) up to polynomial time transformation on time and space complexity(and this blow up is inevitabe and worst case will be $5kT^2(n)$).

---

Proof:

Left to readers

---

1.1.4 Universal Turing Machine

• 2025 3

2025

流形上的分析 Calculus on Manifold 笔记

49 分钟阅读

[!NOTE] This work is licensed under a Creative Commons Attribution 4.0 International License. Read more

CMU15-855(2017fall)PS1&sol

少于 1 分钟阅读

[!NOTE] This work is licensed under a Creative Commons Attribution 4.0 International License. Read more

Note on Computational Complexity - 1.1 Models of computation-Turing Machines

4 分钟阅读

[!NOTE] This work is licensed under a Creative Commons Attribution 4.0 International License. Read more

返回顶部 ↑