Variants

Definition

A Nondeterministic TM (TM) is the same 7-tuple, just
No longer this transition relation:
- $\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\} \quad (L = \text{Left}, R = \text{Right})$
Utilize power set:
- $\delta: Q \times \Gamma \rightarrow \mathcal{P} (Q \times \Gamma \times \{L, R\})$

Recall

The NFA and the DFA are equivalent in power
The PDA and the deterministic PDA are not equivalent in power
The NTM and TM are equivalent in power.

Theorem

$A$ is $T-recognizable$ iff some NTM recognizes $A$
It is trivial for an NTM to emulate a TM
- Impose the restriction that sets mapped in $\delta$ have cardinality =1

Theorem

$A$ is $T-recognizable$ iff some NTM recognizes $A$
We will show we can convert an NTM to a TM.

Insight

For any computation, we can view the set of possible computations as a tree.
Consider fast exponentiation by squares:

def exp_by_squaring(a, n):
    if n == 0:
        return 1
    elif n == 1:
        return a
    elif n % 2 == 0:
        return exp_by_squaring(a * a, n / 2)
    else:
        return a * exp_by_squaring(a * a, (n - 1) / 2)

Insight

It would be much faster to ignore checks.

def exp(a, n, magic):
    return [1,a,exp(a * a, n / 2),a * exp(a * a, (n - 1) / 2)][magic]

Insight

Imagine a growing tree

def exp(a, n, magic):
    return [1,a,[1,a,exp(a ** 4, n / 4),a * exp(a ** 4, (n - 1) / 4)],a * exp(a * a, (n - 1) / 2)][magic]

Nondeterministic

Recurse

Recurse everywhere

Recurse recursively

It’s tree

Take one path

Multi-tape

Store state as separator

Create new tape on branch

Theorem 9

$A$ is $T-recognizable$ iff some NTM recognizes $A$

Proof.

Aside

There exists a formulation called a “Turing Enumerator”
It is a generator rather than a recognizer.
Left as an exercise.

Variants

Sketch

Questions

Multi-tape

Motivation

Minimal model

Theorem

Theorem

Statement

Statement

Graphically

Single Tape

Show heads

Extend Alphabet

In Practice

Theorem 8

Nondetermistic

Definition

Recall

Theorem

Theorem

Insight

Insight

Insight

Nondeterministic

Recurse

Recurse everywhere

Recurse recursively

It’s tree

Take one path

Multi-tape

Store state as separator

Create new tape on branch

Theorem 9

Aside

Stretch Break