--- # System prepended metadata title: Turing Machine tags: [計算理論] --- # Turing Machine Turing machine was proposed by **Alan Turing** in 1936. Used as automata in computational issues: * Decidabililty of problems * Time/Space complexity analysis of problems * Algorithms design and analysis A Turing machine can: 1. Read a symbol from the tape, but the symbol is not erased! 2. **Write** a symbol on the tape. 3. Move the head left or right. 4. Change its state. ## Components * An infinite input tape. * A state register. * A control unit. * A read/write head ## Mathematical Model A Turing machine is defined by: $$ M = (K, \Sigma, \delta, s, H) $$ Where: * $K$: A fintie set of states. * $\Sigma$: The alphabet. * $s$: Initial state. * $H$: The set of **halting** states, it is a subset of $K$. * $\delta$: The transition function. Transition function defines actions of $M$: * $\delta(q, a) \rightarrow (p, b)$: changing state and tape. * $\delta(q, a) \rightarrow (p, \rightarrow)$: move right. * $\delta(q, a) \rightarrow (p, \leftarrow)$: move left. ## Acceptance The machine **stops** when it enters a halting(final) state. The machine leaves the **result** in the tape. > If the transition function is not carefully designed, the machine may loop forever. ## Language of Turing Machine Recognition process of an input string: * Keep the input sting $w$ in the tape. * The TM processes $w$ according to its transition function. * The TM has 2 halting states, $H = {y, n}$ * If halting in $y$-state, it accepts the input string. * If halting in $n$-state, it reejects the string. ### Recursive Language Definition: A language is **recursive**, if it is **decidable** by some Turing machine. #### Compare with Context Free A PDA can always be simulated by using a Turing machine, so context free language is a proper subset of **recursive language class**. ### Recursively Enumerable Languages Definition: A language is **recursively enumerable**, if it is **semi-decidable** by some Turing machine. > Recursively Enumerable > Recursive #### Semi-Decidable A language $L$ is **semi-decidable** by Turing machine if: * For any string $w$ in $L$, $M$ enters the halting state, $h$, at the end of the computation. * For any string $w$ NOT in $L$: $M$ loops forever. > Compared with decidable carefully, "Decidable" means that Turning machine always halt in **y** or **n** state; "Semi-decidable" means halting or loop-forever. ### Semi-deciable vs Decidable Theorem: **Recursive language** class is a proper subset of **recursively enumerable language** class. > Because decidability is a proper subset of semi-decidability，所以說 Semi-decidable 會比 Decidable 強大。 ## Turing Computable Functions ### Numerical Computation Turing machines can be used to compute (numerical) functions. * The input (if any) is kept in the tape. * The results are left on the tape. ### Basic Functions Definition: Functions which are directly computable by using Turing machine. * The Turing machine are designed by using **mathematical definition** or **machine schema**. Key basic functions ($x$ and $y$ are binary number): * Minus 1: $x = x - 1$ * Add 1: $x = x + 1$ * Test zero: $x = 0 ?$ * 1's or 2's complement: $-x$ * Addition and subtraction: $x+y$, $x-y$. ### Recursive Function A function which is **computable** by Turing machine is called by a **recursive function**. Turing machine can compute functions of $n$ parameters. ### Function Classes Function classes: * Basic functions * Primitive recursive functions * Partial recursive functions ## Non-determinstic Turing Machine Definition: If the transition functions is replaced by a transition relation, the Turing machine becomes a non-deterministic Turing machine. A NTM may: 1. Hang on the current configuration since no action can be taken. 2. It may have multiple chocies for this configuration. ### Acceptance * If $w \in L$: There are **some** computations leading the machine into acceptance configurations. * If $w \notin L$: The machine always rejects the string. ### Decidable by NTM If the language $L$ is decidable by an non-determinsitc Turing machine $M$, then $L$ is still a recursive language. ### Semi-decidable by NTM If the language $L$ is **semi-decidable** by an non-determinsitc Turing machine $M$, then $L$ is still a **recursively enumerable language**. ## Determinstic Turing Machine Definition: For each configuration, a deterministic Turing machine has exactly only one operation to perform. ### Non-determinstic vs Determinstic Theorem: Every DTM is an NTM. Non-deterministic Turing machine can be converted into deterministic Turing machines. 非常重要！！！ In the aspect of **computational power**: **non-deterministic Turing machines = deterministic Turing machines.** **Theorem: Every DTM is an NTM.** * Transition functions are special cases of transition relations. * Therefore, DTM are NTM by definition. * DTM $\leq$ NTM Theoerm: Non-deterministic Turing machines can be converted into deterministic Turing machines. Conclusion: * NTM $\geq$ DTM. * NTM $\leq$ DTM. * Totally, NTM $=$ DTM. ![](https://i.imgur.com/WddL3Ml.png) ## Extensions We can add the following facilities to a Turing machines: 1. Multiple tapes. 2. Multiple heads. 3. Two-way tape. 4. Random access memory. 5. Two-dimensional memory. 6. A stack, multiple Turing machines in a Turing machine. These extensions may increase the efficiency of Turing machine, However, none of these facilities will increase the power of Turning mahcines. ## Church-Turing Thesis Turing machines are the **ultimate** computational devices. Turing machines = algorithms. Never be proved or denied. Any Turing machine solvable problems can be solved by using modern computers. Any Tuting machine sovlable problems can be solved by using algorithms. If a problem is unsolvable by using Turing machine, it's unsolvable for modern computer either. Therefore, no algorithm for solving such problem. ## Design Turing Machine Define a Turing machine by using the mathematical model is inconvenient. Understanding a Turing machine via its formal definition is not easy. Design Turing machine by using **machine schema**. ## Turing Equivalence A computational device which can simulate Turing machine is called **Turing Equivalence** or **Turing Complete**. # Machine Schema For finite automata, transition diagrams are easier to understand than formal models of finite automata, We can use a similar methodology to design Turing machine. * Represent Turing machine operations as basic instructions. * Code more instructions using these basic instructions. * Create complex instructions by using the available instructions. * Program advanced Turing machine by using this instructions set. * Draw flowcharts to represent Turing machine. Design Turing machine by using the following method: * Represent instructions by using symbols. * Create subroutines to form complex instructions. * Draw Turing machine by using flowcharts (Directed Graphs) * **Vertices**: symbols of instructions and subroutines. * **Arcs**: conditional / unconditional branches or loops. ## Basic Machines Use simple Turing machine as basic instruction, for example: * Writing an `a` in the tape $\rightarrow$ represented by the symbol 'a'. * Moving right, $\rightarrow$ represented by 'R'. * Moving left, $\rightarrow$ represented by 'L'. R a R: Means move right, write an 'a' and move right. * Conditional branches: if encounter an `a` move right: $\xrightarrow{a}R$ * Unconditional branches: just jump to there, and move right: $\rightarrow R$ * until encountering a certain symbol: $L_{\#}$: move left until encountering a '#'. $R_{\overline{\#}}$: move right until encounter a non-'#' symbol ### Example Copy machine: copy the string $w$ in the input tape and stop at the '#' between the two strings. $\#w\# \rightarrow \#w\#w\#$ ![](https://i.imgur.com/bRJvp5g.png) ## Multiple Tape We can use multiple tapes to keep the input, intermediate results, or results. Multiple tapes simplify Turing machine design. Use **superscripts** to indicate tape indices. * $R^1, a^2$ // Move right in tape 1, write an 'a' in tape 2. * $L^{1,2}, \#^2\#^1$ // Move left in tape 1 and 2, write a '#' in tape 1 and 2. # Functions 如果有一個 Function 可以被 Turing machine 計算，就稱之為 **Recursive Functions**。 Turing machines can be used to compute functions. However, not all functions are computable by Turing machines! Computable functions are divided into 3 classes: * Basic functions * Primitive recursive functions * $\mu$-recursive functions (partial recursive functions) Theorem: a function is $\mu$-recursive if and only if it is computable by Turing machines. > Partial recursive functions = Recursive functions > Primitive recursive，Primitive recursive 是 Recursive functions 的一種特例。 ## K-ary Basic Functions A k-ary function takes k arguments and produce one result. ## Basic Functions Some functions are so basic that we can design Turing machine computing them directly. ## Complicated Functions More complicated functions can be defined by using functional operators. * These functional operators are Turing machine computable! Functional operators: 1. function composition 2. recursive definition 3. definition by cases 4. minimalization ## Primitive Recursive Functions Definition: The primitive recursive function class includes: * Basic functions * Functions defined by using function **composition** * Functions defined by using **recursive definition** ### Primitive Recursive Predicates A function can be not only numerical but also logical. Definition: a primitive recursive function which return 1 or 0 is a primitive recursive predicate. ## Partial Recursive Functions Definition: The partial recursive functions class includes: * Basic functions * Functions defined by using function composition * Functions defined by using recursive definition * Functions defined by using **minimalization** # Unrestricted Grammar ## Definition $$ G = (V, \Sigma, R, S) $$ * $V$ is an alphabet. (Variables + Terminals) * $\Sigma$ is a subset of $V$, the set of terminals * $R$ is the set of grammar rules: $V^\star (V-\Sigma) V^\star \rightarrow V^\star$ * $S$ is a start **variable**. ### Unrestricted and Context Free Grammars Their definitions are very similar. However, only **one non-terminal** appears at the left hand sides of Context Free Grammar rules: $(V-\Sigma) \rightarrow V^\star$ ### Derivation String To derive a string: * Strarting with the initial symbol, a non-terminal. * Applying a grammar rule to replace a substring of the current string with another sub-string in each step. ### Grammar and CFG * Every Context-Free Grammar is a simplified grammar. * A grammar is not necessarily a Context-Free Grammar. * So **Grammar > Context-Free Grammar** ### Grammar and Turing Machines * Theorem: Unrestricted grammars are equivalent to Turing machines. * **Grammer**: language generators * **Turing Machine**: language recognizers. ### Recursively Enumerable Languages Theorem: The languages generated by unrestricted grammars are **recursively enumerable languages**. * $L$ is generated by a grammar if and only if $L$ is **semi-decidable** by a Turing machine. # Closure Properties ###### tags: `計算理論`