The Special Case of Non-Deterministic Turing Machines


Home / The Special Case of Non-Deterministic Turing Machines

One Sample Non-Deterministic Turing Machine

A typical use of any TM is pattern recognition: it accepts a string of symbols.

This example uses two symbols {A, B}. An acceptable pattern is any substring “(Ai, Bi, Ai, Bi) for i > zero.” The TM should halt in an “accept” state when it finds a string with the same number of ‘A’s, ‘B’s, ‘A’s and ‘B’s embedded in the input tape. If it runs out of input before accepting, it will halt in a “reject” state.

The shortest acceptable string is ‘ABAB…’. This TM will also accept ‘AABBAABB…’. In either case, there could be any number of letters to the right of the strings, but the TM would stop and accept without reading them.

One Non-Deterministic Turing Machine Tape, image by Mike DeHaan

One Non-Deterministic Turing Machine Tape: Image by Mike DeHaan

The difficulty comes in accepting ‘AAABBAABB…’. After the TM has read the second ‘B’, it might “hope” that the next symbol is another ‘B’, because that continues an acceptable string of three ‘A’s followed by three ‘B’s. When it reads that the sixth symbol is ‘A’, a deterministic TM must backtrack through the preceding ‘B’s and the same number of ‘A’s; then resume searching for the pattern starting with the second ‘A’.

A non-deterministic TM could avoid rewinding the tape by starting a parallel decision process as it reads each ‘A’ from left to right. This NTM runs five parallel processes, each numbered for the corresponding first ‘A’:

  1. The first process rejects ‘AAABBA…’
  2. The second accepts ‘.AABBAABB…’
  3. The third rejects ‘..ABB…’
  4. The fourth process was still working on ‘…AABB.’
  5. The fifth rejects ‘…ABB’ when it reads the second ‘B.’

Do NTMs Lead to Practical Applications?

Some modern processing chips run a limited number of parallel computations. A processor might pre-fetch data to suit either path of an “if…else” branch, prior to resolving the condition.

Parallel processing is implemented in most graphics processing chips. If each pixel’s value can be determined independently of the other pixels, then all can be computed at once.

Leave a Comment