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,\mathrm{\Sigma },\delta ,s,H)$$
Where:

• $K$: A fintie set of states.
• $\mathrm{\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)\to (p,b)$: changing state and tape.
• $\delta (q,a)\to (p,\to )$: move right.
• $\delta (q,a)\to (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
  $\le$ NTM

Theoerm: Non-deterministic Turing machines can be converted into deterministic Turing machines.
Conclusion:

• NTM
  $\ge$ DTM.
• NTM
  $\le$ 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
  $\to$ represented by the symbol 'a'.
• Moving right,
  $\to$ represented by 'R'.
• Moving left,
  $\to$ represented by 'L'.

R a R: Means move right, write an 'a' and move right.

• Conditional branches:
  if encounter an a move right:

  $\stackrel{a}{\to }R$

• Unconditional branches:
  just jump to there, and move right:

  $\to R$

• until encountering a certain symbol:
  

  $L_{\mathrm{\#}}$: move left until encountering a '#'.
  
  $R_{\overline{\mathrm{\#}}}$: 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.

$\mathrm{\#}w\mathrm{\#}\to \mathrm{\#}w\mathrm{\#}w\mathrm{\#}$

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},{\mathrm{\#}}^2{\mathrm{\#}}^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,\mathrm{\Sigma },R,S)$$

• $V$ is an alphabet. (Variables + Terminals)
• $\mathrm{\Sigma }$ is a subset of
  $V$, the set of terminals
• $R$ is the set of grammar rules:
  $V^{\star }(V-\mathrm{\Sigma })V^{\star }\to 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-\mathrm{\Sigma })\to 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: 計算理論