# 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.


## 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\#$

## 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: `計算理論`