ITEC 420 - Section 3.2 - Variants of Turing Machines

Main Results

Proof Idea for Theorem 3.13

Theorem 3.16

Theorem 3.16: How to Prove?

Executing Possible Computations on the Nondeterministic Turing Machine

Representing a Nondeterministic Choices

Theorem 3.16 Proof: Simulating a Nondeterministic Machine

Algorithm for Theorem 3.16: Simulate N on D

  1. Intialize Tape 1.

  2. Initialize Tape 3 with the number for the first possible computation N

  3. Loop
    1. Copy Tape 1 to Tape 2

    2. Execute N using Tape 2 as input and following the computation choices specified in Tape 3
      1. If sequences of choices represents an accepting computation for N (ie N enters an Accept state), then D halts and accepts
      2. Else (ie a number represents an infeasible or rejecting computation) continue with the next step

    3. Initialize Tape 3 with the string that represents the next possible sequence of choices of N

    4. Repeat loop

N and D are Equivalent

Avoiding Looping

Deciders and Recognizers



Theorem 3.21

Proof Idea for Theorem 3.21